Hash Tables & Binary Tree

Hash Tables

Hash tables adalah suatu bentuk data struktur yang berguna untuk memetakan suatu value dengan mengassignkan key ke value tersebut. Hash tables berguna lebih banyak untuk tujuan keamanan, karena esensi dari hash table adalah mengenkripsi suatu petunjuk dari sebuah data agar tidak mudah diakses.

Hash tables juga digunakan dalam berbagai bidang seperti blockchain, yang diimplementasikan saat kita melakukan transaksi menggunakan bitcoin. record-record transaksi tersebut akan di hash atau dienkripsi agar record transaksi tersebut aman dan tidak bisa diubah.

Bagaimana cara kita mengimplementasikan hash table di C? Akan kita coba dengan memasukkan string berikut ini kedalam hash table.

1. Bibi

2. Abi

3. Cindi

string tersebut akan kita implementasikan menjadi hash table dimana string tersebut akan disimpan kedalam indeks array. Bagaimana cara kita menentukan array indeks masing-masing string tersebut akan disimpan? Banyak sekali formula atau yang kita sebut hash function yang dapat kita gunakan untuk menentukan array indeks, tetapi untuk contoh kali ini kita akan menentukan indeks sesuai dengan karakter string yang pertama.

indeks 0 = a atau A

indeks 1 = b atau B

indeks 2 = c atau C

.

.

.

indeks 25 = z atau Z

jadinya string tersebut akan disimpan seperti ini:

Array[0] = "Abi"

Array[1] = "Bibi"

Array[2] = "Cindi"

Mari kita coba contoh lain. Kita akan coba memetakan value strings menggunakan formula dimana setiap karakter ascii dari string tersebut akan ditambahkan, setelah itu totalnya akan dimodulus ukuran array.

Berikut contoh codenya:

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#define tableSize 100 // ukuran array

// hash table

struct node{

char value[101];

int key;

}*temp = NULL;

struct node *array[tableSize];

void hash(char *val){

temp = (struct node*)malloc(sizeof(struct node));

int len = strlen(val);

int realValue = 0;

 // loop untuk menambahkan ascii tiap karakter val

for(int i = 0 ; i < len; i++){

realValue += val[i];

}

strcpy(temp->value, val);

temp->key = realValue;

realValue = realValue % tableSize;

array[realValue] = temp;

}

void print(){

for(int i = 0 ; i < tableSize; i++){

if(array[i] != NULL){

printf("value: %s\nkey: %d\nindex: %d\n\n", array[i]->value, array[i]->key, i);

}

}

}

int main(){

hash("stefan");

hash("halo");

print();

return 0;

}

Output:

value: halo

key: 420

index: 20

value: stefan

key: 641

index: 41

Nah dari contoh diatas dapat kita lihat, itulah contoh penggunaan hashing dalam hash tables, menggunakan hash function kita. Tetapi, dari contoh diatas ada kelemahan yang tidak terlihat. Apa yang akan terjadi jika kita memasukkan string baru dan keluar key yang sama dengan string yang sudah ada.

Sebagai contoh kita bisa melakukan:

hash("halo");

hash("ahol");

string kedua tersebut jika di hash menggunakan hash function milik kita akan menghasilkan key yang sama, yaitu '420'. Maka yang akan terjadi selanjutnya jika kita menjalankan function print(), yang akan muncul di layar adalah:

value: ahol

key: 420

index: 20

Yang muncul hanyalah satu saja yaitu "ahol" karena kita menghash string tersebut setelah "halo".

Nah, inilah yang disebut collisions dalam hash table. Collisions dalam hash table adalah suatu peristiwa dimana ada hasil enkripsi yang sama, sehingga tempat penyimpanannya pun sama. Ada beberapa cara yang bisa kita lakukan untuk menangkal masalah collision di hash table.

1. Linear Probing

Linear probing adalah satu cara yang bisa kita gunakan untuk menangkal collision. caranya mudah, jika kita menemukan suatu collision, kita harus mencari indeks yang kosong. Jadi jika pada contoh yang diatas "halo" berada pada indeks 20, dan sehabis itu kita akan menghash "ahol". dengan linear probing kita akan mencari indeks array yang kosong. Kebetulan saja indeks selanjutnya, indeks 21 tidak ada data, sehingga bisa kita gunakan untuk menyimpan data "ahol".

Berikut adalah snippet dari function hash diatas yang sudah dimodifikasi:

