Hashing and Hash Table, Trees & Binary Tree

Pada kesempatan kali ini, saya akan membahas tentang Hashing and Hash Table, Trees & Binary Tree.

Hashing and Hash Table

Hashing

Hashing adalah suatu teknik yang di gunakan untuk mengidentifikasi objek tertentu dari sekelompok objek yang serupa dengan cara yang unik. Hashing dapat di gunakan dalam kehidupan kita, sebagai contoh :

• Di universitas, setiap mahasiswa memiliki NIM yang terdiri dari angka-angka yang berbeda amtar satu mahasiswa dengan mahasiswa yang lain. Saat kita ingin mencari data tentang seorang mahasiswa, kita dapat menggunakan NIM yang dimiliki oleh mahasiswa tersebut.

Hashing merupakan struktur data penting yang dirancang untuk menggunakan suatu fungsi khusus yang di panggil "The Hash Function" yang digunakan untuk memetakan nilai yang telah diberikan dengan kunci tertentu untuk akses ke elemen yang lebih cepat. Efisiensi dari pemetaan ini tergantung dari efisiensi dari "The Hash Function" yang digunakan.

Dalam hashing, string of characters di transformasikan ke dalam panjang nilai yang biasanya lebih pendek atau ke dalam kunci yang merepresentasikan/mewakili string yang asli. 

Hashing digunakan untuk mengindeks dan mengambil item di suatu database karena pencarian item lebih cepat untuk ditemukan dengan menggunakan hashed key yang lebih pendek daripada menemukan item tersebut menggunakan nilai asli.

Hashing juga bisa didefinisikan sebagai konsep mendistribusikan kunci(key) dalam suatu array yang disebut "Hash Table" dengan menggunakan fungsi yang telah ditentukan, yaitu "Hash Function".

Hashing di implementasikan dalam 2 langkah, yaitu:

1. Elemen dikonversikan kedalam suatu integer dengan menggunakan "Hash Function". Elemen ini dapat digunakan sebagai suatu index untuk menyimpan elemen asli yang jatuh ke hash table.

2. Elemen ini disimpan di hash table dimana dia bisa diambil dengan cepat menggunakan hashed key.

hash = hashfunc(key)

index = hash%array_size

Pada metode ini, hash tidak tergantung pada ukuran array dan kemudian dia akan dikecilkan menjadi suatu index (angka antara 0 dan array_size - 1) dengan menggunakan operator modulo (%).

Hash Table

Hash table adalah suatu struktur data yang digunakan untuk menyimpan keys/value pairs. Hash table menggunakan suatu hash function (fungsi hash) untuk menghitung suatu index ke dalam suatu array dimana suatu elemennya akan dimasukkan atau dicari. Dengan menggunakan suatu hash function yang baik, hashing dapat bekerja dengan baik pula.

Hash table adalah sebuah tabel yang berbetuk array dimana di dalamnya kita menyimpan string asli. Indeks dari tabelnya adalah hashed key sementara nilainya adalah nilai dari string asli. 

Ukuran dari hash table biasanya beberapa urutan yang besarannya lebih rendah daripada jumlah total dari string yang memungkinkan. Jadi, beberapa string mungkin akan memiliki kunci hash (hashed key) yang sama.

Operasi dasar yang ada dalam hash table :

• Search
• Insert
• Delete

Data item yang digunakan dalam hash table

struct DataItem {

   int data;

   int key;

};

Search Operation

struct DataItem *search(int key) {
   //get the hash
   int hashIndex = hashCode(key);

   //move in array until an empty
   while(hashArray[hashIndex] != NULL) {

      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];

      //go to next cell
      ++hashIndex;

      //wrap around the table
      hashIndex %= SIZE;
   }

   return NULL;     

}

Insert Operation

void insert(int key,int data) {
   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data;
   item->key = key;   

   //get the hash
   int hashIndex = hashCode(key);

   //move in array until an empty or deleted cell
   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
      //go to next cell
      ++hashIndex;

      //wrap around the table
      hashIndex %= SIZE;
   }

   hashArray[hashIndex] = item;     

}

Delete Operation

