Salah satu alasan diaplikasikannya fungsi hash adalah
bahwa fungsi hash akan mendistribusikan kunci seperangkat data dengan lebih
merata. Fungsi hash yang menghasilkan banyak kolisi atau
sinonim dikatakan memiliki kluster prima. Makin sedikit jumlah kolisi, makin baik fungsi hashing
tersebut karena makin sedikit waktu yang diperlukan untuk melihat tempat-tempat
yang berbeda dalam rangka menemukan yang diinginkan dan juga akan
mempertahankan probe atau kases terhadap penyimpanan agar mendekati satu.
Beberapa cara
yang dapat ditempuh untuk mereduksi kolisi adalah mengganti fungsi
hashing, atau dengan mereduksi
factor-packing.
Faktor-packing suatu berkas adalah perbandingan (atau rasio) antara
jumlah rekaman yang disimpan dengan berkas, atau dapat dinyatakan sebagai
berikut :
FP (Factor Packing) = Jumlah rekaman yg disimpan / Jumlah total lokasi penyimpanan
Kerugian dari
usaha mengurangi nilai factor packing dengan tujuan untuk mengurangi jumlah kolisi
membawa pada konsekuensi diperlukannya ruang yang lebih luas untuk menyimpan
jumlah rekaman yang sama.
2.2.1. Resolusi Kolisi
Mengubah fungsi hashing atau mengubah factor-packing
à
mengurangi jumlah kolisi. Tetapi, tidak akan mengeliminasi kolisi tersebut. Diperlukan
suatu prosedur untuk menempatkan sinonimnya ke posisi lain bila kolisi memang
benar terjadi.
Tujuan utama metode resolusi kolusi adalah
menempatkan rekaman sinonim pada suatu lokasi yang membutuhkan probe tambahan
yang minimum dari home-address rekaman tersebut. Salah satu penyelesaian yang
dapat dilakukan adalah memberikan penunjuk pada lokasi rekaman sinonim. Bila terjadi
sinonim jamak pada satu home-address tertentu, akan dibentuk rantai rekaman
sinonim.
Sebagai contoh R1, R2, R3 sinonim dengan home
address r maka rantai sinonim akan berbentuk seperti diperlihatkan oleh gambar
dibawah ini. Medan penghubung lokasi r menunjuk pada lokasi s dimana tersimpan
sinonim pertama, yaitu R2 disimpan. Simbol ^ atau petunjuk nol pada medan
penghubung t menunjukkan akhir dari rantai sinonim.
a)
Coalesced
– Hashing
Metode resolusi yang menggunakan penunjuk untuk
menghubungkan elemen-elemen dari sebuah rantai sinonim.
Coalesced Hashing terjadi bila terdapat usaha untuk
menyisipkan sebuah rekaman dengan home-address yang sudah diokupasi oleh
rekaman dari rantai yang memiliki home address yang berbeda.
