HASHING TABLE

Hash Table

Hash table adalah sebuah table yang isinya adalah sebuah data yang berfungsi untuk memetakan nilai kunci unik untuk setiap baris menjadi angka lokasi record tersebut di dalam tabel. Hash tabel sendiri memiliki sebuah kelebihan yaitu waktu aksesnya cepat sehingga jika ada record yang di cari maka langsung terletak pada angka hash lokasi storage nya.

Fungsi Hashing

Sebenarnya fungsi hashing itu bebas, terserah kalian ingin mendefinisikannya seperti apa. Tapi, berikut adalah fungsi hashing yang di harapkan :

·        Untuk dua buah key yang sama, hasil hashing-nya selalu sama.

·        Memiliki kompleksitas rendah.

·        Meminimalkan collision (akan dijelaskan pada bagian selanjutnya).

Ada beberapa operasi pada Hash tabel :

·        - Insert

·        - Find

·       -  Remove

·       -  getIterator

Hash collision

Perhatikan bahwa jumlah kemungkinan kunci sangat banyak. Jika kunci adalah nama, jumlah kemungkinan nama tersebut sangat banyak, sedangkan jumlah sel dalam hash table terbatas. Hal ini bisa memungkinkan terjadinya collision.

Karena collision tidak mungkin terhindarkan, implementasi hash table harus menentukan apa yang harus dilakukan bila terjadi collision. Salah satu cara yang banyak dipakai yaitu dengan mengijinkan lebih dari satu nilai dalam satu lokasi. Umumnya hash table menggunakan struktur data linked list untuk menyimpan lebih dari satu nilai dalam satu lokasi yang sama.

Bila data akan dimasukkan ke dalam bucket yang sudah ada isinya (collision terjadi), maka operasinya tidak sesederhana pada kasus bucket kosong. Mari kita perhatikan animasi yang saya buat di bawah ini.

Ketika memasukkan data (insert), pada bucket yang tidak kosong maka perlu dilakukan operasi komparasi kunci untuk melihat apakah kunci yang sama sudah ada di bucket itu atau belum. Bila kunci yang sama ternyata ada di situ, artinya operasi insert berubah menjadi operasi update, yaitu mengubah data yang lama dengan yang baru. Bila kunci yang dimasukkan tidak ada di situ, maka kunci dan data yang dimasukkan akan disimpan di node paling akhir dari bucket tersebut.

Berikut ini cara-cara yang digunakan untuk mengatasi collision :

1.   Closed hashing (Open Addressing)

Close hashing menyelesaikan collision dengan menggunakan memori yang masih ada tanpa menggunakan memori diluar array yang digunakan. Closed hashing mencari alamat lain apabila alamat yang akan dituju sudah terisi oleh data. 3 cara untuk mencari alamat lain tersebut :

• Linear Probing
• Quadratic Probing
• Double hashing

2.   Open hashing

Pada dasarnya open hashing membuat tabel yang digunakan untuk proses hashing menjadi sebuah array of pointer yang masing-masing pointernya diikuti oleh sebuah linked list, dengan chain (mata rantai) 1 terletak pada array of pointer, sedangkan chain 2 dan seterusnya berhubungan dengan chain 1 secara memanjang.