Hashing Functions


Memilih fungsi hash yang baik, h(k), adalah sangat penting untuk pencarian berbasis hash-table. h merupakan distribusi elemen dari koleksi data yang secara unik menempati “SLOT” pada tabel hash. Kriteria dari key sebaiknya menghasilkan jumlah collision yang minimum.

Jika probabilitas key, k, terjaadi pada koleksi data kita P(k), kemudian terdapat m slot didalam tabel hash kita, maka uniform hashing function, h(k), adalah sebagai berikut:

uniform_hash.gif

Sebagai contoh jika kunci secara acak terdistribusi pada [0, r], maka

h(k) = floor((mk)/r)

akan menghasilkan uniform hasing.

Mapping keys untuk bilangan asli

Kebanyakan fungsi hash akan map pertama dari kunci di set pada bilangan asli, anggap saja (0,r]. Sebenarnya banyak cara untuk melakukan mapping, sebagai contoh jika key adalah string dari karakter ASCII, kita tinggal menambahkan representasi ASCII dari karakter mod 255 untuk menghasilkan angka (0,255) – atau menggunakan fungsi xor, atau menembahkannya dala mod 212

  1. Menggunkan fungsi mod:
    h(k) = k mod m
    Apabila menggunakan method ini, kita biasanya menghindari nilai pasti dari m. Perpangkatan dari 2 biasanya dihindari, untuk k mod 2b secara sederhana pilih b yang kurang dari k. Bilangan prima yang mendekati perpangkatan 2 secara umum merupakan pilihan yang baik untuk m. Sebagai contoh, jika kita memiliki 4000 elemen dan kita memilih organisasi tabel overflow, tetapi lebih baik untuk mempunyai kemungkinan collisions yang kecil, maka kita memilih m = 4093. (4093 dalah bilangan prima terbesar yang kurang dari 4096=212).
  2. Menggunakan metode perkalian
    – Kalikan key dengan bilangan konstan A, 0 < A < 1,
    Kurangi sebagian kecil dari hasil perkalian tersebut
    – Kalikan nilai tersebut dengan m.
    Sehingga fungsinya sebagai berikut:

    h(k) = floor(m * (kA – floor(kA)))

    Dalam kasus ini nilai dari m tidak begitu penting dan pilih perpangkatan dari 2 sehingga kita dapat mendapatkan efisien prosedur:
    – pilih m = 2 p
    – kalikan bit w dari k dengan floor(A*2 w ) untuk menghasilkan 2 w bit
    – kurangi p bit paling signifikan dari setengah hasilnya
    A = (sqrt(5)-1)/2 = 0.6180339887

Bila bingung berlanjut baca Knuth, “Sorting and Searching”, v. 3 of “The Art of Computer Programming”

Technorati : , ,
Del.icio.us : , ,
Zooomr : , ,
Flickr : , ,

2 thoughts on “Hashing Functions

  1. he3….hash…jadi teringat seseorang lut….
    he…blog mu kuq rada feminin gini design na,…ganti bos..wkwkwkwk

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s