Hashing table & Binary Tree.

*HASHING TABLE* 

Apa itu Hasing Table? Sebelum masuk kedalam pengertian Hashing Table, ayuk pahami apa itu Hashing terlebih dahulu.

Apa itu Hashing?

Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. Dalam hashing, string karakter ditransformasikan menjadi nilai panjang yang biasanya lebih pendek atau kunci yang mewakili string asli.

Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya menggunakan nilai asli.

Hashing juga dapat didefinisikan sebagai konsep mendistribusikan kunci dalam array yang disebut tabel hash menggunakan fungsi yang telah ditentukan yang disebut fungsi hash.

PENGERTIAN HASH TABLE

Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain.

Fungsi Hash

Ada banyak cara untuk mengaitkan string menjadi kunci. Berikut ini adalah beberapa metode penting untuk membangun fungsi hash.

a. Mid-square

b. Divisi (paling umum)

c. Fold

d. Ekstraksi Digit

e. Rotasi Hash

Hash table menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Pada intinya hash table merupakan penyimpanan data menggunakan key value yang didapat dari nilai data itu sendiri. Dengan key value tersebut didapat hash value. Jadi hash function merupakan suatu fungsi sederhana untuk mendapatkan hash value dari key value suatu data. Yang perlu diperhatikan untuk membuat hash function adalah:

–       ukuran array/table size(m),

–       key value/nilai yang didapat dari data(k),

–       hash value/hash index/indeks yang dituju(h).

Hash Table pada Block Chain

Hashing berarti mengambil string input dengan panjang berapa pun dan memberikan output dengan panjang tetap . Dalam konteks cryptocurrency seperti Bitcoin, transaksi diambil sebagai input dan dijalankan melalui algoritma hashing (Bitcoin menggunakan SHA-256) yang memberikan output dengan panjang tetap.

*BINARY TREE*

Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lainnya (disebut subtree).

Ada beberapa istilah-istilah yang terdapat dalam Binary Tree, berikut adalah istilah-istilah tersebut

Jenis-jenis binary tree :

• Full Binary Tree

Full binary tree adalah binary tree yang tiap node-nya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.

• Complete Binary Tree

Complete binary tree adalah binary tree yang mirip dengan full binary tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

• Skewed Binary Tree

Skewed binary tree adalah binary tree yang semua node nya (kecuali leaf) hanya memiliki satu child.

• Binary search tree (BST)

Binary search tree (BST) adalah jenis pohon terurut yang digunakan untuk menyimpan data sehingga memudahkan pencarian kembali data tersebut.