HASHING, HASH TABLE, BINARY TREE

Hashing merupakan teknik untuk menyimpan data-data dan secara unik mengidentifikasi data tertentu dari sekelompok data serupa. Teknik hashing memudahkan saat ingin melakukan pencarian data karena teknik ini memetakan Hash Key dalam tabel Hash Table menggunakan fungsi yang sudah ditentukan yaitu Hash Function. Konsep hashing digunakan dalam database untuk menyimpan banyak data dan setiap data dimasukkan ke setiap index dalam Hash Table. 

Hash Function (Teknik Hashing) 

1. Mid - Square : Teknik ini menguadratkan key yang akan dimasukkan ke hash table, lalu mengambil angka tengah dari hasil yang sudah dikuadratkan sebagai hash key.

Contoh: 

Key = 3123

Hasil Kuadrat Key = 9753129

Key baru = 531

Jadi hash key yang disimpan adalah 531.

2. Division : Teknik ini mencari sisa bagi dari jumlah karakter yang ingin disimpan (ASCII).
Contoh: "PIPE" akan memiliki hash key (64+16 + 64+9 + 64+16 + 64+5) % 97 = 11.

3. Folding :  Teknik ini membagi key menjadi beberapa kelompok digit lalu dijumlahkan dan diambil beberapa digit dari hasil perhitungan untuk dijadikan hash key.
Contoh: 678 maka menjadi 67 dan 8. Hash key dari 678 adalah 67 + 8 = 75

4. Digit Extraction : Teknik ini mengekstrak digit key yang ditentukan untuk mendapat hash key.
Contoh:  76543 diextract digit ke 2,4, dan 5. Hash key menjadi 643 karena 6 merupakan digit ke 2, 4 merupakan digit ke 4, dan 3 merupakan digit ke 5.

5. Rotating Hash : Teknik ini dilakukan dengan menggeser digit terakhir ke paling awal untuk menjadi hash key.
Contoh: 500203, 3 digeser menjadi digit pertama, maka hash key menjadi 350020

Selain itu, teknik hashing untuk string dapat juga dilakukan dengan mengubah karakter paling awal dari setiap string menjadi index dalam hash table.

Contoh : String dengan awalan huruf A akan masuk ke index ke 0, string dengan awalan huruf B akan masuk ke index 1, string dengan awalan huruf C akan masuk ke index 2, dan seterusnya hingga string dengan awalan huruf Z akan masuk ke index ke 25 (total abjad ada 26).

Dalam penyimpanan data di hash table, setiap index dapat menyimpan lebih dari 1 data (Collision).
Collision berarti terdapat lebih dari satu data yang memiliki hash index yang sama, padahal seharusnya hanya satu index array yang hanya dapat menyimpan satu data. Untuk meminimalkan collision kita bisa gunakan hash function yang dapat mencapai seluruh indeks/alamat.

Terdapat 2 cara untuk mengatasi Collision:

1. Linear Probing (Open Addresing)
Yaitu mencari index lain dengan bergeser 1 slot selanjutnya.
Contoh: S adalah total index tabel. 
jika index ke x % S sudah terisi, maka coba index ke (x+1) % S.
jika index ke (x+1) % S sudah terisi, maka coba index ke (x+2) % S.
dan seterusnya.

Hash Function : Key mod 7
Keys : 50, 700, 76, 85, 92, 73, 101

sumber : https://www.geeksforgeeks.org/hashing-set-3-open-addressing/

2. Chaining
Yaitu setiap index hash table membuat linked list.

Hash Function : Key mod 7
Keys : 50, 700, 76, 85, 92, 73, 101

sumber : https://www.geeksforgeeks.org/hashing-set-2-separate-chaining/?ref=lbp

Kelebihan :
1. Mudah diterapkan.
2. Hash table dapat selalu menampung alamat baru karena dapat selalu menambahkan tempat.
3. Dapat digunakan ketika tidak diketahui berapa banyak alamat dan seberapa sering alamat dimasukkan atau dihapuskan dalam hash table.

Kekurangan :
1. Ada beberapa bagian dari hash table yang tidak pernah digunakan, sehingga memori yang sudah disediakan menjadi percuma.
2. Jika chain menjadi panjang, maka waktu pencarian juga menjadi lama.
3. Membutuhkan memori lebih untuk link.


Binary Tree
Binary tree merupakan salah satu struktur data dimana setiap simpul memiliki paling banyak 2 anak, yaitu anak kiri (left child node) dan anak kanan (right child node).
Node yang tidak memiliki anak disebut leaf.

sumber : https://www.tutorialspoint.com/data_structures_algorithms/tree_data_structure.htm

Root = Level 0
D adalah  parent node dari H dan I.
H dan I adalah child node dari D.
D, H, I adalah left sub-tree dari B.
E dan J adalah right sub-tree dari B.
Height / Depth dari tree adalah 4.
H, I, J, F, G disebut leaf.
H siblings dengan I.
F siblings dengan G.
Ancestor dari J adalah A, B, E.
Descendant dari B adalah D, E, H, I, J.

1. Perfect Binary Tree adalah binary tree yang setiap levelnya memiliki kedalaman yang sama.

sumber : https://www.w3schools.in/data-structures-tutorial/binary-trees/

2. Complete Binary Tree adalah binary tree yang setiap levelnya, kecuali yang terakhir, terisi semua dan semua node kiri terisi. Perfect binary tree disebut juga complete binary tree.

3. Skewed Binary Tree adalah binary tree yang setiap node memiliki paling banyak 1 child node.

sumber : https://www.geeksforgeeks.org/skewed-binary-tree/

4. Balanced Binary Tree adalah binary tree dimana perbedaan antara ketinggian subtree kiri dan subtree kanan pada setiap node tidak lebih dari satu.

sumber : https://algorithmsandme.com/is-bst-balanced/