* 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 ->;
* 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 :
- Ruang alamat yang tersedia : 10 alamat
- Metode collision resolution yang dipakai adalah open addressing dengan linier probing jarak 3
Jawaban Linier Probing
* 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 :
Tidak ada komentar:
Posting Komentar