Hashing Table and Binary Tree

Hashing Table dan Binary Tree

Sebenarnya apa itu hashing?

Hashing adalah metode untuk menyimpang data dalam sebuah array agar penyimpanan data, pencarian data, penambahan data, dan penghapusan data dapat dilakukan dengan cepat serta dengan constant average time.

Hash Table adalah 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.

Kelebihan dari hash table antara lain sebagai berikut:

- Waktu aksesnya cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya.

- Hash table relatif lebih cepat.

- Kecepatan dalam insertions, deletions, maupun searching relatif sama. 

- Cocok untuk mempresentasikan data dengan frekuensi insert, delete dan search yang tinggi.  

Kekurangan dari hash table antara lain sebagai berikut:

- Seringkali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (berantakan).

- Sulit digunakan untuk mencetak seluruh elemen pada hash table.

- Tidak efisien untuk mencari elemen minimum ataupun maksimum.

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:

1. ukuran array/table size(m), 

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

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

Terdapat beberapa cara untuk mengubah string menjadi kunci, yaitu:

• Division
• Mid-Square
• Folding
• Digit Extraction
• Rotating Hash

Division:

Membagi string/identifier dengan menggunakan operator modulus. Biasanya modulo nya berupa ukuran dari table/array atau menggunakan bilangan prima terdekat diatas banyaknya data.

contoh :
string "ABCD" akan distore di dalam hash table yang memiliki size 97
QWER: (81 + 87 + 69 + 82 ) = 319
Totalnya adalah 319 kemudian dimodulus 97.

319 % 97 = 28
jadi kunci dari string "QWER" adalah 28 kemudian string tersebut distore di dalam hash table yang berindeks 28.

Mid-Square:

Mengkuadratkan string/identifier, kemudian mengambil beberapa angka dari hasil kuadrat (dari tengah) untuk dijadikan hash key.

Folding:

Membagi string/identifier menjadi beberapa bagian, kemudian jumlahkan bagian-bagian tersebut untuk mendapatkan hash key.

Digit Extraction:

Mengambil bagian dari string/identifier yang diberikan.

Contoh: x = 14567, jika kita mengambil angka ke 1 dan 3, kita akan mendapatkan hash key 15.

Rotating Hash:

Yaitu dengan menggunakan metode hash seperti division atau mid-square. Kemudian balikkan hash code.

Contoh: x= 12345 dibalik menjadi 54321.


Binary Tree adalah pohon khusus dimana disetiap node atau vertex bisa tidak memiliki cabang atau juga bisa memiliki 1 atau 2 cabang dan setiap cabang bisa bercabang lagi dan memiliki sifat yang sama. Binary tree digunakan untuk mewakili struktur data nonlinear. Pohon biner memiliki peran penting dalam software application dan salah satu hal paling penting dari Binary Tree adalah searching dalam algoritma.

Terdapat banyak operasi pada binary tree seperti:
Create, Clear, Empty, Insert, Find, Update, Retrieve, DeleteSub, Characteristic, Traverse.

Referensi:
https://www.academia.edu/25537608/TABEL_HASH_HASH_TABLE
https://informatika11d.wordpress.com/2012/11/22/struktur-data-hash-table/
https://www.slideshare.net/GRADhita/modul-praktikum-11-hashing-table