struct DataItem* delete(struct DataItem* item) {
   int key = item->key;

   //get the hash
   int hashIndex = hashCode(key);

   //move in array until an empty
   while(hashArray[hashIndex] !=NULL) {

      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex];

         //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem;
         return temp;
      }

      //go to next cell
      ++hashIndex;

      //wrap around the table
      hashIndex %= SIZE;
   }

   return NULL;     

}

Hash Function

Hash function adalah suatu fungsi yang mengubah nomor telepon yang besar menjadi nilai integer praktis yang kecil. Nilai integer yang dipetakan digunakan sebagai suatu index di dalam hash table. Sederhananya, suatu hash function memetakan sejumlah angka atau string yang besar kedalam suatu integer yang kecil yang dapat digunakan sebagai index di dalam hash table.

Hash function yang baik harus memiliki properti sebagai berikut :

1. Dihitung secara efisien
2. Harus mendistribusikan kunci(keys) secara seragam (setiap posisi tabel memiliki kemungkinan yang sama untuk setiap kunci)

Ada banyak cara untuk meng-hash suatu string ke dalam suatu key. Berikut ini adalah beberapa method-method penting untuk membangun fungsi hash :

• Mid-square
• Division (paling umum)
• Folding
• Digit Extraction
• Rotating Hash

1. Mid-square

Dalam mid-square, kita akan mempangkatkan semua nilainya. Singkatnya, semua nilai yang diberikan kepada kita akan kita pangkat 2 kan. 

Function : h(k) = s

keterangan :

k = key

s = hash key yang diperolah dengan memilih r bits dari k pangkat 2

Dalam teknik ini, semua nilai dari kunci(key) akan kita ambil dan kuadratkan. Kemudian, beberapa digit angka dari tengah akan kita ekstraksi. Angka-angka yang sudah diekstrak akan membentuk angka yang dapat kita ambil sebagai nilai kunci(key) baru. Teknik ini dapat menghasilkan key(kunci) dengan tingkat ke acakan yang tinggi jika nilai yang cukup besar yang kita ambil. Namun, hal ini tentunya memiliki batasan. Saat nilai dari kunci(key) kita kuadratkan, jika angka 6-digit diambil, maka hasil kuadrat dari angka tersebut akan memiliki angka sebanyak 12-digit. Ini akan melebihi kisaran tipe data integer. Jadi, jika terjadi overflow, gunakan tipe data integer yang panjang atau gunakan string sebagai perkalian jika luapan masih terjadi.

Contoh :

Misalkan diambil 4 digit benih.

Benih = 4765

Hasil kuadrat dari benih = 22705225

Dari angka yang berjumlah 8-digit ini, kita akan melakukan ekstraksi (Katakan, 4 tengah)

Jadi, nilai benih baru = 7052

Lalu, kuadratkan nilai dari benih baru (7052)

Hasil kuadrat nilai dari benih baru = 49730704

.

.

.

Proses seperti ini akan berlangsung sebanyak yang diperlukan dari suatu kunci.

2. Division

Pada teknik division, kita akan menggunakan operator modulus (%), dimana string/value yang diberikan akan kita moduluskan dengan sejumlah memori.

Function : h(z) = z % M

keterangan :

z = key

M = nilai yang digunakan untuk membagi kunci, biasanya menggunakan angka prima, ukuran tabel, atau ukuran dari memori yang digunakan.

Contoh :

z = 1276

M = 10

h(1276) = 1276 % 10

h(1276) = 6

nilai hash yang diperoleh adalah 6

Kekurangan dari method division ini adalah kunci yang berturut-turut akan memetakan ke nilai hash yang berturut-turut di dalam tabel hash. Ini akan menyebabkan kinerja yang kurang baik.

3. Folding

Folding akan memecahkan string/identifier menjadi beberapa bagian, lalu ditambahkan bagian yang bersama-sama untuk mendapatkan hash key.

Step-step yang akan dilakukan :

• Membagi nilai key kedalam beberapa bagian
• Tambahkan bagian individual (biasanya carry terakhir diabaikan)

Contoh :

