Konsep tabel hash

Tabel hash adalah struktur data yang menyimpan pasangan kunci-nilai dan menyelesaikan pembacaan, penulisan, serta penghapusan dalam waktu rata-rata $O(1)$. Topik ini membedah mekanisme di balik kecepatan tersebut, mulai dari cara kunci diubah menjadi indeks array, peran bucket sebagai wadah penyimpanan, sampai dua teknik penanganan tabrakan (collision). Materi yang sama langsung dipraktikkan dengan membangun tabel hash mini dari nol, lengkap dengan operasi put, get, dan delete beserta keluaran aslinya.

Dari kunci ke indeks#

Fungsi hash (hash function) adalah fungsi yang mengubah kunci apa pun, baik string maupun angka, menjadi bilangan bulat dengan aturan yang tetap. Bilangan itu lalu ditekuk ke rentang indeks array lewat operasi modulo, sehingga bentuk umumnya ditulis hash(kunci) % m dengan $m$ banyaknya slot tabel. Dari rumus itu terlihat mengapa indeks tidak pernah keluar dari rentang array, dan kunci yang sama selalu menghasilkan indeks yang sama. Pencarian pun tidak perlu menelusuri isi tabel, cukup satu perhitungan untuk tahu ke mana sebuah kunci pergi.

Slot yang dituju hasil perhitungan itu disebut bucket, yakni wadah tempat pasangan kunci-nilai disimpan pada satu indeks. Diagram berikut mengikuti kunci “na” yang diolah fungsi hash buatan, yaitu penjumlahan kode karakter tiap huruf lalu modulo 8. Sisa operasi modulo itu, angka 7, menunjuk satu bucket di antara delapan slot yang tersedia.

Fungsi hash pada diagram sengaja dibuat sederhana agar setiap langkahnya bisa dihitung dengan tangan. Fungsi hash bawaan seperti hash() pada Python atau hashCode() pada Java jauh lebih rumit, tetapi prinsip yang sama tetap berlaku, kunci yang sama selalu menghasilkan nilai yang sama. Kualitas sebuah fungsi hash dinilai dari meratanya sebaran hasil, karena kunci yang menumpuk di sedikit indeks akan memanjangkan rantai dan mengikis keunggulan $O(1)$.

Chaining menampung tabrakan#

Dua kunci yang berbeda kadang menghasilkan indeks yang sama, kejadian ini disebut tabrakan dan tidak mungkin dihindari sepenuhnya. Ruang kunci jauh lebih besar daripada banyaknya slot, misalnya jutaan string kemungkinan harus muat ke delapan slot, sehingga tabrakan pasti terjadi menurut prinsip sarang merpati. Teknik penanganan pertama adalah chaining, yaitu setiap bucket berisi list yang dapat menampung lebih dari satu pasangan sekaligus. Operasi get menjadi dua langkah, menghitung indeks lalu menelusuri list pendek di dalam bucket sambil membandingkan kunci yang sesungguhnya.

Implementasi berikut membangun tabel hash mini dengan chaining dari nol. Fungsi hash_buatan menghitung jumlah kode karakter modulo 8, sedangkan setiap bucket diwujudkan sebagai list tuple kunci-nilai. Dua kunci sengaja dipilih untuk bertabrakan, yaitu “an” dan “na”, karena penjumlahan kode karakter keduanya sama dengan 207.

"""Tabel hash mini dengan chaining, dibangun dari nol."""


def hash_buatan(kunci, m):
    """Fungsi hash sederhana: jumlah kode karakter modulo m."""
    total = 0
    for karakter in kunci:
        total += ord(karakter)
    return total % m


class TabelHashMini:
    def __init__(self, m=8):
        self.m = m
        self.bucket = [[] for _ in range(m)]

    def _indeks(self, kunci):
        return hash_buatan(kunci, self.m)

    def put(self, kunci, nilai):
        daftar = self.bucket[self._indeks(kunci)]
        for i, (k, _) in enumerate(daftar):
            if k == kunci:             # kunci sudah ada, nilai lamanya diganti
                daftar[i] = (kunci, nilai)
                return
        daftar.append((kunci, nilai))  # kunci baru, tambahkan di ujung rantai

    def get(self, kunci):
        for k, v in self.bucket[self._indeks(kunci)]:
            if k == kunci:
                return v
        return None

    def delete(self, kunci):
        daftar = self.bucket[self._indeks(kunci)]
        for i, (k, _) in enumerate(daftar):
            if k == kunci:
                daftar.pop(i)
                return True
        return False


# dua kunci sengaja ditabrakkan, penjumlahan kode karakternya sama
print("hash('an')  :", hash_buatan("an", 8))
print("hash('na')  :", hash_buatan("na", 8))

tabel = TabelHashMini(m=8)
tabel.put("an", "angka")
tabel.put("na", "nama")
tabel.put("api", "unggun")

print("get('an')   :", tabel.get("an"))
print("get('na')   :", tabel.get("na"))
print("get('oli')  :", tabel.get("oli"))
print("bucket 7    :", tabel.bucket[7])
print("bucket 2    :", tabel.bucket[2])

print("put('na') diganti nilainya")
tabel.put("na", "nomor")
print("get('na')   :", tabel.get("na"))

print("delete('an'):", tabel.delete("an"))
print("bucket 7    :", tabel.bucket[7])
print("delete('an'):", tabel.delete("an"))

hash('an')  : 7
hash('na')  : 7
get('an')   : angka
get('na')   : nama
get('oli')  : None
bucket 7    : [('an', 'angka'), ('na', 'nama')]
bucket 2    : [('api', 'unggun')]
put('na') diganti nilainya
get('na')   : nomor
delete('an'): True
bucket 7    : [('na', 'nomor')]
delete('an'): False

