Apa itu Hash Table? Penjelasan Lengkap untuk Pemula

Pendahuluan

Bayangkan kamu bekerja di sebuah perpustakaan besar. Ada ribuan buku di sana, dan setiap hari kamu harus mencari buku tertentu. Jika buku-buku tersebut disusun secara acak, kamu harus memeriksa satu per satu — butuh waktu sangat lama. Tapi jika buku disusun berdasarkan sistem kode tertentu (seperti sistem Dewey Decimal), kamu bisa langsung menuju rak yang tepat dalam hitungan detik.

Itulah konsep dasar Hash Table — sebuah struktur data yang memungkinkan kita menyimpan dan mengambil data dengan sangat cepat, hampir seperti “langsung ke rak yang tepat” tanpa harus mencari satu per satu.

Hash Table adalah salah satu struktur data paling penting dan paling sering digunakan dalam dunia pemrograman. Jika kamu sudah membaca artikel tentang Mengenal Big O Notation: Cara Mengukur Efisiensi Algoritma, kamu akan senang mendengar bahwa Hash Table bisa melakukan pencarian, penyisipan, dan penghapusan data dalam waktu O(1) — konstan, tidak peduli seberapa besar datanya!

Konsep Dasar Hash Table

Hash Table (atau Hash Map) adalah struktur data yang menyimpan pasangan key-value (kunci-nilai). Setiap data disimpan dengan sebuah “kunci” unik yang memudahkan pengambilan data tersebut di kemudian hari.

Komponen utama Hash Table:

• Key: Identifikasi unik untuk data (misalnya: username, NIK, nomor pesanan)
• Value: Data yang ingin disimpan (misalnya: profil user, alamat, detail produk)
• Hash Function: Fungsi yang mengubah key menjadi angka indeks
• Bucket/Array: Tempat penyimpanan data yang sebenarnya

Analogi sederhananya: bayangkan Hash Table seperti loker di gedung perkantoran. Setiap karyawan punya kunci loker dengan nomor tertentu. Ketika ingin mengambil barang, karyawan langsung ke nomor lokernya — tidak perlu memeriksa semua loker.

# Dictionary di Python adalah implementasi Hash Table bawaan
loker_karyawan = {
    "Budi": "Laptop + Dompet",
    "Sari": "Tas + Kunci Motor",
    "Andi": "Buku + Charger"
}

# Mengambil isi loker berdasarkan nama (key)
print(loker_karyawan["Budi"])  # Output: Laptop + Dompet
print(loker_karyawan["Sari"])  # Output: Tas + Kunci Motor

Bagaimana Hash Function Bekerja

Inti dari Hash Table adalah Hash Function — fungsi yang mengubah key (biasanya string) menjadi angka indeks array. Proses ini harus selalu menghasilkan angka yang sama untuk input yang sama (deterministik).

Cara Kerja Hash Function Langkah demi Langkah

Misalkan kita punya array berukuran 7 slot (indeks 0–6), dan kita ingin menyimpan key "Budi":

1. Ambil setiap karakter dari "Budi": B, u, d, i
2. Ubah setiap karakter ke nilai ASCII-nya: B=66, u=117, d=100, i=105
3. Jumlahkan semua nilai: 66 + 117 + 100 + 105 = 388
4. Modulo dengan ukuran array: 388 % 7 = 3
5. Data "Budi" disimpan di indeks 3

def hash_function_sederhana(key, ukuran_tabel):
    """
    Hash function sederhana berbasis jumlah nilai ASCII karakter.
    Mengembalikan indeks antara 0 sampai ukuran_tabel - 1.
    """
    total = 0
    for karakter in key:
        total += ord(karakter)  # ord() mengubah karakter ke nilai ASCII
    return total % ukuran_tabel


# Demonstrasi cara kerja hash function
ukuran = 7
contoh_key = ["Budi", "Sari", "Andi", "Rina", "Doni"]

print("Key        | Nilai ASCII Total | Indeks (total % 7)")
print("-" * 50)
for key in contoh_key:
    total = sum(ord(c) for c in key)
    indeks = hash_function_sederhana(key, ukuran)
    print(f"{key:<10} | {total:<17} | {indeks}")

