Collision Resolution

Setiap hash function praktis pasti menghasilkan collision — dua key berbeda yang terpetakan ke bucket yang sama. Ini bukan kelemahan, melainkan konsekuensi matematis dari pigeonhole principle: ruang key jauh lebih besar daripada jumlah bucket. Tanpa strategi penanganan, hash table hanya berfungsi penuh ketika diisi sangat sedikit, yang membuang memori. Pada Chapter ini kita akan membedah dua keluarga strategi utama: separate chaining yang menampung collision di luar array, dan open addressing yang mencari bucket alternatif di dalam array itu sendiri. Pemahaman trade-off keduanya penting sebelum kita memilih salah satu untuk implementasi konkret di chapter berikutnya.

Mengapa Collision Terjadi #

Aturan: Pigeonhole Principle #

Jika jumlah kemungkinan key |K| lebih besar dari jumlah bucket m, maka paling sedikit dua key berbeda pasti terpetakan ke bucket yang sama:

text

|K| > m  =>  pasti ada k1 != k2 dengan h(k1) == h(k2)

Untuk hash table int dengan m = 7, ruang key adalah 2^32 (4 miliar) tetapi hanya 7 bucket tersedia — collision tak terhindarkan.

Mekanisme: Birthday Paradox #

Intuisi salah: “Saya hanya insert 10 elemen ke tabel 1000 bucket, collision mustahil terjadi.” Realitas berbeda karena birthday paradox: peluang collision mencapai 50% ketika jumlah insert mendekati sqrt(m).

Jumlah bucket `m`	Threshold 50% collision	Threshold 1% collision
100	~12	~2
1.000	~37	~4
10.000	~118	~13
1.000.000	~1.177	~132

Bahkan dengan m = 1.000.000, hanya sekitar 1.177 insert acak diperlukan untuk peluang collision 50%. Inilah mengapa strategi collision resolution adalah komponen wajib setiap hash table.

Dua Keluarga Strategi #

Separate Chaining #

Setiap bucket berisi sebuah wadah sekunder (linked list, vector, atau tree) yang menampung semua entry dengan hash yang sama. Insert selalu mungkin (cukup tambahkan ke wadah), pencarian me-loop di dalam wadah.

flowchart TD A["Hash Table bucket[0..m-1]"] --> B0["bucket 0 -> (k1,v1) -> (k2,v2)"] A --> B1["bucket 1 (kosong)"] A --> B2["bucket 2 -> (k3,v3)"] A --> B3["bucket 3 -> (k4,v4) -> (k5,v5) -> (k6,v6)"]

Open Addressing #

Semua entry disimpan langsung di dalam array. Jika bucket h(k) terisi key lain, lakukan probing untuk mencari bucket alternatif berdasarkan rumus h(k, i) dengan i = 0, 1, 2, ... hingga menemukan bucket kosong.

flowchart LR K["Insert k"] --> H0["i=0: h(k,0)"] H0 -- terisi --> H1["i=1: h(k,1)"] H1 -- terisi --> H2["i=2: h(k,2)"] H2 -- kosong --> OK["simpan k di sini"] H0 -- kosong --> OK H1 -- kosong --> OK

Perbandingan Strategi #

Aspek	Separate Chaining	Open Addressing
Struktur bucket	Linked list / vector per bucket	Array datar tanpa wadah sekunder
Load factor α	Boleh > 1 (jarang diinginkan)	Wajib < 1 (umumnya α ≤ 0.75)
Resolusi collision	Tambah ke wadah (selalu berhasil bila memori cukup)	Probing sampai ketemu slot kosong
Performa cache	Buruk (pointer chasing)	Baik (data kontigu)
Traversal bucket collision	O(panjang rantai)	O(jumlah probe)
Deletion	Mudah (hapus node)	Sulit (butuh tombstone)
Memori overhead	Tinggi (pointer per entry)	Rendah (hanya array)
Sensitif terhadap hash lemah	Cukup toleran	Sangat sensitif (clustering)

Variasi Open Addressing #

Open addressing dibedakan berdasarkan rumus probing h(k, i):

Metode	Rumus	Kelebihan	Kekurangan
Linear probing	`(h'(k) + i) mod m`	Cache-friendly, sederhana	Primary clustering
Quadratic probing	`(h'(k) + c1i + c2i^2) mod m`	Mengurangi primary cluster	Secondary clustering
Double hashing	`(h1(k) + i*h2(k)) mod m`	Hampir tak ada cluster	Lebih lambat (2 hash)

Primary clustering: linear probing cenderung membentuk blok panjang bucket terisi. Setiap insert baru ke wilayah blok memperpanjang blok.
Secondary clustering: quadratic probing tetap menghasilkan rangkaian probe yang sama untuk semua key dengan h'(k) sama, terbentuk blok “bertahap”.

Variasi Separate Chaining #

Implementasi chaining dapat bervariasi pada wadah sekunder:

Linked list: paling tradisional, overhead pointer per entry.
Dynamic array (vector): lebih cache-friendly, tetapi reallocation per bucket bisa mahal.
BST / skip list: panjang rantai dikelola O(log n). STL tidak memakai ini; Map-only.
Move-to-front heuristic: setiap lookup yang berhasil memindahkan entry ke depan list — exploitasi lokalitas akses.

Deletion: Tombstone pada Open Addressing #

Penghapusan pada open addressing tidak bisa sekadar mengosongkan bucket. Bila kita insert k1 -> bucket 3, lalu k2 collision dan menempati bucket 4 (probe 1), lalu k1 dihapus — k2 akan hilang dari pandangan lookup yang berhenti pada bucket kosong.

Solusinya: gunakan tombstone — penanda “pernah dihapus, lewati saat probing tetapi anggap kosong saat insert”. Tombstone perlu dibersihkan secara berkala (mis. saat rehash) agar tidak menurunkan performa lookup.

text
State setelah insert k1, k2 (collision), lalu erase(k1):

[0] empty   [1] empty   [2] k2   [3] TOMBSTONE   [4] empty

find(k2): h(k2)=3 -> tombstone, lanjut -> bucket 4? BUKAN, bucket 2!

Tabel di atas menggambarkan skenario hipotetis: urutan insert berbeda menghasilkan layout berbeda. Detail implementasi akan kita bahas tuntas di Chapter Open Addressing.

Pemilihan Strategi: Panduan Praktis #

Berikut panduan kasar untuk memilih strategi berdasarkan situasi:

Situasi	Rekomendasi
Akses data acak, α moderat (~0.5), pentingkan kesederhanaan	Separate chaining dengan vector per bucket
Akses data intensif, α dapat dikontrol ketat (<0.7)	Open addressing dengan double hashing
Iterasi sering, urutan relatif penting	Separate chaining (lebih stabil saat rehash)
Memori sangat terbatas	Open addressing (tanpa overhead pointer)
Deletion sering	Separate chaining (tombstone pada open addressing berisiko boros)

Ringkasan #

Collision adalah konsekuensi pigeonhole principle dan muncul lebih cepat dari intuisi karena birthday paradox.
Dua keluarga strategi: separate chaining (wadah sekunder per bucket) dan open addressing (probing di array datar).
Separate chaining toleran terhadap α tinggi, deletion mudah; open addressing cache-friendly tetapi sensitif terhadap clustering dan α.
Variasi open addressing: linear (primary clustering), quadratic (secondary clustering), double hashing (paling merata).
Deletion pada open addressing membutuhkan tombstone; deletion pada chaining trivial.
STL std::unordered_map memakai separate chaining; cache-friendly hash table modern memakai open addressing.