Diberikan sebuah hash table dari 100 lokasi, hitung nilai hash dari 5678, 321, 34567. Dikarenakan terdapat 100 alamat lokasi, jadi kita akan bagi key kedalam beberaoa bagian dimana setiap bagian akan mengandung 2 digit.

4. Digit Extraction

Sebuah digit yang telah di tentukan sebelumnya yang berasal dari nomor yang diberikan, dianggap sebagai alamat dari hash.

Contoh :

Misal :

x = 14,568

Jika kita mengekstrak digit 1, 3, dan 5, kita akan mendapatkan kode hash 158.

5. Rotating Hash

Menggunakan method hash apa saja(seperti division atau mid-square method). Setelah mendapatkan kode/alamat hash dari metode hash, lakukan rotasi. Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash yang baru.

Contoh :

Misal :

Alamat hash yang diberikan = 20021

Hasil rotasi = 12002 (Folding pada digit)

Collision

Dalam bahasa indonesia, collision dikenal sebagai tabrakan.

Dikarenakan fungsi hash memberikan kita sebuah angka kecil untuk sebuah kunci(key) yang merupakan bilangan integer besar atau string. Ada kemungkinan bahwa dua kunci(key) menghasilkan nilai yang sama. Situasi dimana sebuah peta kunci (key map) yang baru, dimasukkan ke dalam sebuah slot yang sudah ditempati pada tabel hash disebut collision(Tabrakan) dan harus ditangani menggunakan beberapa teknik penanganan collision(collision handling technique).

Ada 2 cara untuk menangani Collision(tabrakan), yaitu :

1. Linear Probing
2. Chaining

Linear Probing

Dilakukan dengan mencari slot yang kosong yang terletak setelah slot yang terisi dan menaruh string nya disana. Dia akan mencari terus hingga mendapatkan slot yang kosong.

Contoh program Linear Probing :

struct { ... } node;

node Table[M]; int Free;

/* insert K */

addr = Hash(K);

if (IsEmpty(addr)) Insert(K,addr);

else {

/* see if already stored */

test:

if (Table[addr].key == K) return;

else {

addr = Table[addr].link; goto test;}

/* find free cell */

Free = addr;

do { Free--; if (Free<0) Free=M-1; }

while (!IsEmpty(Free) && Free!=addr);

if (!IsEmpty(Free)) abort;

else {

Insert(K,Free); Table[addr].link = Free;

}

}

Chaining

Dilakukan dengan menaruh string di dalam sebuat slot sebagai sebuah chained list(linked list).

Hash dan Perannya pada Sistem Keamanan Blockchain

Peran penting kriptografu dalam jaringan blockchain terus berkembang tiada henti. Salah satunya adalah proses perhitungan sebuah data secara konkret dan unik. Metode ini dikenal dengan Hash, kode unik yang banyak ditemukan di Blockchain adalah salah satu contoh Hash. Untuk menghindari sebuah data dibobol atau diketahui oleh orang lain adalah dengan pemberian kode unik. Dengan demikan, data tersebut akan aman dan pastinya menjadi orisinalitas data dari orang lain. Saat ini, beragam proses pengamanan data, mulai dari sidik jari dan sidik mata. Pada blockchain, digunakanlah kode unik(Hash).

Password atau kode unik di blockchain memiliki nilai karakter yang lebih panjang dan menggunakan kode yang unik sehingga proses peretasan dengan aplikasi tebak akan berlangsung sangat lama bahkan mustahil. Itulah yang menjadi alasan bahwa Hash sangat penting dan dinilai sangat aman.

Hash mampu mengubah setiap data yang mengalami perubahan dengan nilai unik sendiri. Ini yang tidak didapatkan pada jaringan biasa. Selain itu, setiap data dokumen dengan panjang berapa pun akan menghasilkan nilai hash yang punya nilai panjang yang berbeda, tergantung spesifikasi Hash yang digunakan.

1. SHA256

Merupakan Hash yang pertama sekali muncul dan digunakan di jaringan blockchain publik. Hash ini digunakan pada Bitcoin khusus proses transaksi dan perhitungan nilai Hash. Penggunaan SHA256 sudah mulai dicetus sejak tahun 2001 oleh NIST (NAstional Institute of Standard and Technology).

