Assalamu'alaykum,
kali ini saya akan membahas mengenai MANAJEMEN KOLISI DAN COLLISION RESOLUTION
dalam sistem berkas
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
COLISION
- 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 :
 |
| RUMUS |
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 a ;
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
- Urutan kunci yang masuk adalah 20, 31, 33, 40, 10, 12, 30, dan 15
 |
| JAWABAN |
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 :
 |
| CARA |
 |
| JAWABAN |
CONTOH SOAL:
 |
JAWABAN
open addresing:
 | |
 |
| COALESED |
SEMOGA BERMANFAAT (:
