Hashing
Apa sih hashing itu? Hashing adalah sebuah teknik yang digunakan untuk menyimpan dan mengambil kunci dalam waktu yang cepat atau singkat. Dalam hashing, string akan diubah menjadi string yang lebih pendek atau kunci yang merepresentasikan string awal. Hashing dapat diartikan sebagai konsep pembagian kunci dalam array (hash table) dengan fungsi yang telah ditentukan sebelumnya (hash function).
Oke, sekarang kita sudah tau apa itu hashing. Kalau gitu, hash table itu apa sih? Hash table adalah sebuah tabel (array) dimana kita menyimpan string awal (original string). Biasanya ukuran dari hash table lebih kecil dari jumlah total string. Jadi ada kemungkinan beberapa string memiliki hash key yang sama.
Gambar diatas menunjukan hash table dengan ukuran n = 10. Setiap posisi dari hash table disebut slot. Hash table tidak mengandung item, sehingga setiap slotnya kosong. Contoh, kita memiliki integer items {26, 70, 18, 31, 54, 93}. Salah satu cara yang paling umum untuk mentukan hash key adalah dengan cara:
Hash key = nilai key % jumlah slot
Cara diatas merupakan cara menentukan hash key dengan metode division. Dengan menggunakan cara tersebut, maka berikut adalah hasil dari hash key
Data Item
|
Hash Key
|
Hash Value
|
26
|
26 % 10 = 6
|
6
|
70
|
70 % 10 = 0
|
0
|
18
|
18 % 10 = 8
|
8
|
31
|
31 % 10 = 1
|
1
|
54
|
54 % 10 = 4
|
4
|
93
|
93 % 10 = 3
|
3
|
Setelah itu, kita masukkan ke dalam hash table
Selain menggunakan cara diatas, berikut merupakan metode yang dapat digunakan untuk membangun fungsi hash:
l Mid square
Kuadratkan nilai dari key, lalu ambil nilai tengah dari hasil kuadrat tersebut. Contoh: key = 3121, key2 = 9740641, bagian yang diambil = 406
l Division
Bagi string atau identifier dengan menggunakan operator modulus (seperti contoh diatas). Metode ini merupakan metode yang paling sering dipakai.
l Folding
Partisi string / identifier menjadi beberapa bagian, lalu menambahkan bagian-bagian yang ada untuk mendapatkan hash key.
l Digit Extraction
Digit yang telah ditentukan dari nomor yang diberikan dianggap sebagai alamat dari hash.
l Rotating Hash
Menggunakan metode hash apapun (seperti division, atau folding). Setelah mendapatkan hash code/alamat dari hash method, lakukan rotasi. Rotasi dilakukan dengan shifting digits untuk mendapatkan alamat hash yang baru.
Trees and Binary Tree
Salah satu materi dalam Data Structures yang paling penting adalah Tree. Tree biasa digunakan untuk mewakili data yang memiliki struktur hierarki antar elemen. Selain itu, Binary Tree adalah tipe spesial dari tree dimana setiap node antara tidak memiliki node, memiliki satu node atau dua node. Ada dua cara untuk mewakili binary tree, yaitu dengan menggunakan array dan dengan menggunakan linked list. Child node dalam binary tree di sebelah kiri disebut sebagai “left child node” dan child node di sebelah kanan disebut sebagai “right childe node”.
Pada gambar di atas, root node 8 (root merupakan node yang paling atas) memiliki 2 anak (3 dan 10), kemudian kedua child node bertindak sebagai parent node untuk child node 1 dan 6 (bagi left parent node) dan 14 (bagi right parent node) dan seterusnya.
Binary tree memiliki beberapa bentuk atau jenis, berikut merupakan beberapa contohnya:
l Full Binary Tree
l Complete Binary Tree
l Skewed Binary Tree
l Dan lain-lain
References:
Tidak ada komentar:
Posting Komentar