Hash Table & Binary Tree


Hashing

Pengertian hasing adalah suatu teknik yang dipakai untuk menyimpan dan mengambul kunci dengan cepat. Dalam hashing, string karakter diubah menjadi nilai yang panjang dan biasanya lebih pendek atau kunci yang mewakili string asli.

Hashing juga dapat diartikan sebagai sebuah konsep mendistribusikan kunci dalam array yang di sebut tabel hash menggunakan fungsi yang telah di tentukan yang disebut sebagai hash function

Hash Table

Pengertian hash table adalah suatu tabel tempat kita menyimpan sstring asli. Indeks tabel adalah hashed key sementara nilainya adalah string asli

Ukuran tabel hash biasanya terdiri dari beberapa urutan besarnya lebih rendah dari jumlah total string yang mungkin, sehingga beberapa string mungkin memiliki hashed key yang sama

Contoh
kita ingin menyimpan 5 string: define, float, exp, char, atan ke tabel hash dengan ukuran 26. hash
function yang akan kita gunakan adalah "mengubah karakter pertama setiap string menjadi angka antara 0..25 ”
(a akan menjadi 0, b akan menjadi 1, c akan menjadi 2, ..., z akan menjadi 25).

Hash Function

Pada hash function terdapat beberapa cara untuk mengaitkan string menjadi key. Berikut adalah beberapa cara untuk membangun hash function

* Mid-square

Kuadratkan string kemudian gunakan jumlah bit yang sesuai dari tengah kotak untuk mendapatkan hash-key.
Jika key nya adalah string, akan di konversi ke angka

   Langkah langkah:

   1. kuadratkan nilai pada sebuah key.

   2. ekstrak  ambil nilai tengah sejumlah r bits dari hasil kuadrat nilai pada step pertama.
Contoh
nilai = 3121
hasil kuadrat = 3121 * 3121 = 9740641
nilai tengah = 9740641   

* Division (most common)

Membagi suatu string dengan memakai operator modulus
Ini adalah metode hashing integer x yang paling sederhana

Function: h(z) = z mod M
z  = key

M = nilai yang digunakan untuk membagi key, biasanya menggunakan bilangan prima, ukuran tabel atau ukuran memori yang digunakan.

Contoh

"COBB" akan disimpan di lokasi

(64 + 3 + 64 + 15 + 64 + 2 + 64 + 2)% 97 = 88

* Folding

Metode folding berfungsi dalam dua langkah :
1. Bagilah nilai key menjadi sejumlah bagian di mana disetiap bagian memiliki jumlah digit yang      sama kecuali bagian terakhir yang mungkin memiliki angka lebih sedikit daripada bagian lain
2. Tambahkan bagian individual. Yaitu memperoleh jumlah part1 + part2 + ... + bagian n. Nilai hash yang dihasilkan dengan mengabaikan carry terakhir, jika ada.
Contoh
  Nilai = 34567
  Parts = 34,56, dan 7
  Sum = 34 + 56 + 7 = 97
  Hash value = 97

* Digit Extraction

Digit extraction adalah digit yang ditentukan sebelumnya dari nomor yang diberikan yang dianggap sebagai hash address
Contoh
  X = 14.568
  Jika kita mengekstrak digit 1,3, dan 5, kita akan mendapatkan hash code yaitu : 158

* Rotating Hash

Gunakan metode hash (seperti metode pembagian atau mid-square)

Lakukan rotasi

Contoh

 Diberikan hash address = 20021

 Hasil rotasi = 12002 

Impelemntasi Hash Table pada Block Chain

Implementasi hash table pada block chain terdapat pada kriptografi hash, yang berfungsi sebagai penghubung block chain

Binary Tree

Tree

Pengertian tree adalah suatu data structure non linear yang menggambarkan hubungan antara suatu data dengan objek.

Node di tree dapat disimpan dimana saja dan terhubung dengan pointer

Konsep tree :

1. Node yang paling atas di sebut root

2. Gari yang menghubungkan parent dan child disebut edge

3. Node yang tidak punya child disebut leaf

4. Node yang mempunyai parent yang sama disebut sibling

5. Total sub tree pada sebuah node disebut degree

6. Maksimum degree pada sebuah node disebut height / depth

7. Ancestor dan Descendant

Binary Tree

Mirip dengan tree hanya bedanya kalau binary tree di setiap node paling banyak memiliki 2 child

Tipe tipe Binary Tree

1. Perfect Binary Tree

   setiap levelnya memiliki depth yang sama

2. Complete BinaryTree

   setiap levelnya kecuali yang terakhir semua telah terisi penuh dan setiap nodenya paling panjang     kekiri

3. Skewed Binary Tree

   setiap nodenya memiliki paling banyak hanya satu child

4. Balance Binary Tree

   dimana setiap leafnya sama jauhnya dari root

Sumber : Power Point Binusmaya