Hashing Table & Binary Tree

A.  HASHING

Hash atau Hashing berarti memenggal dan kemudian menggabungkan. Hash menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Hashing digunakan sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan  data dan penghapusan data dapat dilakukan dengan cepat.

Fungsi Hash adalah suatu fungsi yang mengubah key menjadi alamat dalam tabel. Fungsi Hash memetakan sebuah key ke suatu alamat dalam tabel. fungsi hash juga digunakan pada algoritma enkripsi sidik jari digital (fingerprint) untuk mengautentifikasi pengirim dan penerima pesan.

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

·       Mid-square

·       Pembagian (paling umum)

·       Melipat

·       Ekstraksi Digit

·       Rotasi Hash

1.    Mid Square       : Kuadratkan string / identifier dan kemudian gunakan jumlah bit yang sesuai dari tengah kotak untuk mendapatkan hash-key. Jika kuncinya adalah string, itu dikonversi ke angka.

2.    Pembagian        : Membagi string / pengidentifikasi dengan menggunakan operator modulus. Ini adalah metode hashing integer yang paling sederhana x.

3.    Melipat             : Partisi string / identifier menjadi beberapa bagian, lalu tambahkan bagian bersama-sama untuk mendapatkan kunci hash

4.    Ekstrasi Digit    : Digit yang ditentukan sebelumnya dari nomor yang diberikan dianggap sebagai alamat hash.

5.    Rotasi Hash      : Gunakan metode hash (seperti metode pembagian atau mid-square). Setelah mendapatkan kode / alamat hash dari metode hash, lakukan rotasi. Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash baru.

B.  BINARY TREE

Binary Tree atau Pohon Biner adalah sebuah pohon dalam struktur data yang bersifat hirarkis (hubungan one to many). Tree bisa didefenisikan sebagai kumpulan simpul dengan setiap simpul mempunyai paling banyak dua anak. Secara khusus, anaknya dinamakan kiri dan kanan. Binary tree tidak memiliki lebih dari tiga level dari Root.

Binary tree adalah suatu tree dengan syarat bahawa 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 child (anak simpul), secara khusus anaknya dinamakan kiri dan kanan.

Pohon biner dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat. Dalam penyusunan yang rapat ini, jika sebuah simpul memiliki indeks i, anaknya dapat ditemukan pada indeks ke-2i+1 dan 2i+2, meskipun ayahnya (jika ada) ditemukan pada indeks lantai ((i-1)/2) (asumsikan akarnya memiliki indeks kosong).