Hashing Table dan Binary Tree

Hashing Table

Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record(baris) menjadi angka(hash) lokasi record tersebut dalam sebuah tabel.

Adapun kelebihan dari hashing table antara lain sebagai berikut :

- Hash table relatif lebih cepat

- Kecepatan dalam insertions, deletions, maupun searching relatif sama

Berikut adalah fungsi hash yang umum digunakan :

1. Division Remainder Method (Metode Pembagian Bersisa)

Jumlah lokasi memori yang tersedi dihitung, kemudian jumlah tersebut digunakan sebagai pembagi untuk membagi nilai yang asli dan menghasilkan sisa. Sisa tersebut adalah nilai hashnya. Metode ini sering menghasilkan nilai hash yang sama dari dua atau lebih nilai aslinya atau disebut dengan bentrokan. Karena itu, dibutuhkan mekanisme khusus untuk menangani bentrokan yang disebut kebijakan resolusi bentrokan.

       2. Mid Square Hashing

Mid Square hashing adalah teknik hashing di mana kunci unik dihasilkan. Dalam teknik ini, nilai benih diambil dan dikuadratkan. Kemudian, beberapa digit dari tengah diekstraksi. Angka-angka yang diekstrak ini membentuk angka yang diambil sebagai benih baru. Kemungkinan tabrakan di tengah-tengah hashing rendah, tidak usang. Jadi, dalam peluang, jika tabrakan terjadi, itu ditangani menggunakan beberapa peta hash.

       3. Folding Hashing

Untuk mendapatkan alamat relatif, nilai key dibagi menjadi beberapa bagian, setiap bagian (kecuali bagian terakhir) mempunyai jumlah digit yang sama dengan alamat relatif. Bagian-bagian ini kemudian dilipat (seperti kertas) dan dijumlah. Hasilnya, digit yang tertinggi dibuang.

Berdasarkan hasil yang saya dapatkan di internet, Hash digunakan dalam penggunaan blockchain karena Blockchain, ada satu buah blok data yang diisi penuh, begitu penuh, data dienkrip (diubah menjadi bentuk huruf acak atau dikenal sebagai hash) dan hash (huruf acak)-nya dimasukkan ke dalam blok data berikutnya dan seterusnya.

Binary Tree

Binary tree adalah suatu tree dengan syarat bahwa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua anak simpul, secara khusus anaknya  dinamakan kiri dan kanan. Sebuah pohon biner berakar merupakan sebuah grafik yang mempunyai satu dari sudutnya dengan tingkat tidak lebih dari dua sebagai akar. 

Adapun istilah - istilah dalam binary tree yaitu :

1. Predesesor

    Node yang berada diatas node tertentu.

2. Succesor

    Node yang berada dibawah node tertentu.

3. Ancestor

    Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama. 

4. Descendant

    Seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.

5. Parent

    Predesesor satu level diatas satu node

6. Child

    Succesor satu level dibawah satu node

7. Sibling

    Node yang memiliki parent yang sama dengan satu node

8. Subtree

    Bagian dari tree yang berupa suatu node beserta descendant-nya

9. Size

    Banyaknya node dalam suatu tree

10. Height

    Banyaknya tingkat/level dalam suatu tree

11. Root

    Node khusus dalam tree yang tidak memiliki predesesor.

12. Leaf

    Node-node dalam tree yang tidak memiliki daun

13. Degree

    Banyaknya child yang dimiliki oleh suatu node