# Output:
# Key        | Nilai ASCII Total | Indeks (total % 7)
# --------------------------------------------------
# Budi       | 388               | 3
# Sari       | 404               | 5
# Andi       | 397               | 5
# Rina       | 390               | 5
# Doni       | 404               | 5

Sifat Hash Function yang Baik

Hash function yang ideal memiliki sifat berikut:

• Deterministik: Input yang sama selalu menghasilkan output yang sama
• Distribusi merata: Data tersebar secara merata di seluruh array agar tidak menumpuk di satu slot
• Cepat: Proses hashing tidak boleh memakan waktu lama
• Meminimalkan kolisi: Semakin sedikit key yang menghasilkan indeks sama, semakin baik

# Perbandingan hash function sederhana vs yang lebih baik
def hash_sederhana(key, ukuran):
    """Hanya menjumlahkan nilai ASCII — distribusi kurang merata."""
    return sum(ord(c) for c in key) % ukuran


def hash_polynomial(key, ukuran):
    """
    Polynomial rolling hash — distribusi lebih merata.
    Mengalikan setiap karakter dengan pangkat dari bilangan prima.
    """
    PRIMA = 31
    hasil = 0
    pangkat = 1
    for karakter in key:
        hasil = (hasil + ord(karakter) * pangkat) % ukuran
        pangkat = (pangkat * PRIMA) % ukuran
    return hasil


# Bandingkan distribusi keduanya
ukuran = 10
kata_kata = ["apple", "elppa", "paple", "appel", "mango", "grape", "lemon"]

print("Key      | Hash Sederhana | Hash Polynomial")
print("-" * 45)
for kata in kata_kata:
    h1 = hash_sederhana(kata, ukuran)
    h2 = hash_polynomial(kata, ukuran)
    print(f"{kata:<8} | {h1:<14} | {h2}")

# Output:
# Key      | Hash Sederhana | Hash Polynomial
# ---------------------------------------------
# apple    | 0              | 5
# elppa    | 0              | 2
# paple    | 0              | 9
# appel    | 0              | 4
# mango    | 5              | 3
# grape    | 2              | 8
# lemon    | 9              | 0

Perhatikan bagaimana apple, elppa, paple, dan appel semuanya menghasilkan indeks 0 pada hash sederhana (karena jumlah ASCII-nya sama), sedangkan hash polynomial menyebarkannya ke indeks berbeda.

Implementasi Hash Table dari Awal

Mari kita bangun Hash Table lengkap dari nol untuk memahami cara kerjanya:

class HashTable:
    def __init__(self, ukuran=10):
        self.ukuran = ukuran
        # Membuat list berisi bucket kosong untuk menyimpan data
        self.tabel = [[] for _ in range(ukuran)]
        self.jumlah_data = 0

    def _hash_function(self, key):
        """Mengubah key menjadi indeks array menggunakan nilai ASCII."""
        total = 0
        for karakter in str(key):
            total += ord(karakter)
        return total % self.ukuran

    def simpan(self, key, value):
        """Menyimpan atau memperbarui pasangan key-value."""
        indeks = self._hash_function(key)

        # Cek apakah key sudah ada, jika ada maka update nilainya
        for i, (k, v) in enumerate(self.tabel[indeks]):
            if k == key:
                self.tabel[indeks][i] = (key, value)
                return

        # Jika key belum ada, tambahkan pasangan key-value ke bucket
        self.tabel[indeks].append((key, value))
        self.jumlah_data += 1

    def ambil(self, key):
        """Mengambil value berdasarkan key. Mengembalikan None jika tidak ada."""
        indeks = self._hash_function(key)

        for k, v in self.tabel[indeks]:
            if k == key:
                return v
        return None

    def hapus(self, key):
        """Menghapus pasangan key-value. Mengembalikan True jika berhasil."""
        indeks = self._hash_function(key)

        for i, (k, v) in enumerate(self.tabel[indeks]):
            if k == key:
                del self.tabel[indeks][i]
                self.jumlah_data -= 1
                return True
        return False

    def tampilkan(self):
        """Menampilkan isi Hash Table."""
        for i, bucket in enumerate(self.tabel):
            if bucket:
                print(f"  Slot [{i}]: {bucket}")


