MANAJEMEN KOLISI DAN COLLISION RESOLUTION

Assalamualaikum, Pada kesempatan kali ini saya akan membahas materi sistem Berkas mengenai Manajemen Kolisi dan Collision Resolution dalam sistem berkas, ini diaa

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 rekamansynonim 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