Pada keluaran, “an” dan “na” memang mendarat di indeks yang sama dan hidup berdampingan dalam satu bucket, terlihat dari isi bucket 7 yang memuat dua pasangan. Pembacaan tetap benar karena perbandingan kunci dilakukan setelah indeks ditemukan, sehingga get("na") tidak tertukar dengan get("an"). Operasi put pada kunci yang sudah ada mengganti nilai lamanya tanpa menambah butir baru, sedangkan delete menghapus satu pasangan dari rantai dan mengembalikan False ketika kuncinya tidak ditemukan. Selama rantai tetap pendek, ketiga operasi itu selesai dalam waktu mendekati $O(1)$.

Open addressing, alternatif tanpa list#

Teknik penanganan kedua adalah open addressing, yaitu semua pasangan disimpan langsung di dalam array tabel tanpa list tambahan. Ketika slot tujuan sudah terisi, kunci baru dicarikan slot lain mengikuti aturan tetap, misalnya bergeser satu tempat ke kanan sampai slot kosong ditemukan, teknik yang disebut linear probing. Pencarian mengikuti jejak yang sama, mulai dari indeks hasil hash lalu menyusuri slot berikutnya sampai kunci ditemukan atau bertemu slot kosong. Konsekuensinya, penghapusan tidak boleh sekadar mengosongkan slot, karena slot kosong di tengah jejak akan memutus pencarian kunci lain yang melompatinya.

Kedua teknik punya kelebihan yang saling bertolak belakang, sebagaimana dirangkum tabel berikut.

Dict Python memakai open addressing, sedangkan implementasi klasik di banyak buku memakai chaining karena lebih mudah diikuti. Pilihan chaining itulah yang diadopsi tabel hash mini pada topik ini, sebab rantai yang terlihat memudahkan pembacaan mekanismenya. Bagaimanapun bentuknya, kedua teknik sama-sama mengandalkan fungsi hash yang merata supaya jejak pencariannya tetap pendek.

Load factor dan resize#

Rasio antara banyaknya pasangan dan banyaknya slot disebut load factor, dihitung dengan $n/m$ untuk $n$ pasangan dan $m$ slot. Pada tabel berisi 12 pasangan dengan 16 slot, load factor-nya $12/16 = 0{,}75$, artinya rata-rata satu bucket hanya menampung 0,75 pasangan. Semakin tinggi nilainya, semakin panjang rantai atau jejak pencariannya, sehingga waktu operasi merayap dari $O(1)$ menuju $O(n)$. Karena itu implementasi nyata menetapkan ambang, misalnya 0,75 pada HashMap Java. Resize, yakni pembesaran tabel, dipicu begitu ambang itu terlampaui.

Resize membuat array baru yang lebih besar, umumnya dua kali lipat, lalu seluruh kunci lama dihitung ulang dengan fungsi hash untuk mengisi array baru. Perhitungan ulang itu wajib karena indeks bergantung pada $m$, sehingga kunci yang tadinya menumpuk di indeks 7 bisa tersebar setelah tabel membesar. Biaya satu kali resize adalah $O(n)$, tetapi karena dilakukan jarang dan kapasitas melipat ganda setiap kali, rata-rata biaya per operasi tetap $O(1)$, pola amortisasi yang sama dengan pertumbuhan array dinamis. Inilah alasan tabel hash mempertahankan janji kecepatannya meskipun isinya terus bertambah.

Kesalahan umum#

1. Mengira tabrakan adalah tanda kode yang salah. Tabrakan adalah konsekuensi normal dari pemetaan ruang kunci yang jauh lebih besar daripada jumlah slotnya. Struktur tetap benar selama rantai atau jejak probing ditangani dengan disiplin, dan kinerjanya tinggal dijaga lewat load factor.
2. Menyimpan nilai hash() Python untuk dipakai lintas eksekusi. Python mengacak seed, benih yang menentukan hasil hash, setiap kali program dijalankan, sehingga nilai hash string berubah antar eksekusi dan data yang menyimpannya menjadi tidak konsisten. Gunakan fungsi hash sendiri yang deterministik, seperti penjumlahan kode karakter pada demo, bila nilai hashnya perlu dicatat.
3. Membangun tabel sendiri tanpa resize. Tabel mini yang terus diisi tanpa pembesaran akan menumpuk pasangan di bucket yang sama. Pantau rasio $n/m$ dan besarkan tabel mengikuti ambang yang dipilih agar operasi tidak melorot ke $O(n)$.

Ringkasan#

• Fungsi hash mengubah kunci menjadi indeks lewat hash(kunci) % m, dan bucket menampung pasangan kunci-nilai pada indeks tersebut.
• Tabrakan ditangani dengan chaining, yaitu list per bucket, atau open addressing, yaitu pencarian slot lain, dengan kelebihan dan biaya yang berbeda.
• Load factor $n/m$ mengukur kepadatan tabel, dan resize dengan perhitungan ulang seluruh kunci menjaga rata-rata operasi tetap $O(1)$.
• Tabel hash mini dengan chaining hanya butuh fungsi hash, array bucket, dan perbandingan kunci untuk bekerja dengan benar.

Referensi#

• Hash table — Wikipedia — gambaran lengkap chaining, open addressing, load factor, dan resize.
• Hash function — Wikipedia — sifat fungsi hash dan contoh pembagian modulo pada tabel.
• VisuAlgo — visualisasi interaktif tabel hash untuk melihat bucket dan tabrakannya secara langsung.