# Contoh penggunaan lengkap
print("=== Demo Hash Table ===")
ht = HashTable(ukuran=10)

ht.simpan("nama", "Budi Santoso")
ht.simpan("kota", "Jakarta")
ht.simpan("umur", 25)
ht.simpan("pekerjaan", "Software Engineer")

print("\nIsi Hash Table:")
ht.tampilkan()

print(f"\nAmbil 'nama'     : {ht.ambil('nama')}")
print(f"Ambil 'kota'     : {ht.ambil('kota')}")
print(f"Ambil 'hobi'     : {ht.ambil('hobi')}")

# Update nilai
ht.simpan("kota", "Bandung")
print(f"\nSetelah update, 'kota': {ht.ambil('kota')}")

# Hapus data
ht.hapus("umur")
print(f"Setelah hapus, 'umur': {ht.ambil('umur')}")

# Output:
# === Demo Hash Table ===
#
# Isi Hash Table:
#   Slot [2]: [('pekerjaan', 'Software Engineer')]
#   Slot [3]: [('nama', 'Budi Santoso')]
#   Slot [5]: [('kota', 'Jakarta')]
#   Slot [7]: [('umur', 25)]
#
# Ambil 'nama'     : Budi Santoso
# Ambil 'kota'     : Jakarta
# Ambil 'hobi'     : None
#
# Setelah update, 'kota': Bandung
# Setelah hapus, 'umur': None

Menangani Kolisi (Collision Handling)

Kolisi terjadi ketika dua key yang berbeda menghasilkan indeks yang sama dari hash function. Ini adalah kejadian normal — ibarat memiliki 1000 nama tapi hanya 100 slot loker, pasti ada yang perlu berbagi tempat.

Dari contoh sebelumnya, kita lihat bahwa "Sari", "Andi", "Rina", dan "Doni" semuanya menghasilkan indeks yang sama. Inilah yang disebut kolisi.

Ada dua teknik utama untuk menangani kolisi:

1. Chaining (Rantai)

Setiap slot array menyimpan sebuah linked list atau list. Jika terjadi kolisi, data baru ditambahkan ke list yang sudah ada di slot tersebut.

class HashTableChaining:
    def __init__(self, ukuran=7):
        self.ukuran = ukuran
        # Setiap slot adalah list yang bisa menampung banyak pasangan key-value
        self.tabel = [[] for _ in range(ukuran)]

    def _hash(self, key):
        return sum(ord(c) for c in key) % self.ukuran

    def set(self, key, value):
        indeks = self._hash(key)
        bucket = self.tabel[indeks]

        # Jika key sudah ada, update valuenya
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return

        # Tambahkan pasangan baru ke bucket yang sama (chaining)
        bucket.append((key, value))

    def get(self, key):
        indeks = self._hash(key)
        bucket = self.tabel[indeks]

        for k, v in bucket:
            if k == key:
                return v
        return None

    def tampilkan_detail(self):
        """Menampilkan isi setiap slot, termasuk slot dengan kolisi."""
        print(f"Hash Table (ukuran={self.ukuran}):")
        for i, bucket in enumerate(self.tabel):
            if bucket:
                kolisi = "  <-- KOLISI!" if len(bucket) > 1 else ""
                print(f"  Slot [{i}]: {bucket}{kolisi}")
            else:
                print(f"  Slot [{i}]: (kosong)")


# Demonstrasi kolisi dengan Chaining
print("=== Demo Chaining ===")
ht = HashTableChaining(ukuran=7)

# "apple" dan "elppa" memiliki karakter yang sama, jumlah ASCII-nya sama
ht.set("Sari", "Data Sari")
ht.set("Andi", "Data Andi")   # Akan kolisi dengan "Sari"
ht.set("Rina", "Data Rina")   # Akan kolisi juga
ht.set("Budi", "Data Budi")

