Struktur Data : Collision Resolution

📋 Daftar Isi

Collision Resolution: Penyelesaian bila terjadi collision (tabrakan). Dikatakan terjadi collision jika dua buah keys dipetakan pada sebuah sel (index array yang
sama). Collision bisa terjadi saat melakukan insertion dan dibutuhkan prosedur tambahan untuk mengatasi terjadinya collision.

Dua strategi umum:

Closed Hashing (Open Addressing)
Open Hashing (Chaining)

Collision Resolution: Closed Hashing (Open Addressing)

Ide: mencari alternatif sel lain pada hash table.

Padda proses insertion, coba sel lain sesuai urutan dengan menggunakan fungsi pencari seperti berikut:

\[ h_{i}(x)=(hash(x)+f(i)) \bmod H-size \]

Fungsi f digunakan sebagai pengatur strategi collision resolution. Bagaimana bentuk fungsi f ? Ada 3 strategi:

Linear probing
Quadratic probing
Double hashing

Linear Probing

Gunakan fungsi linear: \(f(i)=i\)

Bila terjadi collision, cari posisi pertama pada tabel yang terdekat dengan posisi yang seharusnya. Telusuri table di sampingnya sampai ada tempat yang kosong. Dimulai dari nilai yang didapat dari hash function (array hash table dianggap circular, sehingga jika sampai akhir array dia akan balik lagi ke awal index 0)
Fungsi linear relatif paling sederhana, mudah diimplementasikan
Dapat menimbulkan masalah 🡪 primary clustering (elemen-elemen yang menurut perhitungan hash diletakkan pada lokasi sel berbeda, diarahkan pada sel pengganti yang sama, sehingga membentuk cluster, sehingga membutuhkan waktu yang lama untuk mencari sel kosong untuk pengganti atau ketika mencari elemen)

Contoh

Linear probing hanya disarankan untuk ukuran hash table yang ukurannya lebih besar dua kali dari jumlah data. Membentuk suatu grup atau cluster, sehingga membutuhkan waktu lama untuk mencari sel kosong karena harus memeriksa satu per satu sel terdekat (Primary Clustering)

Quadratic Probing

Metode ini menghindari clustering dengan menggunakan fungsi \(f(i)=i^{2}\)

Telusuri table dengan men-skip index sesuai nilai kuadratik (1, 4, 9, 16, …)

Bisa terjadi secondary clustering: cluster – cluster terbentuk di tempat –
tempat dilaluinya quadratic probing yaitu \(f(x) + 1, f(x) + 4, f(x) + 9\), dst

Double Hashing

Double hashing dapat menemukan slot kosong lebih cepat daripada linear probing. Menggunakan 2 fungsi hash, sehingga menjadi sebagai berikut:

\[(hash1(key)+i \times hash2(key))%Table_Size\]

Cek lokasi hash1(key) apakah kosong. Jika kosong, masukan.
Jika tidak kosong, hitung hash2(key). Cek apakah (hash1(key) + hash2(key))%size kosong
Jika tidak kosong, cek berulang untuk:
(hash1(key) + 2*hash2(key))%size,
(hash1(key) + 3*hash2(key))%size,
(hash1(key) + 4*hash2(key))%size, dst sampai menemukan index yang kosong

Contoh:

\[ N=13\] \[h(k)=k \bmod 13\] \[d(k)=7-k \bmod 7\]

Insert keys 18, 41, 22, 44, 59, 32, 73

Untuk key 44:

h(k) = 5 , sudah ada isinya yaitu 18
d(k) = 5 , (h(k)+d(k)) mod 13 = 10 kosong, masukkan 44 ke index 10

Collision Resolution: Open Hashing (Chaining)

Permasalahan Collision diselesaikan dengan menambahkan seluruh elemen yang memilih nilai hash sama pada sebuah set

Open Hashing:

Menyediakan sebuah linked list untuk setiap elemen yang memiliki nilai hash sama
Tiap sel pada hash table berisi pointer ke sebuah linked list yang berisikan data/elemen

Contoh:

Key: 19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79

\[ H(key) = key \bmod 13 \]

Hash table yang terbentuk menjadi:

Untuk pencarian, gunakan fungsi hash untuk menentukan linked list mana yang memiliki elemen yang dicari, kemudian lakukan pembacaan terhadap linked list tersebut. Dapat juga digunakan struktur data lain selain linked list untuk menyimpan elemen yang memiliki fungsi hash yang sama tersebut. Kelebihan utama dari metode ini adalah dapat menyimpan data yang tak terbatas (dynamic expansion). Kekurangan utama adalah penggunaan memori pada setiap sel lebih banyak.