Hashing table dan Binary Tree

Hash Table & Binary Tree

         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 satu

code 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:

http://muqoddasrengmadureh.blogspot.com/2013/01/algoritma-dan-struktur-data-hashing.html

https://selembardigital.com/apa-itu-hashing-di-bawah-tudung-blockchain/

http://panjiologi.blogspot.com/2017/11/tree-binary-tree-pohon-dan-pohon-biner.html

https://www.mahirkoding.com/struktur-data-binary-search-tree-bst/

http://dwiasihrahaayu.blogspot.com/2014/01/pohon-binar.html