Hash Table & Binary Tree

Hash Table

1. Definisi Hash Table
    Hash Table adalah struktur data yang memetakan kata kunci (hash) kepada sebuah elemen dalam table. Sehingga elemen yang dicari langsung berada pada kata kunci lokasi penyimpanannya. Namun pada kenyataannya sering ditemukan kondisi dimana kata kunci dua elemen atau lebih dapat bertabrakan (Collision).

2. Operasi - Operasi Dalam Hash Table
    Berikut adalah beberapa operasi yang dapat dilakukan dalam suatu hash table:

1. Insert
    Memasukan elemen ke dalam sebuah hash table
2. Lookup
    Mencari elemen dengan kata kunci
3. Remove
    Membuang elemen dengan kata kunci

3. Metode Hashing
    Berikut adalah beberapa cara untuk membuat key / hash dari sebuah kata kunci:

1. Lose Lose Algorithm
    Adalah suatu metode hashing yang sangat simple, yakni dengan menjumlahkan tiap byte dalam kata kunci. misal; "abc" = 294, dimana 'a' = 97, 'b' = 98, 'c' = 99. Metode tersebut bukanlah cara yang baik, karena Collision dapat dengan mudah terjadi.

2. FNV-1
   Fowler-Noll-Vo adalah metode hashing yang diciptakan oleh Glenn Fowler, Landon Curt Noll, dan Kiem-Phong Vo. Metode ini menggunakan Prime dan Basis dari FNV1. berikut adalah contoh pengaplikasiannya.

3. FNV-1a

    FNV-1a adalah variasi dari FNV-1 yakni dengan men-XOR kan byte_of_data terlebih dahulu baru dikalikan dengan FNV Prime.

4. Peran Dalam Blockchain

    Hash table memiliki peran penting dalam blockchain. blockchain menggunakan Distributed Hash Table. Distributed Hash Table (DHT) merupakan bentuk distribusi data Hash ke dalam jaringan peer to peer. yang mana di dalamnya memuat penyimpanan data, pencarian data, dengan penyimpanan berupa Key & Value Pair.

Binary Tree

1. Definisi Binary Tree

    Binary Tree adalah sebuah struktur data yang menyerupai sebuah Tree dan memiliki maksimal dua cabang pada tiap anaknya, yang biasa disebut anak kiri dan anak kanan. 

2. Operasi - Operasi Dalam Binary Tree

1. Insert

    Memasukan data kedalam Binary Tree, data yang dimasukan harus mengikuti aturan dalam Binary Tree yakni:

- tidak ada data yang bernilai sama.

- jika nilai data lebih kecil dari parent, maka data masuk ke anak kiri

- jika nilai data lebih besar dari parent, maka data masuk ke anak kanan

2. Delete

    Membuang data dalam Binary Tree, jika data yang dibuang memiliki anak, maka harus dilakukan salah satu dari dua cara untuk menyambungkan kembali anak tersebut, yakni dengan metode Predecessor atau metode Successor.

3. Print Semua Data

    Untuk mengeprint semua data ada tiga metode yang dapat dilakukan:

- Post-Order

- Pre-Order

- In-Order

Referensi :

- PPT Binusmaya

- Geeksforgeeks