void hash(char *val){

temp = (struct node*)malloc(sizeof(struct node));

int len = strlen(val);

int realValue = 0;

for(int i = 0 ; i < len; i++){

realValue += val[i];

}

strcpy(temp->value, val);

temp->key = realValue;

realValue = realValue % tableSize;

if(array[realValue] == NULL){

array[realValue] = temp;

}

else{

while(array[realValue] != NULL){

realValue++;

}

array[realValue] = temp;

}

}

Nah jika kita menjalankan perintah:

hash("stefan");

hash("halo");

hash("alho");

print();

maka outputnya adalah:

value: halo

key: 420

index: 20

value: alho

key: 420

index: 21

value: stefan

key: 641

index: 41

2. Chaining

Chaining agak berbeda dengan linear probing, didalam chaining jika kita menemukan collision, maka kita akan menyimpannya di dalam block key yang sama tetapi dengan menggunakan linked list. 

Berikut adalah snippet yang sudah dimodifikasi berdasarkan chaining:

struct node{

char value[101];
int key;
struct node *next;
}*temp = NULL, *curr = NULL;


struct node *array[tableSize];
struct node *head[tableSize];
struct node *tail[tableSize];

void hash(char *val){

temp = (struct node*)malloc(sizeof(struct node));

int len = strlen(val);
int realValue = 0;

for(int i = 0 ; i < len; i++){
realValue += val[i];
}

strcpy(temp->value, val);
temp->key = realValue;
temp->next = NULL;

realValue = realValue % tableSize;

if(array[realValue] == NULL){
array[realValue] = temp;
head[realValue] = tail[realValue] = temp;
}
else{

curr = head[realValue];

while(curr->next != NULL){
curr = curr->next;
}

curr->next = temp;
temp->next = NULL;
tail[realValue] = temp;

}


}

jika kita menjalankan:

hash("stefan");

hash("halo");

hash("alho");
hash("haol");

print();

printf("hasil chaining:\n\n");

printf("value: %s\n", array[20]->next->value); // 20 karena indeks string "halo"

printf("key: %d\n", array[20]->next->key);

printf("value: %s\n", array[20]->next->next->value); 

printf("key: %d\n", array[20]->next->next->key);

maka outputnya:

value: halo

key: 420

index: 20

value: stefan

key: 641

index: 41

hasil chaining:

value: alho

key: 420

value: haol
key: 420

Binary Trees

Binary tree adalah suatu struktur data dimana data-data tersebut bisa digambarkan merupai pohon yang terbalik. Binary tree mengharuskan sebuah tree untuk mempunyai anak tidak lebih dari 2. Jika suatu tree mempunyai 3 anak atau lebih maka, tree tersebut bukan binary tree. BInary tree sangat berguna untuk menyimpan ordered data dimana data tersebut sudah disusun secara struktural.

Binary Tree

Binary tree terdiri dari banyak terminologi, antara lain:

• Root adalah titik dimana binary tree dimulai. Pada gambar diatas root dari binary tree tersebut adalah 8.
• Parent adalah titik yang mempunyai anak / children. Pada gambar diatas Parent adalah titik 8, 3, 10, 6, 14.
• Children adalah titik yang merupakan anak dari parent, salah satu contohnya adalah 3 dan 10 merupakan anak dari titik 8.
• Leaf node adalah titik yang tidak mempunyai anak, seperti contohnya titik 1.
• Siblings adalah titik yang mempunyai parent yang sama, 4 dan 7 merupakan siblings karena mereka mempunyai parent yang sama, yaitu 6. 
• Height of tree adalah tingkat kedalaman dari sebuah tree, seperti contoh, pada gambar diatas, tree tersebut memiliki kedalaman 4 level.

Ada juga banyak jenis-jenis Binary tree:

1. Perfect Binary Tree adalah jenis binary tree dimana semua parent memiliki 2 children dan level dari tree tersebut sama.

 

      2. Complete Binary Tree adalah jenis binary tree dimana semua parent harus memiliki 2

          children atau 1 children paling kiri, tetapi tree tidak harus dalam level yang sama.

       3. Balanced Binary Tree adalah jenis binary tree dimana kedalaman / tinggi anak kiri root

           dengan tinggi anak kanan root hanya boleh berselisih maksimal satu.

       4. Skewed Binary Tree adalah jenis binary tree dimana root hanya bisa memiliki anak kiri,  

           atau anak kanan.