KRITERIA FUNGSI HASH YANG BAIK :
- Dapat mendistribusikan setiap rekaman secara merata, sehingga dapat meminimalkan terjadinya collision (tabrakan)
- Dapat dieksekusi secara efisien, sehingga waktu tidak habis hanya untuk menghitung home address saja
Collision (Tabrakan)
- Dengan menggunakan metode hashing, maka secara otomatis hubungan korespondensi satu-satu antara kunci rekaman dengan alamat rekaman menjadi hilang
- Selalu ada kemungkinan terjadinya peristiwa dimana terdapat dua buah kunci yang berbeda namun memiliki home address yang sama
- Kejadi seperti ini dinamakan Collision atau Tabrakan atau Tumbukan
Manajemen Kolisi
- Semakin sedikit jumlah kolisi, maka makin baik bagi fungsi hashing tersebut, karena makin sedikit jumlah waktu yang diperlukan untuk melihat tempat yang berbeda dalam menemukan rekaman yang diinginkan.
- Beberapa cara untuk mengantisipasi kolisi adalah dengan mengganti fungsi hashing, atau mengkombinasikan faktor packing.
- Faktor packing suatu berkas adalah perbandingan (rasio) antara jumlah rekaman yang disimpan dalam berkas dengan kapasitas berkas, atau dapat dinyatakan sbb :
Factor Packing = Jumlah
Rekaman Yang Disimpan
Jumlah Total Lokasi Penyimpanan
Resolusi Kolisi
- Yang menjadi tujuan utama metode resolusi adalah menempatkan rekaman synonim pada suatu lokasi yang membutuhkan probes tambahan yang minimum pada home address rekaman tersebut
Synonim adalah dua atau lebih nilai key yang berbeda pada hash ke
home address yang sama
- Salah satu penyelesaian yang dapat dilakukan adalah dengan memberikan petunjuk pada lokasi rekaman sinonim
- Karena collision dapat di pastikan akan selalu terjadi, maka dapat dikatan bahwa output dari fungsi hash (home-address) bukanlah merupakan alat yang unik yang pasti ditempati oleh rekaman yang diproses, namun hanya berupa kemungkinan alamat yang bisa ditempati
- Jika home-addrees dari suatu rekaman ternyata sudah ditempati rekaman lain, maka harus di carikan alamat lain untuk ditempati oleh rekaman tersebut
- Proses pencarian alamat lain ini dinamakan sebagai Collision Resolution
Berikut beberapa Metode Untuk Mengatasi Kolisi / Tubrukan :
I.
METODE
OPEN ADDRESSING
Alamat alternatif dicari pada alamat-alamat selanjutnya yang masih kosong,
salah satu nya dengan cara Linier Probing
Linier Probing
Pencarian dilakukan dengan jararak pencarian yang fix (tetap), biasanya
satu-satu
Linier Probing Contoh
:
Sesuai dengan namanya jika lokasi yang telah ditempati telah terisi, maka
dilihat lokasi selanjutnya apakah masih belum terisi
- Fungsi Hash yang dipakai adalah : f(key) = key mod 10
- Ruang alamat yang tersedia : 10 alamat
- Metode collision resolution yang dipakai adalah open addressing dengan linier probing jarak 3
- Urutan kunci yang masuk adalah 20, 31, 33, 40, 10, 12, 30, dan 15
II.
METODE COALESCED HASHING
- Bila terjadi tumbukan dalam pemasukan kunci rekaman maka dapat dicari alamat yang paling besar / paling akhir
- Contoh : misalkan akan dilakukan penyisipan rekaman-rekaman dengan kunci 38, 51, 40, 61, 83, 24, dan 60
- Langkah 1 lakukan proses hashing semua kunci dengan kunci modulus 11 (11 adalah kapasitas berkas), maka dihasilkan :
LATIHAN SOAL :
JAWABAN :
