Manajemen Kolisi

Salah satu alasan diaplikasikannya fungsi hash adalah bahwa fungsi hash akan mendistribusikan kunci seperangkat data dengan lebih merata. Fungsi hash yang menghasilkan banyak kolisi atau sinonim dikatakan memiliki kluster prima. Makin sedikit jumlah kolisi, makin baik fungsi hashing tersebut karena makin sedikit waktu yang diperlukan untuk melihat tempat-tempat yang berbeda dalam rangka menemukan yang diinginkan dan juga akan mempertahankan probe atau kases terhadap penyimpanan agar mendekati satu.

Beberapa cara yang dapat ditempuh untuk mereduksi kolisi adalah mengganti fungsi hashing, atau dengan mereduksi factor-packing.

Faktor-packing suatu berkas adalah perbandingan (atau rasio) antara jumlah rekaman yang disimpan dengan berkas, atau dapat dinyatakan sebagai berikut :

FP (Factor Packing) = Jumlah rekaman yg disimpan / Jumlah total lokasi penyimpanan

Kerugian dari usaha mengurangi nilai factor packing dengan tujuan untuk mengurangi jumlah kolisi membawa pada konsekuensi diperlukannya ruang yang lebih luas untuk menyimpan jumlah rekaman yang sama.

2.2.1.   Resolusi Kolisi

Mengubah fungsi hashing atau mengubah factor-packing à mengurangi jumlah kolisi. Tetapi, tidak akan mengeliminasi kolisi tersebut. Diperlukan suatu prosedur untuk menempatkan sinonimnya ke posisi lain bila kolisi memang benar terjadi.

Tujuan utama metode resolusi kolusi adalah menempatkan rekaman sinonim pada suatu lokasi yang membutuhkan probe tambahan yang minimum dari home-address rekaman tersebut. Salah satu penyelesaian yang dapat dilakukan adalah memberikan penunjuk pada lokasi rekaman sinonim. Bila terjadi sinonim jamak pada satu home-address tertentu, akan dibentuk rantai rekaman sinonim.

Sebagai contoh R1, R2, R3 sinonim dengan home address r maka rantai sinonim akan berbentuk seperti diperlihatkan oleh gambar dibawah ini. Medan penghubung lokasi r menunjuk pada lokasi s dimana tersimpan sinonim pertama, yaitu R2 disimpan. Simbol ^ atau petunjuk nol pada medan penghubung t menunjukkan akhir dari rantai sinonim.

 

a)                    Coalesced – Hashing

            Metode resolusi yang menggunakan penunjuk untuk menghubungkan elemen-elemen dari sebuah rantai sinonim.

            Coalesced Hashing terjadi bila terdapat usaha untuk menyisipkan sebuah rekaman dengan home-address yang sudah diokupasi oleh rekaman dari rantai yang memiliki home address yang berbeda.

            Algoritma untuk COALESCED HASHING :

1.      Lakukan hashing pada semua kunci rekaman yang akan disipkan untuk mendapatkan home-address atau calon-address yang mungkin untuk ditempati oleh rekaman-rekaman tersebut

2.      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 medan-penghubung sampai menemukan symbol  yang menandakan akhir dari rantai

·         Cari lokasi paling bawah dalam berkas (yang memiliki alamat paling besar). Jika tidak ditemukan akhiri program dengan pesan “berkas penuh”

·           Sisipkan rekaman ke dalam lokasi yang kosong yang teridentifikasi dan atur medan-penghubung rekaman terakhir dalam rantai-sinonim agar menunjuk ke lokasi rekaman yang baru saja disisipkan.

                                                

b)      LICH dan EISCH

Beberapa varian dari coalesced hashing dapat diklasifikasikan kedalam tiga cara:

·         Mengorganisasikan berkas (dengan atau tanpa overflow)

·         Menghubungkan item yang terkoalisi ke dalam rantai

·         Memilih lokasi yang belum ada penghuninya.

            Kolisi mungkin dapat direduksi dengan memodifikasi organisasi berkas, dengan cara memisahkan antara area untuk data primer dangan area untuk data overflow yang disebut teknik LICH (Late Insertion Coalesced Hashing), karena rekaman yang baru disisipkan pada akhir rantai sinonim.

Teknik lain untuk meningkatkan kinerja probe pembacaan kembali adalah dengan melakukan variasi penempatan posisi, yang disebut EISCH (Early Insertion Standard Coalesced Hashing) dengan cara menyisipkan rekaman baru pada posisi rantai sinonim tepat sesudah rekaman yang disimpan pada home-address.