print("\nSetelah insert 4 data:")
ht.tampilkan_detail()

print(f"\nAmbil 'Sari': {ht.get('Sari')}")
print(f"Ambil 'Andi': {ht.get('Andi')}")
print(f"Ambil 'Rina': {ht.get('Rina')}")

# Output:
# === Demo Chaining ===
#
# Setelah insert 4 data:
# Hash Table (ukuran=7):
#   Slot [0]: (kosong)
#   Slot [1]: (kosong)
#   Slot [2]: (kosong)
#   Slot [3]: [('Budi', 'Data Budi')]
#   Slot [4]: (kosong)
#   Slot [5]: [('Sari', 'Data Sari'), ('Andi', 'Data Andi'), ('Rina', 'Data Rina')]  <-- KOLISI!
#   Slot [6]: (kosong)
#
# Ambil 'Sari': Data Sari
# Ambil 'Andi': Data Andi
# Ambil 'Rina': Data Rina

2. Open Addressing — Linear Probing

Jika slot sudah terisi, cari slot kosong berikutnya secara berurutan sampai menemukan slot yang kosong.

class HashTableOpenAddressing:
    DELETED = "<DELETED>"  # Penanda untuk slot yang sudah dihapus

    def __init__(self, ukuran=10):
        self.ukuran = ukuran
        self.kunci = [None] * ukuran
        self.nilai = [None] * ukuran
        self.jumlah = 0

    def _hash(self, key):
        return sum(ord(c) for c in str(key)) % self.ukuran

    def set(self, key, value):
        if self.jumlah >= self.ukuran:
            print("Hash table penuh!")
            return

        indeks = self._hash(key)
        indeks_awal = indeks

        while self.kunci[indeks] is not None and self.kunci[indeks] != self.DELETED:
            if self.kunci[indeks] == key:
                # Key sudah ada, update valuenya
                self.nilai[indeks] = value
                return

            # Geser ke slot berikutnya (linear probing)
            indeks = (indeks + 1) % self.ukuran

            if indeks == indeks_awal:
                print("Hash table penuh!")
                return

        # Simpan di slot kosong yang ditemukan
        if self.kunci[indeks] is None:
            self.jumlah += 1
        self.kunci[indeks] = key
        self.nilai[indeks] = value

    def get(self, key):
        indeks = self._hash(key)
        indeks_awal = indeks

        while self.kunci[indeks] is not None:
            if self.kunci[indeks] == key:
                return self.nilai[indeks]

            indeks = (indeks + 1) % self.ukuran
            if indeks == indeks_awal:
                break

        return None

    def tampilkan_detail(self):
        print(f"Hash Table Open Addressing (ukuran={self.ukuran}):")
        for i in range(self.ukuran):
            if self.kunci[i] is not None:
                print(f"  Slot [{i}]: key='{self.kunci[i]}', value='{self.nilai[i]}'")
            else:
                print(f"  Slot [{i}]: (kosong)")


# Demonstrasi Linear Probing
print("=== Demo Open Addressing (Linear Probing) ===")
ht = HashTableOpenAddressing(ukuran=7)

# Masukkan data — beberapa akan mengalami probing karena kolisi
ht.set("Sari", "Data Sari")    # Hash -> slot 5
ht.set("Andi", "Data Andi")    # Hash -> slot 5 (penuh), geser ke slot 6
ht.set("Rina", "Data Rina")    # Hash -> slot 5 (penuh), 6 (penuh), geser ke slot 0
ht.set("Budi", "Data Budi")    # Hash -> slot 3

print("\nSetelah insert 4 data (perhatikan posisi slot):")
ht.tampilkan_detail()

print(f"\nAmbil 'Sari': {ht.get('Sari')}")
print(f"Ambil 'Rina': {ht.get('Rina')}")
print(f"Ambil 'Doni': {ht.get('Doni')}")

