MANAJEMEN KOLISI

Assalamualaikum Warahmatullahi Wabarakatu.

Jumpa lagi dengan saya pada pertemuan hari ini, semoga kalian sehat selalu dan selalu berada pada lindungan ALLAH SWT. Aamiin Yaa Rabbal Alaamiin.

Apasih manajemen kolisi itu ?????

Ok , Langsung saja kita ke pembahasan.

Salah satu alasan di aplikasikannya fungsi hash adalah akan mendistribusikan kunci seperangkat data yang lebih merata. Kalau tujuan tersebut tidak tercapai, maka salah satu cara yang dipakai adalah mengkombinasikan beberapa fungsi sederhana dalam satu aplikasi. Terkadang dalam fungsi hash dapat menghasilkan kolisis atau sinonim. Makin sedikit jumlah kolisi makin baik pula fungsi hashing tersebut. 

Penyelesaian yang dapat dilakukan adalah memberikan penunjuk pada lokasi rekaman sinonim. Bila terjadi sinonim jamak pada satu home address tertentu maka akan dibentuk rantai rekaman sinonim.

Sebagai contoh : R1, R2 dan R3 sinonim dengan home addres  r menunjuk pada lokasi s dimana tersimpan sinonim pertama yaitu R2  Simbul ^ menunjuk nol pada penghubung t  menunjukan akhir dari rantai sinonim.

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.
• Kejadian 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 :

Resolusi Kolisi

• Yang menjadi tujuan utama metode resolusi adalah menempatkan rekaman synonim pada suatu lokasi yang membutuhkan probe 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 => ;

Beberapa Metode Untuk Mengatasi Koisi

1. 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

2. Metode Coalesced Hashing 

• Bila terjadi tumbukan dalam pemasukan kunci rekaman maka dapat dicari alamat yang paling besar / paling akhir
• Contoh : misalkan akan dilakukan penyisipan rekamanrekaman 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 :