Hash table merupakan salah satu
struktur data yang digunakan dalam penyimpanan data sementara dengan cara penyimpanan
data menggunakan key value yang didapat dari nilai data itu sendiri.
Keuntunga Hash table :
-
Relatif
lebih cepat
-
Kecepatan
insert, delete dan search relative sama
-
Fungsi
sederhana
Operasi Pada Hash Table:
-
insert:
diberikan sebuah key dan nilai, insert nilai dalam table
-
find:
diberikan sebuah key, temukan nilai yang mempunyai hubungan dengan key
-
remove:
diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus
nilai tersebut
-
getIterator:
mengambalikan iterator,yang memeriksa nilai satu demi satu.
Pada penerapan hashing, terdapat beberapa
keadaan yang memungkinkan terjadinya tabrakan (collision). Ada beberapa cara
mengatasi collision :
1. Closed hashing (Open Addressing)
closed 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.
2. Double hashing
alamat baru untuk menyimpan data yang
belum dapat masuk ke dalam table diperoleh dengan menggunakan hash function
lagi. Hash function kedua yang digunakan setelah alamat yang dihasilkan oleh
hash function awal telah terisi tentu saja berbeda dengan hash function awal
itu sendiri.
3. Open Hashing
separate chaining membuat tabel yang
digunakan untuk proses hashing menjadi sebuah array of pointer yang
masing-masing pointernya diikuti oleh sebuah linked list, dengan chain (mata
rantai) 1 terletak pada array of pointer, sedangkan chain 2 dan seterusnya
berhubungan dengan chain 1 secara memanjang.
Teknik Hashing biasanya digunakan dalam
penerapan blockchain, sederhananya bisa dibilang itu adalah cara bagaimana
mensecure password and stuffs yang penting.
BINARY TREE
Pohon biner adalah pohon dengan
syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree dan kedua
subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap
node dalam binary tree hanya boleh memiliki paling banyak dua anak/child.
Binary Tree
dengan sifat bahwa semua left child harus lebih kecil dari pada right child dan
parentnya. Juga semua right child harus lebih besar dari left childserta
parentnya. Binary seach tree dibuat untuk mengatasi kelemahan pada binarytree
biasa, yaitu kesulitan dalam searching / pencarian node tertentu dalam binary tree.
Pada dasarnya operasi dalam binary search tree sama dengan Binary treebiasa,
kecuali pada operasi insert, update, dan delete.
A. Insert : Pada Binary Search Tree,
insert dilakukan setelah ditemukan lokasiyang tepat. (Lokasi tidak ditentukan
oleh user sendiri).
B. Update : Seperti pada Binary Tree
biasa, namun disini update akan berpengaruh pada posisi node tersebut
selanjutnya. Bila setelah diupdate mengakibatkan tree tersebut bukan Binary
Search Tree lagi, maka harus dilakukan perubahan pada tree dengan melakukan
perubahan pada tree dengan melakukan rotasi supaya tetap menjadi Binary Search
Tree.
C. Delete : Seperti halnya update,
delete dalam Binary Search Tree juga turut mempengaruhi struktur dari tree
tersebut.
Comments
Post a Comment