c)      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 dapat disediakan, sehingga perlu dipertimbangkan teknik resolusi kolisi yang menggunakan suatu bentuk konvensi untuk menemukan kemana selanjutnya rekaman harus dicari.

            Salah satu bentuk konvensin yang sederhana adalah penggunan overflow yang progrsif atau disebut juga probing secara linear.

            Kelemahan utama progressive overflow adalah rata-rata probe yang sangat tinggi. Meskipun demikian progressive overflow lebih efektif dibandingkan dangan berkas sekuensial, mengingat pencarian dimulai dari home-address. Demikian juga untuk pencarian rekaman, tidak seluruh rekaman harus dibaca karena proses akan berhenti bila ditemukan slot yang kosong.

            Untuk menghapus rekaman harus diperhatikan agar proses pencarian rekaman tidak terhenti karena menemukan slot kosong berkas rekaman yang sudah dihapus. Untuk itu, penghapusan rekaman diikuti dengan meletakkan tombstone pada posisi rekaman yang dihapus, maka diartikan sebagai: tetaplah mencari rekaman dengan memeriksa rekaman-rekaman pada posisi berikutnya.

            Bila dikemudian ternyata terdapat rekaman baru yang harus disisipakan dan memiliki home-adrress sama dengan rekaman yang ditempati tombstone, maka rekaman baru disisipkan pada posisi tersebut seakan-akan tombstone tersebut tidak ada.

 

d)     Penggunaan Bucket

             Penggunaan Bucket Adalah unit penyimpanan yang berada diantara rekaman dengan berkas, juga sebuah unit dengan informasi yang dapat diases dan dipindahkan antar peralatan penyimpan

             Jumlah pengaksesan dapat direduksi dengan meletakkan atu rekaman pada satu alamat penyimpanan.

e)     Pembagian Linear

            Resolusi kolisi dengan teknik pembagian linear merupakan varian dari progressive-overflow. Tujuan inkremen yang variable adalah mereduksi pengklusteran sekunder yang terjadi pada progressive-overflow, yang artinya pembacaan probe akan berkurang. Terdapat inkremen yang merupakan fungsi dari kunci yang akan disisipkan. Fungsi tersebut dapat juga disebut sebagai fungsi hashing lain karena fungsi tersebut digunakan untuk mengkonversi kunci menjadi sebuah inkremen. Pembagian linear dapat dikelompokkan sebagai metode resolusi kolisi dengan hashing-ganda.

1.      Di lakukan hash untuk menentukan home address, dalam hal ini menggunakan fungsi H1

2.      Di lakukan hash untuk mendapatkan inkremen, dalam hal ini menggunakan fungsi H1

Terdapat 2 alternatif bentuk H2:

1.      H2  : Pembagian (kunci/P) modulus P

2.      H2’ : (kunci modulus (P-2)) + 1

di mana P adalah bilangan Prima dari ukuran berkas.

                                    Algoritma :

                                                                    I.            Hash kunci yang akan disisipkan ke dalam berkas untuk memperoleh home-address sebagai tempat menyimpan rekaman

                                                                 II.            Jika home-address kosong, sisipkan rekaman ke dalam lokasi tersebut, jika tidak maka :

                                                                                    A.            tentukan inkremen dengan menghitung hasil bagi kunci   dengan modulus ukuran berkas. Jika hjasilnya nol, maka inkremennya = 1

                                                                                     B.            beri harga awal pencacah untuk perhitungan lokasi yang akan dicari dengan 1

                                                                                     C.            selama jumlah lokasi yang dicari lebih kecil dari ukuran berkas, maka :

1.      Tentukan alamat yang akan dicari berikutnya dengan menambahkan inkremen terhadap alamat terakhir dan kemudian cari modulusnya terhadap ukuran berkas

2.      Jika alamat tersebut tidak ada yang menempati, maka sisipkan rekaman serta akhiri penyisipan dengan sukses.

3.      Jika lokasi sudah ditempati oleh rekaman yang memiliki kunci yang sama dengan yang akan disisipkan, akhiri proses dengan pesan “ rekaman dobel ”

4.      Tambahkan 1 pada pencacah pencarian lokasi.

                                                                                    D.            Akhiri proses dengan pesan  “ berkas penuh “