FUNGSI HASHING

FUNGSI HASHING

Hash adalah suatu teknik "klasik" dalam Ilmu Komputer yang banyak digunakan dalam praktek secara mendalam. Hash merupakan suatu metode yang secara langsung mengakses record-record dalam suatu tabel dengan melakukan transformasi aritmatik pada key yang menjadi alamat dalam tabel tersebut. Key merupakan suatu input dari pemakai di mana pada umumnya berupa nilai atau string karakter.

Pelacakan dengan menggunakan Hash terdiri dari dua langkah utama, yaitu:

1. Menghitung Fungsi Hash

 Fungsi Hash adalah suatu fungsi yang mengubah key menjadi alamat dalam tabel. Fungsi Hash memetakan sebuah key ke suatu alamat dalam tabel. Idealnya, key-key yang berbeda seharusnya dipetakan ke alamat-alamat yang berbeda juga. Pada kenyataannya, tidak ada fungsi Hash yang sempurna. Kemungkinan besar yang terjadi adalah dua atau lebih key yang berbeda dipetakan ke alamat yang sama dalam tabel. Peristiwa ini disebut dengan collision (tabrakan). Karena itulah diperlukan langkah berikutnya, yaitu collision resolution (pemecahan tabrakan).

2. Collision Resolution

 Collision resolution merupakan proses untuk menangani kejadian dua atau lebih key di-hash ke alamat yang sama. Cara yang dilakukan jika terjadi collision adalah mencari lokasi yang kosong dalam tabel Hash secara terurut. Cara lainnya adalah dengan menggunakan fungsi Hash yang lain untuk mencari lokasi kosong tersebut.

 Fungsi Hash (dilambangkan dengan h(key)) bertugas untuk mengubah key menjadi suatu nilai dalam interval [0....LEVELSIZE-1], dimana "LEVELSIZE" adalah jumlah maksimum dari record-record yang dapat ditampung dalam tabel. Jumlah maksimum ini bergantung pada ruang memori yang tersedia. 

 Fungsi Hash yang ideal adalah mudah dihitung dan bersifat random, agar dapat menyebarkan semua key. Dengan key yang tersebar, berarti data dapat terdistribusi secara seragam dan collision dapat dicegah. Sehingga kompleksitas kinerja model Hash dapat mencapai O(1), di mana kompleksitas tersebut tidak ditemukan pada struktur model lain. 

KELEBIHAN DAN KELEMAHAN MODEL HASHING 

 Model Hash memiliki kelemahan pada saat penambahan dan penghapusan record. Diperlukan waktu untuk menstrukturisasi tabel Hash. Pada tabel Hash terdapat suatu daerah (akibat collision) kelebihan data (overflow). Untuk mencapai daerah tersebut, memerlukan waktu. Lamanya waktu disebabkan jika data diletakkan dalam disk atau tape. 

 Hal ini bisa diatasi dengan meletakkan keseluruhan data sampel secara utuh ke dalam memori. Namun ruang memori yang terbatas merupakan kendala tersendiri, karena data yang tersedia dalam kamus kata ini sangat besar (46.010 buah).

 Penghapusan suatu unsur dari tabel Hash dapat menimbulkan masalah. Penghapusan suatu key dapat menyebabkan key-key yang berikutnya tidak dapat diakses, karena stuktur tabel yang sudah ada menjadi berubah. Namun dalam pembuatan kamus kata, hal tersebut tidak perlu dikhawatirkan, karena program ini tidak membutuhkan suatu penghapusan. Semua data yang terdapat dalam "Basis Data Kamus Kata" (yang berarti berada dalam tabel Hash), bersifat permanen, sehingga tidak perlu penghapusan. 

PENANGGULANGAN COLLISION 

 Masalah yang biasanya terjadi adalah, data yang ada begitu besar dibandingkan dengan jumlah lokasi dalam tabel. Sangatlah sukar, bahkan tidak mungkin untuk menemukan fungsi Hash yang dapat mencegah collision. Oleh karena itu penanggulangan collision yang baik sangat penting dalam Hash agar bisa meminimalkan jumlah collision.

 Jika tabel Hash yang dimiliki berukuran T[0...LEVELSIZE-1], collision terjadi apabila lokasi T[h(key)] telah terisi pada saat ingin menyisipkan key. Oleh karena itu, harus ada suatu cara untuk menentukan lokasi lain dalam tabel Hash tersebut untuk menyimpan key. Collison resolution bertujuan untuk menentukan lokasi kosong tersebut.

Teknik-teknik collision yang ada diantaranya adalah:

è Separate Chaining

Teknik Separate Chaining merupakan suatu teknik untuk mengatasi collision dengan cara menggunakan daerah di luar tabel Hash dalam bentuk linier. Bentuk linier ini bisa berupa linked-list atau array. Urutan data pada daerah overflow bisa terurut atau random, tergantung cara penyisipan yang dilakukan.

è Open Addressing

Teknik Open Addressing adalah suatu teknik penyimpanan dalam tabel Hash yang membutuhkan ruang memori sangat besar. Open Addressing Hash menyimpan N data dalam tabel Hash yang berukuran LEVELSIZE dengan menggunakan tempat-tempat kosong untuk menangani collision resolution.

è Double Hashing

Teknik Double Hashing adalah suatu teknik penyimpanan dalam tabel Hash dimana jika terjadi collision, lokasi selanjutnya adalah lokasi sekarang + h(k). h(k) adalah suatu fungsi Hash yang berbeda dengan fungsi Hash yang pertama

KESIMPULAN 

 Dari rangkaian eksperimen yang telah diujikan, kami mendapat kesimpulan bahwa kecepatan dari suatu algoritme pencarian kata dipengaruhi oleh:

1. Fungsi Hash

Fungsi Hash yang mendekati ideal sangat menentukan kemerataan penyebaran kata pada tabel Hash, sehingga dapat meminimalkan jumlah collision yang terjadi. Fungsi Hash yang ideal adalah mudah dikomputasikan dan bersifat random untuk meminimalkan jumlah collision. Hasil random tersebut dicapai dengan cara memanfaatkan seluruh unsur dalam key dan memperhatikan semua urutan dalam key tersebut. Namun dalam pemanfaatan seluruh unsur dalam key dapat berakibat pada sulitnya komputasi fungsi Hash. Fungsi Hash yang kompleks akan menambah kompleksitas (bisa menyebabkan fungsi Hash tidak lagi linier) yang mengakibatkan penambahan running time pada saat perhitungan terhadap fungsi Hash. Dengan demikian, perlu dicari suatu algoritme Hash yang bagus.

2. Pemakaian Informasi Frekwensi

Algoritme Hash dengan memanfaatkan informasi frekwensi kata ternyata memberikan kontribusi besar dalam kecepatan waktu pencarian kata. Waktu keseluruhan pencarian kata yang diperlukan oleh algoritme dengan memanfaatkan informasi frekwensi adalah 0,056 detik. Hasil ini 65% lebih cepat dibandingkan dengan algoritme Hash yang tidak memanfaatkan informasi frekwensi (0,086 detik).

3. Hardware yang dipakai untuk melakukan running terhadap program

Dengan pemakaian hardware yang memiliki kinerja tinggi, maka running time terhadap program juga semakin cepat