MANAJEMEN KOLISI
Salah satu fungsi hash adalah akan mendistribusikan data secara merata ke dalam berkas. Jika tujuan tersebut tidak tercapai, salah satu strategi yang bisa diambil adalah mengkombinasikan beberapa fungsi sederhana dalam satu aplikasi. Fungsi hash menghasilkan banyak kolisi atau sinonim dikatakan memiliki kluster primer. Makin sedikit jumlah kolisi, makin baik fungsi hashing tersebut karena makin sedikit waktu yang diperlukan rekaman yang diinginkan, dan juga akan mempertahankan probe atau akses terhadap penyimpan agar mendekati satu.
Beberapa cara yang dapat ditempuh untuk mereduksi kolisi adalah mengganti fungsi hashing, atau dengan mereduksi factor-packing. Factor-packing suatu berkas adalah perbandingan (atau rasio) antara jumlah rekaman yang disimpan dalam berkas dengan kapasitas berkas, atau dapat dinyatakan sebagai berikut :
` Mengubah fungsi hashing atau mengubah factor-packing akan dapat mengurangi jumlah kolusi. Akan tetapi, pada umumnya tidak akan mengeliminasi kolusi tersebut. Oleh karena itu, diperlukan suatu posedur untuk menempatkan sinonimnya ke posisi lain bila kolisi memang benar terjadi. Yang menjadi tujuan utama metoda resolusi kolusi adalah menempatkan rekaman sinonim pada suatu lokasi yang membutuhkan probe tambahan yang minimum dari home-address rekaman tersebut.
Coalesed-Hashing
Coalesed-Hashing adalah metode resolusi yang menggunakan penunjuk untuk menghubungkan elemen-elemen dari sebuah rantai sinonim. Coalesced-hashing (kolisi) terjadi bila terdapat usaha untuk menyisipkan sebuah rekaman dengan home-address yang sudah di okupasi oleh rekaman dari rantai yang memiliki home-address yang berbeda. Algoritma untuk coalesced-hashing adalah sebagai berikut:
a) Lakukan hashing pada semua kunci rekaman yang akan disisipkan untuk mendapatkan home-address
atau calon-address yang mungkin akan ditempati oleh rekaman-rekaman tersebut.
b) Jika home-address kosong, sisipkan rekaman pada lokasi tersebut, jika rekaman ternyata kembar,
akhiri program dengan pesan ‚Rekaman Kembar‛, jika tidak :
- Cari lokasi terakhir rantai-sinonim dengan mengikuti penunjuk pada medanpenghubung sampai
menemukan symbol ^ yang menandakan akhir dari rantai.
- Cari lokasi paling bawah dalam berkas (atau memiliki alamat paling besar). Jika tidak ditemukan,
akhiri program dengan pesan ‚Berkas Penuh‛.
- Sisipkan rekaman ke dalam lokasi yang kosong sudah teridentifikasi dan atur medan-penguhubung
rekaman terakhir dalam rantai-sinonim agar menunjuk ke lokasi rekaman yang baru saja disisipkan.
LICH dan EISCH
Berbagai usaha telah dilakukan untuk mengurangi kolisi pada rantai sinonim sehingga mengurangi probe pembacaan dan akhirnya meningkatkan kinerja. Beberapa varian dari coalesced-hashing dapat diklasifikasikan ke dalam tiga cara:
- Mengorganisasi berkas (dengan atau tanpa overflow)
- Menghubungkan item yang terkolisi kedalam rantai
- Memilih lokasi yang belum ada penghuinya
Kolisi mungkin dapat direduksi dengan memodifikasi organisasi berkas. Cara pertama adalah dengan memisahkan antara area untuk data prima dengan area untuk data overflow, area primer adalah ruang alamat yang cocok dengan fungsi hash. Overflow (atau Cellar) adalah area yang hanya berisi rekaman-rekaman yang sinonim. Faktor alamat adalah perbandingan antara area primer dengan ukuran total berkas.
Progressive Overflow
Kerugian utama penggunaan coalesced-hashing adalah diperlukannya penyimpanan tambahan untuk medan penghubung. Bila penyimpanan tambahan tersebut tidak tersedia, maka penghubung yang sifatnya fisik tidak tersedia, sehingga perlu dipertimbangkan teknik resolusi kolisi yang menggunakan konversi untuk menentukan kemana selanjutnya rekaman harus dicari.
Salah satu konversi yang sederhana adalah penggunaan overflow yang progresif atau probing secara linier. Sesuai namanya bila lokasi yang akan ditempati telah terisi, maka lokasi selanjutnya dilihat apakah masih belum terisi. Secara progresif lokasi selanjutnya di overflow.
Penggunaan Buckets
Dalam diskusi mengenai prosedur resolusi kolisi, diasumsikan bahwa hanya sebuah rekaman saja yang dapat disimpan pada sebuah alamat penyimpanan. Jumlah pengaksesan dapat direduksi dengan meletakkan lebih dari satu rekaman pada satu alamat penyimpanan. Kemungkinan tersebut dapat direalisir bila digunakan sistem ‚buckets‛ (disebut juga ‚blok‛ atau ‚halaman‛).
Pembagian Linier
Resolusi kolisi dengan teknik pembagian-linier merupakan varian dari progressiveoverflow. Kalau ada progressive-overflow inkremen untuk menuju ke lokasi berikutnya adalah konstan (1=satu), maka pada pembagian-linier digunakan inkremen yang bersifat variable.
Tujuan inkremen yang variable adalah mereduksi pngklusteran sekunder yang terjadi pada progressive-overflow sehingga jumlah probe untuk pembacaan kembali juga berkurang. Pengklusteran sekunder akan terjadi pada skema hashing dengan fungsi inkremen yang berupa konstanta atau yang hanya bergantung pada home-address rekaman.
0 komentar:
Posting Komentar