# Output:
# === Demo Open Addressing (Linear Probing) ===
#
# Setelah insert 4 data (perhatikan posisi slot):
# Hash Table Open Addressing (ukuran=7):
#   Slot [0]: key='Rina', value='Data Rina'
#   Slot [1]: (kosong)
#   Slot [2]: (kosong)
#   Slot [3]: key='Budi', value='Data Budi'
#   Slot [4]: (kosong)
#   Slot [5]: key='Sari', value='Data Sari'
#   Slot [6]: key='Andi', value='Data Andi'
#
# Ambil 'Sari': Data Sari
# Ambil 'Rina': Data Rina
# Ambil 'Doni': None

Perbandingan Chaining vs Open Addressing

Contoh Kasus Nyata

Hash Table digunakan di hampir semua aplikasi modern. Berikut beberapa contoh yang dekat dengan kehidupan sehari-hari:

1. Sistem Login Pengguna

database_user = {}


def daftar_user(username, email, password):
    if username in database_user:
        return "Username sudah digunakan!"

    database_user[username] = {
        "email": email,
        "password": hash(password),  # Simpan dalam bentuk hash
        "aktif": True
    }
    return f"Akun '{username}' berhasil dibuat"


def login(username, password):
    if username not in database_user:
        return "Username tidak ditemukan"

    user = database_user[username]
    if user["password"] == hash(password):
        return f"Selamat datang, {username}!"
    return "Password salah"


print(daftar_user("budi123", "budi@email.com", "rahasia123"))
print(login("budi123", "rahasia123"))
print(login("budi123", "passwordsalah"))
print(login("tidakada", "apapun"))

# Output:
# Akun 'budi123' berhasil dibuat
# Selamat datang, budi123!
# Password salah
# Username tidak ditemukan

2. Cache Data (Menghindari Query Berulang)

Jika ingin membangun aplikasi seperti Tokopedia, caching dengan Hash Table sangat berguna untuk menyimpan data yang sering diakses agar tidak perlu query ke database berulang kali.

class SimpleCache:
    def __init__(self):
        self._cache = {}

    def get(self, key):
        if key in self._cache:
            print(f"[CACHE HIT] Data '{key}' diambil dari cache")
            return self._cache[key]
        return None

    def set(self, key, value):
        self._cache[key] = value
        print(f"[CACHE SET] Data '{key}' disimpan ke cache")


def ambil_produk(product_id, cache):
    data = cache.get(product_id)
    if data is not None:
        return data

    print(f"[DB QUERY] Mengambil produk {product_id} dari database...")
    data = {"id": product_id, "nama": "Sepatu Nike", "harga": 850000}
    cache.set(product_id, data)
    return data


cache = SimpleCache()

produk1 = ambil_produk("P001", cache)
print(produk1)

produk2 = ambil_produk("P001", cache)  # Kali ini dari cache
print(produk2)

# Output:
# [DB QUERY] Mengambil produk P001 dari database...
# [CACHE SET] Data 'P001' disimpan ke cache
# {'id': 'P001', 'nama': 'Sepatu Nike', 'harga': 850000}
# [CACHE HIT] Data 'P001' diambil dari cache
# {'id': 'P001', 'nama': 'Sepatu Nike', 'harga': 850000}

3. Penghitungan Frekuensi Kata

def hitung_frekuensi_kata(teks):
    frekuensi = {}
    for kata in teks.lower().split():
        frekuensi[kata] = frekuensi.get(kata, 0) + 1
    return frekuensi


paragraf = "belajar python itu mudah belajar struktur data itu penting python sangat populer"
hasil = hitung_frekuensi_kata(paragraf)

# Tampilkan diurutkan dari yang paling sering muncul
for kata, jumlah in sorted(hasil.items(), key=lambda x: x[1], reverse=True):
    print(f"  '{kata}': {jumlah}x")

# Output:
#   'belajar': 2x
#   'itu': 2x
#   'python': 2x
#   'mudah': 1x
#   'struktur': 1x
#   'data': 1x
#   'penting': 1x
#   'sangat': 1x
#   'populer': 1x

Kompleksitas Waktu Hash Table

Kasus terburuk O(n) terjadi saat semua key menghasilkan indeks yang sama (seluruh data masuk ke satu bucket). Hash function yang baik membuat kasus ini sangat jarang terjadi.

