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.

Organisasi Berkas Langsung

Dengan organisasi berkas langsung, untuk menemukan suatu rekaman tidak melalui proses pencarian, namun bisa langsung menuju alamat yang ditempati rekaman.

Pada awalnya, untuk tujuan tersebut maka digunakan cara dengan menyimpan rekaman pada alamat yang sama dengan nilai kunci rekaman tersebut. Contohnya : rekaman dengan kunci 100 akan disimpan di alamat 100. Sehingga untuk menemukan sebuah rekaman cukup melihat nilai kunci dan menuju ke alamat yang ditunjuk oleh kunci rekaman tersebut. Contoh : untuk membaca rekaman dengan kunci 55 langsung saja menuju alamat 55.

Dalam hal ini akan dibahas berbagai teknik yang dapat digunakan sebagai alternatif dalam merancang system. Khususnya dalam menentukan lokasi rekaman yang akan disimpan serta pembacaan rekaman tersebut.

Hal tersebut hanya mungkin terjadi bila bila kunci rekaman juga merupakan alamat lokasi rekaman. Dengan demikian waktu pencarian akan sangat baik, yaitu 1 probe untuk setiap rekaman yang dicari. Harus dimengerti harus tersedia 1 lokasi untuk setiap kemungkinan kunci rekaman.

Cara Untuk mengorganisasi berkas untuk pengaksesan langsung, yaitu :

1. Kunci Sebagai Alamat Rekaman Yang Unik

Untuk mendapatkan rekaman yang diasosiasikan dengan suatu kunci primer, sangat diharapkan agar proses langsung menuju ke alamat tempat rekaman dengan kunci tertentu disimpan. Hal tersebut hanya mungkin terjadi apabila kunci rekaman juga merupakan alamat lokasi rekaman. Untuk suatu aplikasi dengan rekaman berisi informasi mahasiswa, untuk tigabelas digit nomor identitas mahasiswa (atau kunci utama rekaman yang merupakan gabungan dari 4 digit kode fakultas + jurusan, 4 digit tahun angkatan + 5 digit nomor urut), maka diperlukan 9.000.000.000.000 lokasi sebagaimana diperlihatkan pada gambar dibawah ini.

 

  Dengan demikian waktu pencarian akan sangat baik, yaitu probe 1 untuk setiap rekaman yang dicari. Namun teknik tersebut memiliki kerugian, karena diperlukan ruang yang sangat besar untuk menampung semua rekaman. Namun, pasti ada beberapa nomor yang kosong karena beberapa alasan, misalnya sudah lulus, mengundurkan diri, drop-out, cuti, dan sebagainya. Sehingga tidak semua ruang dimanfaatkan.

2. Konversi kunci rekaman menjadi satu alamat yang unik

Dilakukan untuk mengantisipasi kerugian dengan korespondensi 1-1. Terdapat beberapa formula, beberapa diantaranya.

Contoh Sistem reservasi penerbangan. Jika suatu maskapai penerbangan memiliki nomor penerbangan dari 1 sampai 999, ingin memantau reservasi pesawat selama setahun yang jumlah harinya 1 sampai 366 (1 tahun), maka nomor penerbangan dan hari-ke dapat dihubungkan untuk mendapatkan lokasi rekaman yang berisi data reservasi penerbangan pada hari tertentu.