hash table

Pengertian Hash Tabel

Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah table, Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).

Beberapa contoh operasi Pada Hash Tabel :

-        insert: diberikan sebuah key dan nilai, insert nilai dalam table

-        find: diberikan sebuah key, temukan nilai yang berhubungan dengan key

-        remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut

-        getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu

Struktur dan Fungsi pada Hash Tabel.

Hash table menggunakan struktur data array asosiatif yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut. Misalnya, terdapat data berupa string yang hendak disimpan dalam sebuah hash table. String tersebut direpresentasikan dalam sebuah field kunci k.

Cara untuk mendapatkan field kunci ini sangatlah beragam, namun hasil akhirnya adalah sebuah bilangan hash yang digunakan untuk menentukan lokasi record. Bilangan hash ini dimasukan ke dalam hash function dan menghasilkan indeks lokasi record dalam tabel.

k(x) = fungsi pembangkit field kunci (1)

h(x) = hash function (2)

Collision (Tabrakan)

Keterbatasan tabel hash menyebabkan ada dua angka yang jika dimasukkan ke dalam fungsi hash maka menghasilkan nilai yang sama. Hal ini disebut dengan collision.

contoh: Kita ingin memasukkan angka 6 dan 29.

Hash(6) = 6 % 23 = 6

Hash(29)= 29 % 23 = 6

Collision Resolution Open Addressing

1.     Linear Probing

Pada saat terjadi collision, maka akan mencari posisi yang kosong di bawah tempat terjadinya collision, jika masih penuh terus ke bawah, hingga ketemu tempat yang kosong. Jika tidak ada tempat yang kosong berarti HashTable sudah penuh.

2.     Quadratic Probing

Penanganannya hampir sama dengan metode linear, hanya lompatannya tidak satu-satu, tetapi quadratic ( 12, 22, 32, 42, … )

3.     Double Hashing

Pada saat terjadi collision, terdapat fungsi hash yang kedua untuk menentukan posisinya kembali.

Collision Resolution Chaining

1.     Tambahkan key and entry di manapun dalam list (lebih mudah dari depan)

2.     Kerugian: Overhead pada memory tinggi jika jumlah entry sedikit

3.     Keunggulan dibandingkan open addressing:

- Proses insert dan remove lebih sederhana

- Ukuran Array bukan batasan (tetapi harus tetap meminimalisir

collision: buat ukuran tabel sesuai dengan jumlah key dan entry yang diharapkan)