Lihat juga artikel Linked List: Struktur Data Berantai untuk memahami struktur yang sering digunakan dalam implementasi Chaining.

Pertanyaan yang Sering Diajukan

Apa itu Hash Table dalam bahasa sederhana?

Hash Table adalah struktur data yang menyimpan data dalam pasangan key-value, mirip seperti kamus atau buku telepon. Kamu menyebutkan “nama” (key), dan Hash Table langsung memberikan “nomor telepon” (value) tanpa perlu mencari satu per satu. Kecepatannya hampir selalu konstan, tidak peduli berapa banyak data yang disimpan.

Bagaimana cara kerja Hash Function secara detail?

Hash Function mengambil sebuah key (misalnya string "Budi") dan mengubahnya menjadi angka indeks melalui operasi matematika — biasanya dengan menjumlahkan nilai ASCII setiap karakter, lalu menggunakan modulo terhadap ukuran array. Proses ini selalu menghasilkan angka yang sama untuk input yang sama, sehingga kita selalu tahu di mana data tersimpan. Kualitas Hash Function sangat menentukan performa Hash Table secara keseluruhan, terutama seberapa merata data tersebar.

Apa perbedaan Hash Table dengan Array biasa?

Array menyimpan data berdasarkan indeks numerik (0, 1, 2, …) sehingga kamu harus tahu posisi datanya atau melakukan pencarian linear O(n). Hash Table menggunakan key yang lebih bermakna (seperti "username" atau "email") dan secara otomatis menentukan posisi penyimpanannya dengan kecepatan O(1). Array lebih cocok untuk data berurutan, sedangkan Hash Table lebih cocok untuk pencarian data berdasarkan identifikasi tertentu.

Mengapa kolisi bisa terjadi dan bagaimana cara mengatasinya?

Kolisi terjadi karena Hash Function mengubah input yang tidak terbatas menjadi angka dalam rentang terbatas (ukuran array) — ibarat memiliki 1000 nama tapi hanya 100 slot loker, pasti ada yang berbagi. Kolisi tidak berbahaya asalkan ditangani dengan benar. Dua teknik utama: Chaining (setiap slot menyimpan list, semua data kolisi dirantai di sini) dan Open Addressing (jika slot penuh, cari slot kosong berikutnya secara berurutan). Hash Table yang baik dirancang untuk meminimalkan kolisi dan tetap efisien meski ada kolisi.

Kapan sebaiknya menggunakan Hash Table dibanding struktur data lain?

Gunakan Hash Table ketika kamu sering melakukan pencarian, penyisipan, atau penghapusan data berdasarkan sebuah key — misalnya sistem cache, database in-memory, atau penghitungan frekuensi. Jika kamu butuh data yang terurut atau perlu melakukan operasi range query (misalnya “semua data antara nilai A dan B”), struktur data seperti Binary Search Tree atau Sorted Array lebih cocok. Di Python, dict dan set adalah implementasi Hash Table yang sudah dioptimalkan dan siap digunakan.

Kesimpulan

Hash Table adalah salah satu struktur data paling powerful yang wajib dikuasai setiap developer. Dengan kemampuan pencarian O(1), Hash Table memungkinkan aplikasi untuk mengelola data dalam jumlah besar dengan sangat efisien.

Poin-poin utama yang perlu diingat:

• Hash Table menyimpan data sebagai pasangan key-value
• Hash Function mengubah key menjadi angka indeks array melalui operasi matematika
• Kolisi adalah hal normal — terjadi saat dua key menghasilkan indeks yang sama
• Kolisi ditangani dengan Chaining (list per slot) atau Open Addressing (probing ke slot berikutnya)
• Di Python, dict adalah implementasi Hash Table yang sudah dioptimalkan
• Digunakan untuk: cache, sistem login, penghitungan frekuensi, dan masih banyak lagi

Langkah selanjutnya: coba implementasikan Hash Table sederhana dari awal menggunakan Python, kemudian eksplorasi bagaimana Python dict bekerja di balik layar. Semakin kamu memahami struktur data ini, semakin mudah kamu merancang solusi yang efisien untuk masalah nyata.