Tabel Hash — Cara Kerja Hashing & Penanganan Tabrakan

Tabel hash menyimpan pasangan kunci-nilai dengan melakukan hashing pada setiap kunci ke sebuah indeks array. Ini memungkinkan tabel langsung menuju lokasi yang mendekati posisi yang benar, alih-alih memeriksa setiap item yang tersimpan satu per satu.

Itulah sebabnya tabel hash sering kali mendekati $O(1)$ untuk pencarian, penyisipan, dan penghapusan secara rata-rata. Syaratnya penting: fungsi hash harus menyebarkan kunci dengan cukup baik, dan tabel tetap memerlukan aturan untuk menangani tabrakan.

Apa yang Dilakukan Tabel Hash

Tabel hash menyimpan pasangan kunci-nilai seperti "name" -> "Ada" atau 42 -> "blue". Tabel ini memiliki dua bagian utama:

• sebuah array slot atau bucket
• sebuah fungsi hash yang memetakan setiap kunci ke salah satu slot tersebut

Jika array memiliki $m$ slot, Anda bisa membayangkan fungsi hash menghasilkan indeks dari $0$ sampai $m-1$.

Untuk contoh bilangan bulat kecil, aturannya bisa berupa

$$h(k) = k \bmod 8$$

Maka kunci $10$ masuk ke slot $2$ karena $10 \bmod 8 = 2$.

Fungsi hash nyata dirancang dengan lebih hati-hati, terutama untuk string dan himpunan data yang lebih besar. Namun gagasan intinya tetap sama: hitung sebuah indeks dengan cepat, lalu periksa item yang disimpan di sana.

Mengapa Tabrakan Hash Tidak Bisa Dihindari

Tabrakan terjadi ketika dua kunci yang berbeda dipetakan ke slot yang sama.

Ini hal yang normal karena tabel biasanya memiliki lebih sedikit slot daripada jumlah kemungkinan kunci. Dengan

$$h(k) = k \bmod 8$$

kunci $10$, $18$, dan $26$ semuanya dipetakan ke slot $2$. Jadi meskipun fungsi bekerja persis seperti yang didefinisikan, tabel tetap memiliki konflik yang harus diselesaikan.

Jadi tabel hash tidak menjanjikan slot yang unik untuk setiap kunci. Yang dijanjikan adalah cara cepat untuk mempersempit pencarian, asalkan tabrakan ditangani dengan baik.

Contoh Langkah demi Langkah: Satu Tabel, Satu Tabrakan

Misalkan sebuah tabel memiliki $8$ slot dan menggunakan

$$h(k) = k \bmod 8$$

Masukkan kunci $10$, $18$, dan $7$.

Pertama, $10$ masuk ke slot $2$ karena $10 \bmod 8 = 2$.

Berikutnya, $18$ juga di-hash ke slot $2$, sehingga terjadi tabrakan.

Lalu $7$ masuk ke slot $7$, jadi penyisipan itu tidak mengalami tabrakan.

Pola yang berguna selalu sama:

1. Hash kuncinya.
2. Pergi ke slot yang disarankan.
3. Jika kunci yang berbeda sudah ada di sana, terapkan aturan tabrakan.

Setelah pola itu jelas, dua strategi utama penanganan tabrakan akan lebih mudah dipahami.

Chaining Vs. Open Addressing

Chaining menyimpan bucket di setiap slot

Dalam chaining, setiap slot menyimpan kumpulan kecil entri, bukan hanya satu.

Jika $10$ dan $18$ sama-sama di-hash ke slot $2$, bucket $2$ mungkin menyimpan

• $(10, \text{value}_1)$
• $(18, \text{value}_2)$

Untuk mencari kunci $18$, tabel langsung menuju bucket $2$ dan membandingkan hanya entri yang ada di bucket tersebut.

Chaining secara konsep sederhana, dan penghapusan biasanya lebih mudah daripada pada open addressing. Konsekuensinya, bucket yang panjang membuat operasi menjadi lebih lambat.

Open addressing tetap berada di dalam array

Dalam open addressing, setiap slot array menampung paling banyak satu entri. Jika slot asal penuh, tabel akan memeriksa slot lain menurut aturan tetap.

Salah satu aturan yang umum adalah linear probing: jika slot $2$ terisi, coba $3$, lalu $4$, lalu $5$, dan kembali ke awal jika diperlukan.

Ini menghindari daftar bucket terpisah, tetapi slot-slot penuh yang berdekatan dapat membentuk cluster. Detail lain adalah pencarian dan penghapusan harus mengikuti aturan probing yang sama seperti saat penyisipan.

Kapan Klaim $O(1)$ Itu Masuk Akal

Tabel hash sering dijelaskan memiliki pencarian, penyisipan, dan penghapusan $O(1)$ secara rata-rata. Pernyataan kasus rata-rata itu bergantung pada beberapa syarat:

• fungsi hash menyebarkan kunci dengan cukup baik
• load factor tetap terkendali
• strategi penanganan tabrakan diimplementasikan dengan benar

Load factor adalah rasio

$$\text{load factor} = \frac{\text{number of stored entries}}{\text{number of slots}}$$

Jika tabel menjadi terlalu penuh, tabrakan menjadi lebih sering, dan performa memburuk. Itulah sebabnya banyak implementasi mengubah ukuran array saat mulai terisi.

Performa kasus terburuk tetap bisa menurun mendekati $O(n)$ jika terlalu banyak kunci menumpuk di area yang sama.

Kesalahan Umum pada Tabel Hash

Menganggap tabrakan berarti fungsi hash gagal

Tidak. Tabrakan memang diharapkan. Pertanyaan yang sebenarnya adalah apakah tabel menanganinya secara efisien.

Menganggap $O(1)$ berlaku tanpa syarat

$O(1)$ biasanya adalah pernyataan kasus rata-rata, bukan janji untuk setiap input dan setiap saat.

Mencampuradukkan hashing di sini dengan enkripsi

Fungsi hash dalam konteks struktur data dasar terutama digunakan untuk pengindeksan cepat, bukan kerahasiaan. Keduanya memiliki tujuan yang berbeda.

Lupa membandingkan kunci yang sebenarnya

Dua kunci bisa memiliki hasil hash yang sama. Setelah sampai di bucket atau posisi probe yang tepat, tabel tetap harus memeriksa apakah kuncinya benar-benar cocok.

Kapan Tabel Hash Digunakan

Tabel hash digunakan ketika pencarian cepat berdasarkan kunci itu penting. Contoh umum meliputi dictionary, symbol table, cache, indexing, dan menghitung frekuensi dalam data.

Struktur ini sangat cocok ketika pencarian tepat berdasarkan kunci lebih penting daripada menjaga item tetap dalam urutan terurut. Jika Anda memerlukan penelusuran berurutan, range query, atau nilai terdekat, struktur lain mungkin lebih baik.

Coba Contoh Tabrakan yang Mirip

Ambil array kecil dengan $8$ slot dan gunakan $h(k)=k \bmod 8$. Masukkan beberapa kunci seperti $3$, $11$, $19$, dan $27$. Lalu selesaikan tabrakan sekali dengan chaining dan sekali dengan linear probing.

Satu latihan itu membuat gagasan utamanya cepat menjadi konkret: tabrakan tidak bisa dihindari, dan aturan tabrakan mengubah cara tabel berperilaku. Jika Anda ingin langkah lanjutan yang berguna, coba versi Anda sendiri dengan ukuran tabel yang berbeda dan lihat bagaimana tabrakannya berubah.