Hashing, Hash Table and Binary Tree

Hashing, Hash Table and Binary Tree

Hashing
Hash atau Hashing berarti memenggal dan kemudian menggabungkan. Hash menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Hash merupakan suatu metode yang secara langsung mengakses record-record dalam suatu tabel dengan melakukan transformasi aritmatik pada key yang menjadi alamat dalam tabel tersebut.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 haruslah stabil (referential transparent), artinya, jika ia dipanggil dua kali oleh masukan yang benar-benar sama(sebagai misal,string yang mengandung sekuen karakter yang sama), maka ia haruslah memberi hasil yang sama pula.

Hash Function:
Beberapa contoh teknik hash function yang sudah ada:

1. Digit Selection / Truncation (Pemotongan)
   mengambil sebagian atau sepotong dari nilai kunci
   eg. 14110110033 diambil 4 digit dari tengah menjadi 1101.
2. Folding (melipat atau membagi)
   nilai kunci dibagi menjadi kelompok-kelompok yang sama besar,
   kemudian dijumlahkan.
   eg. 14110110033 dibagi 3 menjadi 1411, 0110, 033, lalu dijumlah
   (dalam kasus ini, 4 + 4 + 4 digit menghasilkan ukuran hash table
   9999 + 9999 + 999 size array yang dibutuhkan ~ 21.000 ).
3. Modular arithmetic / divisor (membagi/memodulus)
   nilai kunci di modulus sebuah pembagi (pembagi umumnya prima).
   nilai pembagi kemudian menjadi ukuran hash table.
   eg. 14110110033 % 1011 = 576, ukuran hash table 1011.
4. Multiplication (Perkalian)
   nilai kunci dikalikan sebuah angka (bisa juga dirinya sendiri),
   kemudian diambil beberapa digit (biasanya digit tengah).
   eg. 12345 * 12345 = 152399025, diambil tengah = 399.

Collision:
Beberapa teknik menghindari collision (data bertabrakan) yang sudah ada:

1. Open Addressing:
   Data dimasukkan ke index lain yang masih kosong.
   Jadul, tidak efektif, annoying, gajelas tujuannya.
   • Linear Probing
     telusuri table di sampingnya sampai ada tempat yang kosong. Bisa dimulai dari awal atau dari nilai yang didapat dari hash function.
   • Quadratic Probing
     telusuri table dengan men-skip index sesuai
     nilai kuadratik (1, 4, 9, 16, …).
   • Double Hashing
     apabila terjadi collision, data dimasukkan ke dalam
     hash function berikutnya (dan seterusnya).
   • Rehashing
     apabila hash table mendekati penuh (70%), akan dibentuk
     hash table baru yang ukurannya lebih besar, kemudian
     data yang ada dipindahkan ke hash table tersebut.
2. Separate Chaining:
   Metode mengatasi collision dengan menggunakan array of linked list.
   Metode ini mirip dengan radix sort. Pertama menyiapkan hash table
   berupa array of linked list. Kemudian apabila terjadi collision, maka
   data tersebut di link dengan data sebelumnya (dengan next dan prev).

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.



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.

Aturan main Binary Search Tree :

• Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya.
• Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya.

Lalu, ada 3 jenis cara untuk melakukan penelusuran data (traversal) pada BST :

• PreOrder : Print data, telusur ke kiri, telusur ke kanan
• InOrder : Telusur ke kiri, print data, telusur ke kanan
• Post Order : Telusur ke kiri, telusur ke kanan, print data