2. RIPEMD160

Merupakan singkatan dari Race Integrity Primitive Evaluation Message Digest. Konsepnya dikembangkan oleh MD4. Jumlah data transaksi yang dihasilkan lebih kecil dibandingkan SHA256 yaitu hanya 160 bit.

3. Beragam Hash pada Monero

Penerapan pada keamanan data menggunakan sejumlah Hash, mulai dari Keccak, Black, Grostl, JH, dan Skein pada CryptoNote. Kondep Monero yang sangat kompleks seakan membuatnya dijuluki sebagai fully anonymous. Monero menilai bahwa perlu adanya keamanan khusus dan beragam pada Hash menjadi dasar lahirnya konsep CryptoNote.

Tree and Binary Tree

Tree

Tree merupakan struktur data yang tidak linear yang digunakan untuk merepresentasikan data yang bersifat hirarki antara elemen-elemennya. Definisi tree yaitu kumpulan elemen yang salah satu elemennya disebut root(akar) dan elemen yang lain disebut simpul(node) yang terpecah menjadi sejumlah kumpulan yang tidak saling berhubungan satu dengan yang lain yang disebut sub-tree atau cabang.

Binary Tree

Tree yang unsurnya paling banyak 2 anak disebut Binary Tree. Karena setiap elemen dalam pohon biner hanya dapat emiliki 2 anak, biasanya anak tersebut akan dinamakan left dan right child.

Node dari Binary Tree berisi bagian-bagian, yaitu :

1. Data
2. Pointer to left child
3. Pointer to right child

Node yang tidak memiliki anak disebut leaf.

Jenis - Jenis Binary Tree

• Full Binary Tree

Binary tree yang tiap node-nya(kecuali leaf) memiliki 2 anak dan tiap sub-tree harus mempunyai panjang path yang sama.

• Complete Binary Tree

Mirip dengan Full Binary Tree, namun setiap sub-tree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

• Skewed Binary Tree

Binary tree yang semua nodenya (kecuali leaf) memiliki 1 child.

• Binary Search Tree(BST)

Jenis pohon terurut yang digunakan unruk menyimpan data sehingga memudahkan pencarian kembali data tersebut.

Operasi Pada Tree

• Create

DIgunakan untuk membentuk binary tree baru yang masih kosong.

• Clear

Digunakan untuk mengosongkan binary tree yang sudah ada.

• Empty

Diguakan untuk memeriksa apakah binary tree masih kosong.

• Insert

Digunakan untuk memasukkan sebuah node ke dalam tree.

• Find

Digunakan untuk mencari root, parent, left child, atau right child dari suatu node dengan syarat tree tidak boleh kosong.

• Update

Digunakan untuk mengubah isi dari node yang ditunjuk oleh pointer cureent dengan syarat tree tidak boleh kosong.

• Retrieve

Digunakan untuk mengetahui isi dari node yang ditunjuk pointer current dengan syarat tree tidak boleh kosong.

• Delete Sub

Digunakan untuk menghapus sebuah sub-tree (node beserta seluruh descendant-nya) yang ditunjuk pointer current dengan syarat tree tidak oleh kosong.

• Characteristic

Digunakan untuk mengetahui karakteristik dari suatu tree (size, height, serta everage length-nya).

• Traverse

Digunakan untuk mengunjungi seluruh node-node pada tree, masing-masing sekali.

Representation of Binary Tree

Implementation using linked list

struct node {

  int data;

  struct node *left;

  struct node *right;

  struct node *parent;

};

struct node *root = NULL;

Expression Tree Concept

Prefix  : *+ab/-cde

Postfix : ab+cd-e*

Infix  : (a+b)*((c-d)/e)

Kita juga akan menggunakan struktur ini untuk setiap node didalam tree :

struct tnode {

  char chr;

  struct tnode *left;

  struct tnode *right;
};

Threaded Binary Tree Example

Keuntungan

