Hashing, Hash Table and Binary Tree Rangkuman

Hashing, Hash Table and Binary Tree

1.Hashing & Hash Table

Hashing adalah 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.Hash Table adalah table (array) untuk menyimpan string original. Indeks Hash Table merupakan kunci sedangkan nilainya merupakan string original.
 

Hash Function

   metode hashing yang dapat gunakan dalam mengubah string menjadi kunci:

1. Mid-Square
String/Identifier dikuadratkan setelah itu 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 adalah tabrakan antar hash key, dimana terdapat lebih dari 1 data yang memiliki hashkey yang sama.

Solusi apabila terjadi Collision adalah Linear Probing dan Chaining.
1. Linear Probing = Mencari tempat kosong dan mengisi string di lokasi tersebut.

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

2.Binary Tree 

 

Binary Tree adalah 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.

research about hashing table implementation in Blockchain. Is that used in current block chain technology?  


dari Research paper Blockchains Meet Distributed Hash Tables:Decoupling Validation from State Storage(Extended Abstract) http://ceur-ws.org/Vol-2334/DLTpaper4.pdf konklusi yang bisa diambil untuk saat ini implementasi hash table masih dalam prototipe dan  belum ada di teknologi block chain sekarang.