Hashing, Hash Table and Binary Tree

• Hashing & Hash Table

Hashing merupakan teknik yang digunakan untuk mengubah sebuah string menjadi angka (kunci). Kumpulan karakter dalam sebuah string diubah dalam bentuk nilai/kunci yang lebih pendek yang mempresentasikan string original. Benefit yang kita dapatkan dari menggunakan Hashing adalah kita dapat mengakses database yang kita miliki lebih cepat sehingga memungkinan untuk melakukan proses yang lain. Hash Table merupakan table (array) dimana kita menyimpan string original. Indeks Hash Table merupakan kunci sedangkan nilainya merupakan string original.

Misalkan kita memiliki Array of String (randomstuff) berisikan Mayahi, Ozone, Lu, Add, Djanu. Kita bisa membuat Hash Table dari mengubah huruf pertama setiap String menjadi sebuah angka dari range 0 hingga 25.

• Hash Function

Berikut adalah metode hashing yang dapat kita gunakan dalam mengubah string menjadi kunci:

1. Mid-Square
String/Identifier dikuadratkan kemudian mengambil beberapa angka hasil kuadrat (yang berada ditengah) untuk dijadikan sebagai hash key


2. Division
Membagi String/Identifier menggunakan operasi Modulus (% || mod). Angka yang digunakan biasany merupakan bilangan primer.

Contoh: "ABCD" akan disimpan pada lokasi 76
Perhitungannya adalah 64(1+2+3+4) mod 97


3. Folding 
Partisi String/Identifier menjadi beberapa bagian, kemudian menjumlahkan bagian tersebut membentuk sebuah hash key


4. Digit Extraction
Mengambil beberapa bagian dari String/Identifier dan menjadikanny sebagai hash key
Contoh: Budi mempunyai nilai x yaitu 472659485, maka kita bisa mengambil angka genap sebagai hash key yaitu 42648

5. Rotating Hash
Gunakan metode Hashing seperti Mid-Square atau Division, kemudian membalikkan hash key dari belakang ke depan.
Contoh: Jika hash key adalah 438573976 maka rotated hash key adalah 679375834

<> Collision
Collision merupakan tabrakan antar hash key, dimana terdapat lebih dari 1 data yang memiliki hash key yang sama.

Linear Probing Method
(very bad search complexity)

Solusi apabila terjadi Collision adalah Linear Probing dan Chaining.
1. Linear Probing = Mencari tempat kosong dan mengisi string di lokasi tersebut.
Misalkan kita mempunyai Array of String (morerandom) yang berisikan Zul, Lu, Add, Djanu, Chotto, Alyx, Dedede

Linked List (Chaining)

 2. Chaining = Membuat Linked List dan menyambungkan string di slot yang sama

•  Binary Tree 

Tree merupakan struktur data non-linear yang mempresentasikan hubungan antar data. Konsep Tree adalah kumpulan dari 1 node atau lebih.

- Node yang berada paling atas merupakan root
- Node yang tidak memiliki child merupakan leaf 
- Node yang memiliki parent yang sama merupakan sibling
- Jika ada garis yang menghubungkan X ke Y, maka X merupakan ancestor dari Y dan Y merupakan descendant dari X

Binary Tree merupakan Tree dimana setiap node memiliki paling banyak 2 child.
C merupakan parent dari F dan G. F dan G merupakan child dari C.