GSLC

Hash Table & Tree

Hashing
Hashing adalah transformasi aritmatik sebuah string atau karakter
menjadi nilai yang merepresentasikan string aslinya.

Hashing digunakan sebagai metode untuk menyimpan data di dalam
sebuah array agar penyimpanan, penambahan, dan pencarian data
dapat dilakukan dengan benar.

Hash Table
Hash table adalah table (array) dimana kita menyimpan suatu string asli,
dimana index dari array adalah suatu kunci yang dienkripsi (hashed key
), namun nilainya adalah string yang asli.

Hash table biasanya terdiri dari berbagai macam urutan,
namun biasanya lebih sedikit dari berbagai kemungkinan string. Jadi,
beberapa string kemungkinan mempunyai hashed key yang sama.


Hash Function
Hashing adalah salah satu bagian penting dari data structure dimana
didesain oleh suatu fungsi yang dinamakan hash function yang
digunakan untuk memetakan suatu nilai dengan suatu ciri yang spesifik
untuk akses elemen yang lebih cepat.
Misalkan untuk fungsi H(x) akan memetakan nilai x yang disimpan di
index x%10, maka data {11,13,15,17,19 } akan disimpan secara
berturut-turut akan disimpan di index { 1,3,5,7,9 } di dalam array.

Beberapa metode untuk membuat Hash Function :
- Mid – Square
- Division
- Folding
- Digit Extraction
- Rotating Hash

-Mid-Square
Function: h(k) = s
k = key
s = hash key yang diperoleh dari nilai tengah kuadrat k
 kuadratkan string/identifier (k), lalu kita ambil angka tengah dari
kuadrat string/identifier untuk dijadikan hash key (s)
-Division
Function: h(z) = z mod M
z = key
M = angka yang digunakan untuk membagi key
 ketika ingin memunculkan index dan meletakkan key di index hasil
function division
-Folding
 bagi key menjadi beberapa bagian
 jumlahkan bagian individualnya
-Digit Extraction
 beberapa bagian digit dari key akan dijadikan hash address
-Rotating Hash