HASHING AND HASH TABLE, TREES AND BINARY TREE

-HASHING AND HASH TABLE, TREES AND BINARY TREE-

Hashing adalah sebuah teknik yang dibuat dengan bertujuan untuk membuat nilai kunci unik agar menjadi hasil yang lebih pendek dan kecil. Hashing dibuat menjadi pendek dan kecil agar mudah dicari dan juga dilokasikan.

Hash Table adalah Tabel yang dibuat dan diisi oleh kunci hash ( index di hash table) dan juga string aslinya (value di hash table). Hash table memiliki beberapa kelebihan salah satunya adalah agar lebih cepat untuk dicari dan lebih mudah untuk dilokasikan. Hash table juga juga dapat memiliki angka/key hash yang sama tetapi terkadang angka hash yang sama bisa juga menjadi menjadi tubrukan. Biasanya ini diatasi dengan membuat kebijakan untuk hash nya.

Contoh:

dibawah ini adalah list dari nama mahasiswa yang ada di kelas 

Anton, Bella, Deni, Galih, Hasan.

dalam hash table yang huruf depannya ‘A’ akan mempunyai index 0, ‘B’  mempunyai index 1, ‘C’ mempunyai index 2, ‘D’ mempunyai index 3 dan seterusnya.

Maka tabel Hashnya akan menjadi  seperti ini :

 

Function Hash : Banyak sekali cara untuk Hashing tetapi cara yang paling pentingnya ada 5 yaitu :

1. Mid-square

Mid square adalah metode hashing dengan mengkuadratkan nilai atau valuenya. Apabila itu string akan dikonversikan ke angka. Sesudah di kuadratkan akan di ambil nilai tengah dari hasil pangkatannya.

Contoh :

Nilai = 1234

Nilai 1234 dikuadratkan menjadi 1522756

Nilai tengah dari hasil kuadrat tersebut adalah 227. Inilah hasil dari Mid-Square Hashing.

2. Division

Division adalah metode hashing yang paling mudah dan  juga metode yang paling terkenal. Caranya adalah dengan me-modulo.

Contoh :

Apabila dibuat tabel yang berisikan 10 dan ada 6 data yaitu 75, 16, 23, 62, 37, 21

Maka dengan division akan menjadi

75 mod 10 =  5 + 1 = 6. Maka data 75 akan dilokasikan ke 6

16 mod 10 =  6 + 1 = 7. Maka data 16 akan dilokasikan ke 7

23 mod 10 =  3 + 1 = 4. Maka data 23 akan dilokasikan ke 4

62 mod 10 =  2 + 1 = 3. Maka data 62 akan dilokasikan ke 3

37 mod 10 =  7 + 1 = 6. Maka data 37 akan dilokasikan ke 8

21 mod 10 =  1 + 1 = 6. Maka data 21 akan dilokasikan ke 2

3. Folding

Folding adalah metode hashing yaitu apabila kita mempunyai data, data akan di bagi 2 dan data yang kedua akan dibalik dan digabungkan dengan data yang pertama.

Contoh :

Ada data Nim mahasiswa yaitu: 235482, 415381, 654321

Maka:

235+284 = 519 maka data 235482 di lokasikan di 519

415+183 = 598 maka data 415381 di lokasikan di 598

654+123 = 777 maka data 654321 di lokasikan di 777

4. Digit Extraction

Digit Extraction adalah metode hashing yang men-ekstrak atau mengambil angka secara terpilih dari data.

Contoh :

Ada data Nim mahasiswa yaitu: 235482, 415381, 654321 dan yang diambil itu angka ke-1, ke-3, dan ke-6 maka:

235482 -> 252 maka data 235482 di lokasikan di 252

415381 -> 451 maka data 415381 di lokasikan di 451

654321 -> 641 maka data 654321 di lokasikan di 641

5. Rotating Hash

Rotating hash adalah metode hashing yang dapat menggunakan metode hashing lainnya sperti Digit Extraction atau Division dan memutarnya.

Contoh:

