Hash Function

8 09 2010

Hash Function merupakan suatu fungsi yang terkait dengan Hash Set dan Hash Table atau Hash Map. Hash ‘whatever’ biasanya digunakan untuk membuat struktur data yang nantinya akan mudah untuk digunakan dalam pemrosesan data. Dimana tujuan utama dari diimplementasikannya Hash Function di dalam suatu aplikasi adalah untuk mengurangi waktu pencarian data, sehingga program-program yang diciptakan akan dapat dijalankan dengan lebih efisien.

Proses yang dilakukan dalam Hash Function ini adalah mentransformasikan data yang dianggap sebagai key dari suatu deretan data menjadi suatu hash value yang nantinya dipakai untuk mengidentifikasikan data tersebut. Data yang ditransformasikan tersebut tidak hanya terdiri dari data key saja, tetapi juga mencakup data-data yang terkait dengan data key tersebut. Function yang digunakan untuk mencari key dari suatu deretan data dapat dalam bentuk yang bermacam-macam misalnya dengan menggunakan fungsi “mod” untuk data angka, fungsi yang memanfaatkan nama file, ukuran file, dan karateristik file lainnya untuk data dalam bentuk file, fungsi sequencing untuk data dalam bentuk sequence, fungsi probabilitas untuk data dalam bentuk angka, dan fungsi-fungsi lainnya.

Apabila sekumpulan data mempunyai data key yang sama maka akan terjadi ‘collision’. Ada beberapa cara untuk menangani collision ini termasuk memasukkan sekumpulan data tersebut ke dalam suatu hash value yang sama dengan membuat suatu struktur data dalam bentuk tertentu seperti linked list. Bisa juga dilakukan dengan melakukan open addressing yang artinya menyediakan hash value yang baru untuk data yang sama tersebut. Ada berbagai macam cara untuk menyediakan hash value yang baru untuk data yang mengalami collision tersebut. Cara yang lainnya adalah dengan menghapus data yang muncul belakangan.

Beberapa bidang yang menjadi pengaplikasian Hash Function ini adalah pembuatan Hash Table, caches, menemukan duplikat records, menemukan similar records, menemukan similar substrings dan lain-lain.

Referensi:
[1] Knuth, Donald (1973). The Art of Computer Programming. Sorting and Searching Vol 3, pp. 506–542.


Actions

Information

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




%d bloggers like this: