Hashing and Hash Tables, Tree & Binary Tree

HASHING AND HASH TABLES

• Hashing adalah teknik yang digunakan untuk menggunakan fungsi khusus yang dinamakan Hash function yang digunakan untuk memetakan nilai /objek dengan unique key tertentu untuk mengakses elemen dengan lebih cepat.
• Efisiensi dari pemetaan/mapping bergantung dari efisiensi dari fungsi yang digunakan.
• Dalam hashing, string characters biasanya ditransformasi ke nilai atau key yang lebih pendek yang menggambarkan original string tersebut.

• 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 didapatlah hash value.
• Kelebihan dari hash table antara lain sebagai berikut:
1. Hash table relatif lebih cepat
2. Kecepatan dalam insertions, deletions, maupun searching relatif sama
• Misal kita memiliki array dengan ukuran 13, maka hash function : h = k (mod 13).
• Dengan hash function didapat :

Gambar 1.0

• Maka data 13 akan disimpan pada index 0, data 25 akan disimpan di index 12, dst.
• Untuk melakukan pencarian kembali suatu data, maka cukup menggunakan hash function yang sama dan mendapat hash index yang sama juga.
• Misal : mencari data 27 --> h = 27 (mod 13) = 1

• Hash function dapat dibentuk dari beberapa metode:
1. Mid-square
• Teknik yang dilakukan dengan mengkuadratkan nilai string/identifier dan diambil nilai tengahnya sebanyak jumlah digit yang diinginkan. 
• Fungsi : h(k) = s
• k = key
• s = hash key
• Contoh:
• 
2. Division (paling sering digunakan)
• Teknik ini dilakukan dengan cara membagi string/identifier dengan menggunakan operasi modulus, kemudian sisa pembagiannya dijadikan alamat relatifnya.
• Fungsi : h(z) = z mod M
• z = key
• M = nilai untuk membagi key nya, biasanya bilangan prima, ukuran table, atau ukuran memori yang digunakan
• Contoh :
• 
3. Folding
• Teknik ini dilakukan dengan cara membagi key value ke beberapa bagian dan selanjutnya menjumlahkan semua bagian-bagian yang telah dipecah tersebut.
• Contoh :
• 
4. Digit Extraction
• Teknik yang dilakukan dengan menentukkan digit dari angka yang sudah diberikan dan dijadikan sebagai hash address.
• Contoh :
• - Misal x = 14.568
• - Jika yang di extract adalah nomor pertama, ketiga, dan kelima, maka hash code nya adalah : 158
5. Rotating Hash
• Teknik dengan memanfaatkan method division atau mid-square
• Setelah nilai hash code/address nya didapat, lalu dilakukan rotasi
• Misal :
• - Hash address yang sudah didapat : 20021
• - Hasil rotasi : 12002

• (Lihat gambar 1.0)
• Terdapat tabrakan (collision) pada k = 13 dan k = 39, dimana keduanya memiliki hash index yang sama, yaitu 0.
• Collision berarti ada lebih dari satu data yang memiliki hash index yang sama, padahal seperti yang kita ketahui, satu alamat / satu index array hanya dapat menyimpan satu data saja.
• Berikut ini cara-cara yang digunakan untuk mengatasi collision :
• Closed hashing (Open Addressing)
• Close hashing menyelesaikan collision dengan menggunakan memori yang masih ada tanpa menggunakan memori diluar array yang digunakan. Closed hashing mencari alamat lain apabila alamat yang akan dituju sudah terisi oleh data. Cara untuk mencari alamat lain tersebut antara lain :
• Linear Probing
• Apabila telah terisi, linear probing mencari alamat lain dengan bergeser 1 indeks dari alamat sebelumnya hingga ditemukan alamat yang belum terisi data, dengan rumus (h+1) mod m.
• Open hashing (Separate Chaining)
• Dalam chaining, tiap string di simpan dalam chain (linked list), sehingga jika ada collision, kita hanya perlu untuk iterate/pengulangan dari chain.

TREES & BINARY TREE

• Tree (pohon) adalah salah satu bentuk struktur data yang menggambarkan hubungan hierarki antar elemen-elemennya (seperti relasi one to many).
• Node pada tree tidak perlu disimpan secara berdekatan dan dapat disimpan di mana saja dan dihubungkan oleh pointer.

• Istilah umum dalam tree :
1. Predecessor : node yang berada diatas node tertentu
2. Successor : node yang berada di bawah 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 : Predecessor level di atas suatu node
6. Child : successor satu level di bawah suatu node
7. Sibling : node-node yang memiliki parent yang sama dengan suatu node
8. Subtree : bagian dari tree yang berupa suatu node beserta descendant nya dan memiliki semua karakteristik dari tree tersebut
9. Size : banyaknya node dalam suatu tree
10. Height : banyaknya tingkatan/level dalam suatu tree
11. Root : satu-satunya node khusus dalam tree yang tak punya predecessor
12. Leaf : node-node dalam tree yang tak memiliki successor
13. Degree : banyaknya child yang dimiliki suatu node

• Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah.

leaf = 2, 5, 11, 4

• Tipe-tipe binary tree :
• Perfect binary tree : pohon biner yang semua node leafnya berada pada kedalaman yang sama dari node root.

Depth = 4

• Complete binary tree : Mirip dengan perfect binary tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

• Skewed binary tree : binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.

• Implementasi binary tree menggunakan array

• Index di array menggambarkan nomor node
• Index 0 adalah root node
• Index left child adalah 2p+1, p adalah index parent
• Index right child adalah 2p+2
• Index parent adalah (p-1)/2

• Implementasi binary tree dengan linked list
• struct node {
    int data;
    struct node *left;
    struct node *right;
    struct node *parent;
  };
  struct node *root = NULL;

                    

• Expression tree concept
• Misal :

                     

• Prefix : *+ab/-cde
• Postfix      : ab+cd-e/*
• Infix          : (a+b) * ((c-d)/e)