• Memungkinkan lintasan linear elemen di tree
• Tranversal linear menghilangkan penggunaan tumpukan yang pada gilirannya akan mengkonsumsi banyak ruang memori dan waktu komputer
• Memungkinkan untuk menemukan induk dari elemen yang diberikan tanpa menggunakan pointer parent secara eksplisit
• Karena node berisi pointer ke pendahulu dan penerus di in-order, tree berulir memungkinkan traversal maju dan mundur dari node seperti yang diberikan oleh mode in-order.

Contoh Coding Binary Tree

#include <stdio.h>

#include <stdlib.h>

//inisialisasi struct

struct data{

int number;

//pointer untuk menampung percabangan kiri dan kanan

data *left, *right;

}*root;

//fungsi push untuk menambah data

void push(data **current, int number){

//jika pointer current kosong maka akan membuat blok data baru

if((*current)==NULL){

(*current) = (struct data *)malloc(sizeof data);

//mengisi data

(*current)->number=number;

(*current)->left = (*current)->right = NULL;

//jika tidak kosong, maka akan dibandingkan apakah angka yang 

//ingin dimasukkan lebih kecil dari pada root

//kalau iya, maka belok ke kiri dan lakukan rekursif 

//terus menerus hingga kosong

}else if(number < (*current)->number){

push(&(*current)->left, number);

//jika lebih besar, belok ke kanan

}else if(number >= (*current)->number){

push(&(*current)->right, number);

}

}

//preOrder : cetak, kiri, kanan

void preOrder(data **current){

if((*current)!=NULL){

printf("%d -> ", (*current)->number);

preOrder(&(*current)->left);

preOrder(&(*current)->right);

}

}

//inOrder : kiri, cetak, kanan

void inOrder(data **current){

if((*current)!=NULL){

inOrder(&(*current)->left);

printf("%d -> ", (*current)->number);

inOrder(&(*current)->right);

}

}

//postOrder : kiri, kanan, cetak

void postOrder(data **current){

if((*current)!=NULL){

postOrder(&(*current)->left);

postOrder(&(*current)->right);

printf("%d -> ", (*current)->number);

}

}

//searching data

void search(data **current, int number){

//jika pointer current memiliki data

if((*current)!=NULL){

//cek, apakah datanya lebih kecil. Jika iya, belok ke kiri

if(number<(*current)->number){

search(&(*current)->left,number);

//jika lebih besar, maka belok ke kanan

}else if(number>(*current)->number){

search(&(*current)->right,number);

//jika sama dengan, maka angka ketemu

}else{

printf("Found : %d", (*current)->number);

}

//jika tidak ada data lagi (not found)

}else{

printf("Not Found.");

}

}

void main(){

push(&root, 11);

push(&root, 22);

push(&root, 13);

push(&root, 15);

push(&root, 9);

inOrder(&root);

printf("\n");

preOrder(&root);

printf("\n");

postOrder(&root);

printf("\n");

search(&root,91);

getchar();

}

Referensi :

https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/

https://www.geeksforgeeks.org/hashing-data-structure/
https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.html
https://www.geeksforgeeks.org/what-are-hash-functions-and-how-to-choose-a-good-hash-function/
https://arisistemberkas.blogspot.com/2018/10/teknik-hashing.html
https://www.geeksforgeeks.org/mid-square-hashing/
https://www.tutorialspoint.com/Hash-Functions-and-Hash-Tables
https://greatnusa.com/course/view.php?id=178
https://www.geeksforgeeks.org/hashing-set-2-separate-chaining/
http://muqoddasrengmadureh.blogspot.com/2013/01/algoritma-dan-struktur-data-hashing.html
https://steemit.com/indonesia/@iqbalsweden/hash-dan-perannya-pada-sistem-keamanan-blockchain
https://slideplayer.info/slide/12575320/
https://www.geeksforgeeks.org/binary-tree-data-structure/
http://bocahngoding.blogspot.com/2018/01/pengertian-tree-pada-struktur-data.html
https://www.slideshare.net/SsankettNegi/threaded-binarytreeheapsort
https://www.mahirkoding.com/struktur-data-binary-search-tree-bst/
Binus Maya Slides