Analisa Hashing

Salah satu alasan diaplikasikannya fungsi hash adalah bahwa fungsi hash akan mendistribusikan kunci seperangkat data dengan lebih merata kedalam berkas. Fungsi hash yang menghasilkan banyak kolisi atau sinonim dikatakan sebagai memiIiki kluster primer. Makin sedikit jumlah kolisi, makin baik fungsi hashing tersebut karena makin sedikit waktu yang diperlukan untuk melihat tempat-tempat yang berbeda dalam rangka menemukan 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. Faktor-packing suatu berkas adalah perbandingan (atau rasio) antara jumlah rekaman yang disimpan dengan berkas, atau dapat dinyatakan sebagai berikut;

Faktor packing (FP) =

Jumlah rekaman yang 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.

RESOLUSI KOLISI Yang menjasi tujuan utama metode resolusi kolisi adalah menempatkan rekaman sinonim pada suatu lokasi yang membutuhkan probes tambahan yang minimum dari home-address rekaman tersebut. COALESCED HASHING Coalesced hashing adalah metode resolusi yang menggunakan petunjuk untuk menghubungkan elemen-elemen dari sebuah rantai sinonim. Coalescedn 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. LICH DAN EISHCH 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. 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 homeaddress. 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 seakanakan tombstone tersebut tidak ada. 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. Dengan demikian sebuah bucket (blok/halaman) dapat didefinisikan sebagai unit penyimpanan yang berada diantara rekaman dengan berkas, juga sebuah unit dengan informasi yang dapat diakses dan dipindahkan antar peralatan penyimapan. Jumlah rekaman yang dapat diletakkan pada satu bucket disebut dengan factor-blocking. Jika factor-blocking meningkat, jumlah akses terhadap penyimpanan akan mengecil karena beberapa rekaman yang akan berkolisi dapat disimpan dalam satu alamat yang sama.

Pengunanan bucket sangat tepat bila panjang rekaman merupakan factor dari unit pengingat yang terkecil yang akan dialokasikan oleh system oerasi. PEMBAGIAN LINEAR Resolusi kolisi dengan teknik pembagian linear merupakan varian dari progressive-overflow. Kalau dalam progressive-overflow inkremen untuk menuju ke lokasi berikutnya adalah constant (1=satu), maka pada pembagian linear digunakan inkremen yang bersifat variable, yang bertujuan mereduksi pengklusteran sekunder yang terjadi pada progessive-overflow, dengan demikian, jumlah probe untuk pembacaan juga berkurang. Pengklasteran sekunder akan terjadi pada skema hashing dengan inkremen yang berupa konstanta atau hanya tergantung pada home-address rekaman. Pada pembagian linear, inkremen merupakan fungsi dari kunci yang akan disisipkan. Fungsi tersebut dapat juga disebut sebagai fungsi hashing lain karena digunakan untuk mengkonversi kunci menjadi sebuah inkremen, maka dapat dikelompokkan sebagai metode resolusi kolisi dengan hashing ganda, mengingat pertama dilakukan hash untuk menentukan homeaddress, dan kedua untuk mendapatkan inkremen yang merupakan bilangan primer dari ukuran berkas. Tidak seperti rantai coalesced, sinonim pada pembagian linear umumnya tidak berada pada rantai probe yang sama. Karena inkremen yang berbeda akan menghasilkan rantai probe berbeda, pengklusteran sekunder dapat direduksi.