Apabila Hash yang sudah di division hasilnya 245638 maka hasil dari rotationnya adalah 836542

Collision

Collision adalah apabila nilai atau key-nya sama dan bertubrukan, cara menanggulanginya dapat dengan menggunakan Linear Probing atau Chaining

Linear Probing adalah apabila ada key hash yang sama maka akan ditempatkan di tempat index kosong yang terdekat

Chaining adalah apabila ada key hash yang sama maka akan ditempatkan  disampingnya sehingga membentuk rantai atau Linked list

Trees & Binary Tree

Tree adalah kumpulan dari beberapa node yang dihubungkan oleh pointer. Apabila diibaratkan, node yang paling atas dan mempunyai cabang disebut Parent(root), dan node yang menyambung dengan parent disebut children. Garis yang mengubungkan antara parent dengan childrennya disebut edge. Node yang tidang menyambung lagi atau tidak mempunyai children disebut leaf. Node yang menyambung ke parent yang sama disebut sibling. Dibuat seperti pohon keluarga.

Binary tree adalah tree yang dipastikan hanya memiliki children paling banyak hanya 2. Biasanya anaknya dibedakan dengan right child dan left child. Node yang tidak memepunyai anak disebut leaf. Binary tree paling banyak sampai level 3 atau tingginya 3 tingkatan.

Binary tree juga memiliki beberapa tipe

1. Perfect binary tree

Yaitu binary tree yang mempunyai 2 children yang bercabang dan rata antara yang kanan dan yang kiri.

Contoh:

2. Complete Binary tree

Yaitu binary tree yang mempunyai 2 children tetapi salah satu dari cabang terakhirnya tidak ada dan sisanya terisi semua.

Contoh :

3.Skewed Binary Tree

Yaitu binary tree yang hanya mempunyai paling banyak satu anak.

Contoh:

4. Balenced Binary Tree

Yaitu binary tree yang leaf kanan tidak lebih jauh dari root dengan leaf kirinya sehingga balenced.

Contoh :

Expression Tree

Adalah Binary tree yang mempunyai cabang adalah operatornya dan yang tidak mepunyai cabang atau (leaf) adalah operan(angkanya).

Expression tree mempunyai Prefix, postfix dan infix.

Prefix adalah expression yang operator nya ada terlebih dahulu sebelum operannya.

Contoh : *+WX-YZ

Postfix adalah expression yang operatornya ada di belakang dari operannya.

Contoh : WX+YZ-*

Infix adalah expression yang operatornya beradi di tengah operannya.

Contoh : (W+X)*(Y-Z)

Threaded Binary Tree adalah binary tree tetapi mempunayi pointer yang NULL di kanan dan di kirinya. Ini mempunyai beberapa kelebihan seperti dapat mengunnakan linear traversal dan dapat mengurangi penggunaan stacks sehingga tidak memakan memory yang banyak. Tetapi Threaded binary tree juga memiliki kekurangan seperti lebih sulit untuk membuat binary treenya dan lebih sering mendapat error apabila tidak ada children-nya atau nodenya menunjuk kepada ancestornya.

Contoh Threaded Binary Tree:

Hash Table dalam Block chain dan apakah digunakan dalam blockchain sekarang : Hash table dapat digunakan dalam blockchain karena keduanya (hash table & blockchain) menggunakan data structure yang terdistribusi dan dapat digunakan di dalam blockchain. Tetapi blockchain dan hash table memiliki tujuan yang berbeda, blockchain bertujuan untuk menyediakan data structure yang tahan dengan kerusakan dan untuk menyimpan data yang makin banyak tanpa adanya gangguan atau kerusakan, sedangkan Hash table tujuan utamanya adalah memberikan data structure yang lebih efisien dengan arti lebih cepat dalam mencari dan tidak memakan memory yang besar.

Linkled list dengan double pointer : apabila menggunakan double pointer maka kalau kita ingin merubah head / memperbaharui list, tidak perlu untuk mengembalikan head-nya lagi sedangkan kalau single pointer harus mengembalikan head-nya lagi

Contoh code dengan double pointer: