Hash Table
Hashing adalah teknik untuk memberi
identifikasi pada objek tertentu dari sekelompok objek yang mirip dengan objek
tersebut. Dengan begitu, kita dapat mengakses objek tersebut dengan cepat.
Ambil
contoh jika kita memiliki sebuah objek dan kita ingin memberi sebuah key
kepada objek tersebut. Untuk menyimpan nilai dari key tersebut, kita
dapat menggunakan array simpel dimana index dari array
tersebut dapat menjadi key (integer) dari objek yang ingin dicari.
Namun, ada beberapa kasus dimana nilai dari key sendiri cukup besar dan
tidak dapat digunakan langsung dari index array, dan kita harus
menggunakan hashing.
Hash
Table adalah tabel
(array) untuk menyimpan string awal. Ukuran dari hash table biasanya
beberapa kali lebih rendah dari total angka dari string, maka beberapa
string dapat mempunyai hashed-key yang sama.
Berikut
contoh source code dari menyatakan data dengan hash key serta
cara menentukan value dari key – nya.
Hash
string dapat dijadikan
key dengan beberapa cara yang disebut sebagai hash function. Cara
– cara tersebut termasuk :
A. Mid-square
B. Division
C. Folding
D. Digit Extraction
E. Rotating Hash
A. Mid-square
Cara mid-square
dapat digunakan dengan cara mencari sebuah value dari string dengan cara
apapun, lalu dari value tersebut kita akan memangkatkan dua dari value
tersebut. Dari hasil pangkat dua tersebut, diambil angka atau serangkaian angka
dari tengah” value tersebut untuk menjadi key - nya.
Contoh :
Value dari string: 717
Hasil
pangkat 2 dari value: 514.089
Key
yang
ditentukan: 40
B. Division (Paling sering digunakan)
Sama pada bagian awal mid-square,
kita perlu menentukan value sebagai pengidentfikasi string yang
ada. Dari value tersebut kita akan membagi value tersebut dengan
operator modulus. Di - modulus dengan siapa? Biasanya dengan
angka prima, dari besar tabel yang ada atau ukuran memori yang digunakan.
Contoh:
Ukuran Tabel: 97
String: “COBB”
Penghitungan value
string: (64*4 + 3 + 15 + 2 + 2) % 97 =
88
*64 adalah ASCII dari
‘A’, serta string terdiri dari huruf kapital saja
C. Folding
Folding adalah cara menentukan hash key
dengan membagi string yang ada menjadi beberapa bagian terlebih dahulu.
Setelah terbagi, kita dapat menemukan hash key dengan menambahkan value
yang terdapat dalam string.
Contoh:
Key: 321
Pembagian: 32 dan 1
Total: 33 -> menjadi value hash key
D. Digit Extraction
Serangkaian angka yang
telah ditentukan akan dianggap menjadi hash address dalam cara digit
extraction. Dari angka tersebut, kita akan memilih beberapa angka dari
serangkaian angka tadi untuk dijadikan hash key.
Contoh:
Hash address: 27.589
Ambil digit pertama, ketiga dan kelima,
lalu kita akan mendapatkan hash key dengan nilai 259.
E. Rotating Hash
Rotating hash adalah cara yang tidak dapat
digunakan tanpa melakukan cara lain terlebih dahulu. Mengapa? Karena rotating
hash diambil dari hash address yang dihasilkan oleh cara lain
seperti division atau mid-square. Setelah mendapatkan hash
address dengan cara rotating hash kita akan mendapatkan key
baru dengan cara memutar hash address yang ada.
Contoh:
Hash address: 20021
Hasil: 12002
Dari cara” tersebut,
kita dapat menemukan value key yang sama dari data yang berbeda. Masalah
ini biasa dikenal dengan nama Collision. Bagaimanakah kita dapat
mengatasi masalah ini? Terdapat dua cara yaitu Linear Probing dan
Chaining.
A. Linear Probing
Cara ini dapat dilakukan
dengan mencari tempat kosong selanjutnya dan menempatkan data yang ada di
tempat tersebut. Maksud dari tempat yakni key baru yang belum ditempati
data.
Contoh :
Linear probing memiliki kekurangan jika bertemu
dengan banyak collision. Karena dengan Linear Probing kita perlu
mencari tempat yang kosong untuk data baru. Jika terjadi banyak collision
maka proses mencari tempat kosong untuk data baru akan memakan waktu yang cukup
lama.
B. Chaining
Chaining dapat dilakukan dengan cara
menghubungkan 2 data yang memiliki key atau index yang sama.
Bagaimana cara menghubungkan 2 data yang berbeda dengan key yang sama?
Dengan cara Linked List yang telah kita bahas sebelumnya.
Binary Tree
Sebelum masuk ke dalam binary
tree, kita perlu membahas tree terlebih dahulu. Tree adalah
struktur data yang non-linear yang merepresentasikan hubungan antara objek
dalam data.
Tree terdiri dari satu atau lebih nodes.
Dari gambar diatas, kita mendapatkan
derajat dari tree tersebut adalah 3 karena hubungan terbanyak
yang dimiliki dalam tree tersebut adalah 3.
Derajat dari C adalah 2,
dan tinggi tree tersebut adalah 3.
Yang berada diatas
cabang disebut sebagai parent, contohnya adalah parent dari C
adalah A. Sebaliknya, yang berada pada bawah cabang disebut dengan children.
Contohnya adalah children dari B adalah E.
Sibling adalah sebutan untuk dua atau lebih
data berbeda yang berada di level yang sama dengan parent yang sama.
Contohnya adalah F dengan G.
Ancestor adalah parent dari parent
suatu data. Contohnya adalah ancestor dari F adalah A.
Yang berada di level 0,
atau data yang menempati tempat teratas dalam sebuah tree, disebut
sebagai root.
Binary tree adalah tree yang tiap node
yang ada dalam tree tersebut memiliki paling banyak 2 children. Node
yang tidak memiliki child disebut sebagai leaf.
Contoh Binary Tree
Binary tree terbagi menjadi 4 tipe. Perfect
binary tree, complete binary tree, skewed binary tree dan balanced
binary tree adalah tipe-tipe dari binary tree.
A. Perfect Binary Tree
Adalah binary tree yang semua node - nya antara kosong
atau memiliki tepat 2 anak.
B. Complete Binary Tree
Adalah binary tree yang seperti perfect
binary tree di semua level kecuali level terakhir, dimana level
terakhir akan selalu penuh dari kiri, sehingga tidak ada kekosongan di tengah
level namun dapat memilki leaf di bagian kanan maupun node yang
hanya memiliki 1 children. Perfect binary tree juga merupakan
salah satu complete binary tree.
C. Skewed Binary Tree
Adalah binary tree yang node – nya hanya memiliki 1 child.
D. Balanced Binary Tree
Adalah binary tree yang seimbang dalam suatu aspek. Contohnya
adalah height balanced binary tree. Dapat dikatakan height
balanced binary tree jika binary tree tersebut seimbang dari kanan
dan kiri. Atau, perbedaan tinggi dari kanan dan kiri tidak lebih dari 1.
Special Part
– Blockchain & Hash
Blockchain
adalah daftar terhubung yang berisi data dan pointer hash yang menunjuk
ke blok sebelumnya sehingga menciptakan sebuah rantai. Hash pointer
adalah sebuah pointer hash yang bukan hanya berisi alamat dari
blok sebelumnya, tetapi juga berisi hash dari data yang ada di dalam
blok sebelumnya. Dari hash pointer tersebut, blockchain mendapatkan
keamanan yang baik karena jika ada suatu data yang berubah, data lain yang ada
didalam rantai blockchain akan ikut berubah sehingga mudah dideteksi.
Sumber :
Binus University - Data Structure - Hashing and Hash Table, Trees & Binary Tree (L)
Comments
Post a Comment