GSLC

Hash Table & Binary Tree

Hash Table

Hashing

Sebelum mempelajari hash table kita harus mengetahui hashing terlebih dahulu. Hashing adalah sebuah teknik yang digunakan untuk menyimpan dan mengambil data dalam waktu yang cepat. Dalam kasus ini teknik hashing mengubah sebuah karakter string menjadi ukuran yang lebih kecil atau sebuah kunci yang merepresentasikan string aslinya. hashing juga dapat diartikan sebagai pembagian kunci ke sebuah array yang disebut hash table dengan menggunakan fungsi yaitu hash function.

Hash table

hash table merupakan suatu tempat atau array dimana digunakan sebagai tempat penyipanan string aslinya. di hash table kita menyimpan data sebagai array yang dimana setaip datanya memiliki sebuah indeksnya masing - masing. Jadi karena hal ini kita dapat mengakses data dengan sangat cepat. 

Operasi dasar pada hash table

1. Insert 
• diberikan sebuah key dan nilai, insert nilai pada table.
2. Find 
• diberikan sebuah key , temukan nilai sebuah key.
3. Remove
•  diberikan sebuah key , temukan sebuah key, menghapus key tersebut.
4. GetIterator 
• mengembalikan iterator,yang mengecek nilai satu persatu.

Hash Fucntion

fungsi - fungsi pada hash yaitu :

1. Mid - Square
• memiliki dua step untuk melakukannya yaitu :
• kuadratkan nilai pada sebuah key.
• ekstrak  ambil nilai tengah sejumlah r bits dari hasil kuadrat nilai pada step pertama.
• jika nilai merupakan string ini akan di ubah menjadi angka.
• Contoh 1 :
• nilai = 3121
• hasil kuadrat = 3121 * 3121 = 9740641
• nilai tengah = 9740641
• Contoh 2 :
• nilai  = 2121
• hasil kuadrat = 2121 * 2121 = 4498641
• nilai tengah = 4498641
2. Division
• membagi string / identifier dengan menggunakan operator modulo.
• ini merupakan hash function paling simpel.
• menggunakan rumus H(K) = K mod N
• dimana : 
• K = nilai pada key.
• N = pembagi nilai , biasanya bilang prima, ukuran memori yang digunakan.
3. Folding
• membagi string / identifier menjadi beberapa bagian, lalu jumlahkan semuanya untuk mendapatkan hash key.
• step dalam folding :
• membagi nilai key menjadi beberapa bagian
• jumlahkan bagian yang sendiri.
• contoh : 
• nilai = 5678.
• parts = 56 dan 78.
• sum / add = 124.
• hash key = 24. 
4. Digit Extraction
• digit yang sudah di tentukan sebelumnya dianggap sebagai hash address.
5. Rotation Hash
• Gunakan hash function lain untuk mendapatkan hash address
• Lalu lakukan rotasi.
• Contoh :
• hash address = 30312.
• hasil rotasi = 21303.
6. Collision
• Keadaan dimana ketika ada beberapa nilai pada sebuah key sama.
• untuk mengatasi hal tersebut ada 2 cara yaitu :
• Linear Probing
• cari tempat yang kosong lalu tempat kan salah satu nilai yang sama ke tempat kosong itu.
• hal ini mempunyai banyak kelemahan jika banyak nilai yang sam pada sebuah key.
• Chaining
• kita menyimpan nilai yang sama pada sebuah key ke sebuah linked list.

Implementasi Hashing Table pada Blockchain

implementasi hash table pada blockchain yaitu pada kriptographi hash. kriptographi hash ini digunakan untuk menghubungkan blockchain.

 Binary Tree

Tree 

• Suatu data structure yang non linear yang menggambarkan hubungan hierarki antara data dengan objek.
• Beberapa hubungan tree dapat dilihat di struktur direktori atau hierarki sebuah organisasi.
• Node di tree dapat disimpan dimana saja dan terhubung dengan pointer.

Konsep tree

Bagian pada suatu tree :

1. Root 
• Node yang berada paling atas.
2. Edge 
• Garis yang menghubungkan parent dan child.
3. Leaf 
• Node yang tidak punya child.
4. Sibling
•  Node yang mempunya parent yang sama.
5. Degree
•  total Sub tree pada sebuah node.
6. Height / Depth
•  Maksimum degree pada sebuah node.
7. Ancestor dan Descendant

Binary Tree

• Hampir sama dengan tree hanya bedanya kalau binary tree setiap node paling banyak memiliki 2 child.

Tipe tipe binary tree :

1. Perfect Binary Tree 
• Binary tree yang setiap levelnya memiliki depth yang sama.
  
2. Complete Binary Tree 
• Binary tree yang setiap levelnya kecuali yang terakhir semua telah terisi penuh dan setiap nodesnya paling panjang ke kiri.
  
3. Skewed Binary Tree 
• Binary tree yang dimana setiap nodesnya memiliki paling banyak satu child.
4. Balance Binary Tree 
• Binary tree yang dimana yang setiap leafnya sama jauhnya dari root.
  

Property binary tree :

1. Nodes maksimum di level k adalah 2^k.
2. Nodes maksimum  di binary tree dengan height h adalah -1+2^h+1.
3. Height minimum dari sebuah binary tree dengan nodes n adalah 2^log(n).
4. Height maksimum dari sebuah binary tree dengan nodes n adalah n - 1.

Representasi dari tree mengunakan 2 cara yaitu :

1. Array
   
2. Linked list
   

Pengekspresian konsep tree dengan notasi aritmatika : 

1. prefix.
2. prefix tranversal.
• di prefix kalian harus print terlebih dahulu baru proses childnya.
3. infix.
4. infix tranversal.
5. postfix.
6. postfix traversal.
• di postfix kalian print setelah proses childnya.