Hashing Minimal Sempurna Menggunakan Metode Peringkat

Abstract

Salah satu metode pencarian dalam struktur data adalah hashing, yaitu teknik perhitungan yang menemukan alamat suatu rekord dengan cara membentuk fungsi hash. Kadangkala fungsi hash yang telah ditentukan ternyata tidak cukup unik dalam menentukan alamat suatu rekord sehingga timbul penumpukan (collision). Salah satu cara mengatasi penumpukan adalah membentuk fungsi hash minimal sempurna yang cara kerjanya sangat cocok untuk kunci berupa huruf. Dengan dilakukan peringkasan kunci yang terprogram dihasilkan pasangan huruf atau lebih yang berbeda pada setiap kunci. Dari hasil peringkasan ini dapat ditentukan alamat masing-masing kunci dengan mengunakan metode peringkat. Karena cara kerjanya yang menghasilkan pemetaan bijektif (pemetaan satu-satu antara n kunci dengan n alamat) maka penumpukan dapat dihindari dan dapat menghemat ruang memori. Besarnya kompleksitas algoritme ini adalah O(kn) dengan k adalah jumlah bit dan n adalah jumlah kunci. Pada hashing biasa/tidak sempurna dihasilkan penumpukan kunci sebesar 39.06% karena bentuk fungsi yang digunakan tidak mampu mentranformasi kunci yang ada agar menyebar ke seluruh tabel alamat. Bentuk fungsi yang digunakan adalah fungsi sisa pembagian, sedangkan ukuran tabel alamat yang dihasilkan terlalu besar sehingga memboroskan pemakaian memori. Karakterisitik penumpukan terjadi apabila selisih bilangan antara satu kunci dengan kunci yang lain habis dibagi dengan ukuran tabel alamatnya. Besarnya kompleksitas algoritme yang dipakai adalah O(nm) dengan n adalah jumlah kunci dan m adalah jumlah huruf pada kunci.