Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.
Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).
Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.
operasi yang terdapat pada hash table adalah
1. insert : diberikan sebuah key dan nilai, insert nilai pada table
2. find : diberikan sebuah key, temukan nilai yang berhubungan dengan key
3. remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
4. getIterator : mengambalikan iterator,yang memeriksa nilai satu demi satucode untuk insert:
int hashtbl_insert(HASHTBL *hashtbl, const char *key, void
*data)
{
struct hashnode_s *node;
hash_size hash=hashtbl->hashfunc(key)%hashtbl->size;
Penambahan elemen baru dengan teknik pencarian menggunakan linked lists
untuk mengetahui ada tidaknya data dengan key yang sama yang
sebelumnya sudah dimasukkan, menggunakan deklarasi berikut:
node=hashtbl->nodes[hash];
while(node) {
if(!strcmp(node->key, key)) {
node->data=data;
return 0;
}
node=node->next;
}
code untuk find:
void *hashtbl_get(HASHTBL *hashtbl, const char *key)
{
struct hashnode_s *node;
hash_size hash=hashtbl->hashfunc(key)%hashtbl->size;
node=hashtbl->nodes[hash];
while(node) {
if(!strcmp(node->key, key)) return node->data;
node=node->next;
}
return NULL;
}
code untuk remove:
int hashtbl_remove(HASHTBL *hashtbl, const char *key)
{
struct hashnode_s *node, *prevnode=NULL;
hash_size hash=hashtbl->hashfunc(key)%hashtbl->size;
node=hashtbl->nodes[hash];
while(node) {
if(!strcmp(node->key, key)) {
free(node->key);
if(prevnode) prevnode->next=node->next;
else hashtbl->nodes[hash]=node->next;
free(node);
return 0;
}
prevnode=node;
node=node->next;
}
return -1;
}
Hashing benar-benar mendasar dalam penciptaan teknologi blockchain. Jika seseorang ingin memahami apa itu blockchain, mereka pasti harus mengerti apa artinya hashing.
BINARY TREE
Pohon
(Tree)
adalah graf terhubung yang tidak mengandung sirkuit. Karena merupakan graf
terhubung maka pada pohon selalu terdapat path atau jalur yang menghubungkan
kedua simpul di dalam pohon. Pohon dilengkapi dengan Root (akar).
Pohon binar (binary tree) adalah himpunan simpul yang
terdiri dari 2 subpohon (yang disjoint / saling lepas) yaitu subpohon kiri dan
subpohon kanan.Setiap simpul dari pohon binar
mempunyai derajat keluar maksimum = 2.
Pendefinisian pohon
binar bersifat rekursif. Pohon binar acapkali disajikan dalam bentuk
diagram.
Sebuah pohon binar
T didefinisikan terdiri atas sebuah himpunan hingga elemen yang disebut
simpul(node), sedemikian sehingga :
a.T adalah hampa
(disebut pohon null) atau;
b.T mengandung
simpul R yang dipilih(dibedakan dari yang lain), disebut “akar: atau “roof”
dari T, dan simpul sisanya membentuk 2 pohon binary (subpohon kiri dan subpohon
kanan dari akar R).
Terminologi Pada Pohon Binar
Terminologi
hubungan keluarga banyak digunakan dalam terminology pada pohon binary.
Misalnya istilah anak kiri dan anak kanan, untuk menggantikan suksesor kiri dan
suksesor kanan , serta istilah ayah untuk pengganti prodesesor. Selain itu juga
istilah saudara (brother) yang diberikan kepada kedua simpul yang mempunyai
ayah yang sama. Jelas bahwa setiap simoul kecuali akar mempunyai ayah yang
tunggal.
Pohon Binar Lengkap
Setiap simpul
dari pohon binary paling banyak mempunyai dua anak. Suatu pohon binar T
dikatakan lengkap atau complete, bila
setiap tingkatnya kecuali mungkin tingkat yang terakhir, mempunyai semua
simpul yang mungkin yakni 21 simpul untuk tingkat ke-r, dan bila semua simpul
pada tingkat terakhir muncul dibagian kiri pohon. Jadi, pohon binary lengkap
dengan simpul, T adalah tunggal(dalam hal ini mengabaikan label simpul).
Pohon-2
Pohon Binar T
dikatakan pohon-2 atau pohon binar yang dikembangkan(extended binary tree) bila
setiap simpul mempunyai 0 atau 2 anak. Dalam kasus ini, simpul dengan dua anak
disebut simpul internal, sedanglan simpul tanpa anak disebut simpul eksternal.
Dalam diagramnya, seringkali diadakan perbedaan antara simpul internal dan
eksternal. Simpul internal digambar sebagai lingkaran, sedangkan simpul
eksternal sebagai bujur sangkar.
Penyajian Pohon Binar Dalam Memori
Kita dapat
menyajikan suatu pohon binary T dalam memori dengan dua cara. Cara pertama
adalah penyajian kait (link). Cara ini biasa digunakan. Ia analaog dengan
cara list berkaitan (linked list) ketika disajikan dalam memori. Cara kedua
adalah dengan menggunakan sebuah array tunggal disebut penyajian sekuensial T.
Kebutuhan utama
yang harus dipenuhi pada setiap penyajian T bahwa seseorang dapat mempunyai
akses langsung ke akar R dan T, bila diberikan sembarang simpul N, seseorang
harus dapat akses langsung ke anak dari N.
referensi:
