Hashing and Hash Tables

Hashing

Hashing merupakan teknik untuk menyimpan dan mengambil key dengan cara yang cepat.

Dalam Hashing, string karakter akan diubah value yang lebih pendek, atau menjadi sebuah key yang merepresentasikan string yang asli.

Hashing juga dilakukan untuk mengambil data dari suatu database yang besar, karena mencari data yang diinginkan lebih mudah dengan menggunakan key daripada mencarinya menggunakan valuenya yang asli.

Hashing juga dapat didefinisikan sebagai konsep dari mendistribusikan key-key dalam suatu array yang disebut hash table menggunakan fungsi yang sudah ditentukan sebelumnya yang disebut hash function

Hash Table

Hash Table adalah tabel ( array ) dimana kita menyimpan string yang asli.

Contoh :

Kita mau menyimpan 5 string : define, float, exp, char, atan menjadi hash table berukuran 26. Hash function yang akan kita gunakan adalah "transform the first character of each string into a number between 0..25" ( a --> 0, b --> 1, c --> 2, ..., z --> 25)

Berikut adalah tabel dari permasalahan tersebut :

h[ ]	Value
0	atan
1
2	char
3	define
4	exp
5	float
6
…
25

    

atan disimpan di h[0] karena a adalah 0

char disimpan di h[2] karena c adalah 2

define disimpan di h[3] karena d adalah 3

dan seterusnya

kita hanya mengambil karakter pertama dari masing2 string

Hash Function

Ada banyak cara untuk meng-hash string menjadi sebuah key. Berikut adalah beberapa metode yang penting untuk membuat hash function.

• Mid-square
• Division ( ini merupakan fungsi yang paling umum)
• Folding
• Digit Extraction
• Rotating Hash

1. Mid-square

Kalikan kuadrat string / identifier lalu gunakan bits di tengah2 hasil perkalian kuadrat yang tepat untuk mendapatkan hash-key

Apabila keynya merupakan string, ubahlah ke angka

Langkah-langkah : 

1. Kalikan Kuadrat nilai dari key (k x k)
2. Keluarkan bits tengah dari hasil perkalian di langkah 1

Function : h(k) = s

k = key

s = hash key yang didapatkan melalui memilih bits tengah dari k2

  2. Division

Bagi string / identifier dengan operator modulus. Ini merupakan metode yang paling sederhana untuk meng-hash integer x

  3. Folding

Partisikan string / identifier menjadi beberapa bagian, lalu sambungkan bagian-bagian itu untuk mendapatkan hash key-nya

  1. Divide the key value into a number of parts

  2. Add the individual part (usually the last carry is ignored)

  4. Digit Extraction

Digit tertentu dari angka yang sudah diberikan akan dianggap sebagai hash address

Contoh : 

x = 14,568

Apabila kita extract digit ke-1, 3, dan 5, kita akan mendapatkan hash code 158

  5. Rotating Hash

Gunakan method hash apapun ( seperti division atau mid-square )

Setelah mendapatkan hash code atau alamat dari hash method, lakukan rotasi

Rotasi dilakukan dengan menggeser digit-digit untuk mendapatkan hash address yang baru

Contoh :
hash address : 20021

hasil rotasi    : 12002 (digit-digit tersebut difold)

Collision

Apabila kita memilikki hash function : define, float, exp, char, atan, ceil, acos, floor.

Collision terjadi apabila ada beberapa string yang memilikki hash-key yang sama 

Ada beberapa string yang memilikki hash-key yang sama, seperti : atan, acos, char, ceil, float, floor.

Ada 2 cara yang dapat kita lakukan : 

  1. Linear Probing

h[ ]	Value
0	atan
1	acos
2	char
3	define
4	exp
5	float
6	ceil
7	floor

Ini merupakan hash-table dari string-string tersebut, ceil diletakkan di h[6] dan floor diletakkan di h[7] karena char sudah ada di h[2] dan float sudah ada di h[5], maka ceil dan floor diletakkan di slot yang kosong

h[ ]	Value	Step
0	atan	1
1	acos	2
2	char	1
3	define	1
4	exp	1
5	float	1
6	ceil	5
7	floor	3

Linear probing tidak efektif apabila banyak collision yang terjadi, tabel di atas (step) menunjukan berapa looping yang diperlukan untuk mencari string tersebut

  2. Chaining

0	atan --> acos
1	NULL
2	char --> ceil
3	define
4	exp
5	float --> floor
6	NULL
7	NULL

Dalam chaining, kita menyimpan setiap string di linked list, jadi apabila ada collision, kita hanya peru mengulang di chain itu