HASHING
TABLE
Pada
post kali ini saya akan membahas mengenai implementasi Hash Table dalam pembuatan
Blockchain. Sebelum itu kita harus tau apa itu Hash Table yang di dalamnya
terdapat Hash Function dan Collision. Saya akan membahas secara lengkap mengenai
semuanya itu pada blog kali ini.
Hash
Table adalah sebuah struktur data sebagai tempat kita menyimpan data. Hash
Table terdiri atas tabel dan fungsi yang bertujuan memetakan nilai kunci yang
unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut
dalam sebuah tabel.
Tujuan
dari Hash Table sendiri adalah untuk mempercepat pencarian kembali dari banyak
data yang disimpan. Namun pada kenyataannya, sering kali ditemukan angka hash
yang bertabrakan (collision) record-recordnya. Maka, untuk mengatasi hal ini diterapkan
Kebijakan Resolusi Bentrokan (Collision Resolution Policy). Kebijakan
ini berguna untuk menentukan lokasi record dalam tabel.
Operasi
pada Hash Table:
· Insert
= Penambahan data dalam tabel
int
hashtbl_insert(HASHTBL *hashtbl, const char *key, void
*data)
{
struct
hashnode_s *node;
hash_size
hash=hashtbl->hashfunc(key)%hashtbl->size;
node=hashtbl->nodes[hash];
while(node)
{
if(!strcmp(node->key,
key)) {
node->data=data;
return
0;
}
node=node->next;
}
//Jika tidak menemukan key yang sama
if(!(node=malloc(sizeof(struct
hashnode_s)))) return -1;
if(!(node->key=mystrdup(key)))
{
free(node);
return
-1;
}
node->data=data;
node->next=hashtbl->nodes[hash];
hashtbl->nodes[hash]=node;
return
0;
}
· Find
=
Pencarian data yang berhubungan dengan key
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;
}
· Delete/remove =
Penghapusan data setelah diberi key, kemudian menemukan nilai yang
berhubungan dengan key dan setelahnya akan dihapus.
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
Function
Teknik-teknik
pada Hash Function:
·
Division :
String yang kita input
akan dimoduluskan dengan sejumlah memori agar nilai (value) yang didapatkan
dari hasil modulus kemudian dijadikan indeks tempat nilai itu disimpan.
·
Mid-Square :
Setiap nilai yang kita
terima akan dipangkatkan dua. Jika memori hash kita ada 100, memori itu terdiri
dari 0-99 maka angka yang menjadi hash kita adalah 2 digit dari nilai tengahnya.
·
Folding :
Memecahkan nilai dari hash tersebut
menjadi beberapa bagian.
Collision
(Tabrakan)
Keterbatasan
table hash menyebabkan terdapat 2 angka yang jika dimasukkan ke dalam fungsi
hash menghasilkan nilai yang sama. Peristiwa ini disebut dengan Collision.
Misalkan
kita ingin menginput string floor dan float (hash-key : 5) dengan
huruf awal f. Di sini terdapat 2 hash index yang sama. Jika bentrok ini
dinamakan collision. Kejadian ini harus bisa ditangani.
Cara
penanganan collision:
· Collision Resolution Open Addressing
Menyelesaikan
collision dengan menggunakan memori yang masih ada tanpa menggunakan memori di
luar array yang digunakan. Cara ini mencari alamat lain apabila alamat yang
akan dituju sudah terisi data. Ada 3 cara untuk mencari alamat lain tersebut:
1. Linear
Probing
Apabila telah terisi,
linear probing mencari alamat lain dengan bergeser 1 indeks dari alamat
sebelumnya hingga ditemukan alamat yang belum terisi data, dengan rumus (h+1)
mod m.
2. Quadratic
Probing
Penanganannya hampir sama
dengan metode linear, hanya lompatannya tidak satu-satu, tetapi quadratic ( 12,
22, 32, 42, … ).
3. Double
Hashing
Alamat baru untuk
menyimpan data yang belum dapat masuk ke dalam table diperoleh dengan
menggunakan hash function lagi.
· Collision Resolution Chaining
Pada
dasarnya 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.
Kerugian:
- Overhead pada memory tinggi jika
jumlah entry sedikit.
Keunggulan
dibandingkan open addressing:
- Proses insert dan remove lebih
sederhana.
- Ukuran Array bukan batasan (tetapi
harus tetap meminimalisir collision.
IMPLEMENTASI HASHING PADA BLOCKCHAIN
Sebelum
masuk lebih dalam kita harus tahu apa itu blockchain. Blockchain adalah catatan
transaksi digital berdasarkan strukturnya, di mana catatan individu, yang disebut
blok, dihubungkan bersama dalam satu daftar, yang disebut chain (rantai). Blockchain
digunakan untuk mencatat transaksi yang dilakukan dengan cryptocurrency,
seperti Bitcoin dan memiliki banyak aplikasi lain.
Pada
era sekarang ini, kriptografi menjadi peran penting dalam jaringan blockchain
yang terus berkembang. Salah satunya adalah proses perhitungan sebuah data
secara konkret dan unik. Metode ini dikenal dengan Hash. Kode unik yang kita temukan dalam Blockchain itu menggunakan metode Hash.
Nilai
berharga sebuah data saat ini berpotensi dibobol atau diketahui oleh orang
lain. Salah satu teknik untuk mencegahnya ialah dengan pemberian kode unik.
Data
tersebut akan aman dan pastinya menjadi orisinalitas data dari orang lain.
Hanya orang yang terkait berhak dan bisa masuk ke akses data tersebut. Saat ini
beragam proses pengamanan data, mulai dari sidik jari, sidik mata, dan di sistem
Blockchain menggunakan kode unik (Hash).
Tak hanya itu saja, 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
berbeda tergantung spesifikasi Hash yang digunakan.
Sejumlah hash yang
digunakan saat ini karena fungsi dan keamanannya beragam dan memiliki kemampuan transaksi data yang cepat :
1. SHA256
SHA256
adalah hash pertama sekali muncul dan digunakan di jaringan blockchain publik.
Hash ini digunakan pada Bitcoin khusus proses transaksi dan perhitungan nilai
Hash. Pengguna ini sudah mulai dicetus sejak tahun 2001 oleh NIST (National
Institute of Standard and Technology).
SHA256
merupakan generasi kedua dari hash jenis Sha, penggunaan angka 256 karena dasar
data yang dihasilkan adalah 256 bit. SHA26 sendiri banyak digunakan oleh
berbagai sistem blockchain lainnya karena punya kapasitas mengirim yang relatif
kecil dan cepat. Terlebih lagi untuk proses transaksi besar.
2. RIPEMD160 (Race Integrity Primitive Evaluation
Message Digest)
Konsep
dari algoritma dari RIPEMD160 dikembangkan oleh MD4. Jumlah data transaksi yang
dihasilkan lebih kecil dibandingkan SHA256 yaitu hanya 160 bit.
Tentu
saja hal ini membuktikan RIPEMD lebih cepat dan bertenaga, sehingga proses pending
data berkurang. Peran utama yang diemban oleh RIPEMD160 adalah dengan membuat
alamat Bitcoin yang diakumulasi berdasarkan pada kunci publik.
3. Beragam Hash pada Monero
Pada Monero, penerapan pada keamanan data menggunakan sejumlah Hash, mulai dari Keccak, Blake, Grostl, JH, dan Skein pada CryptoNote. Konsep dari Monero yang sangat kompleks seakan membuatnya dijuluki sebagai fully anonymous.
Pada Monero, penerapan pada keamanan data menggunakan sejumlah Hash, mulai dari Keccak, Blake, Grostl, JH, dan Skein pada CryptoNote. Konsep dari Monero yang sangat kompleks seakan membuatnya dijuluki sebagai fully anonymous.
Monero
menilai bahwa perlu adanya keamanan khusus dan beragam pada Hash. Inilah yang
menjadi dasar lahirnya konsep CryptoNote. Pengguna yang mengirimkan transaksi
atau data tidak dapat diidentifikasi oleh publik karena ada beberapa kunci
tersebut.
Demikian penjelasan yang
dapat saya sampaikan mengenai Hash Table, Hash Function, Collision serta
pengimplementasian dan peran Hash pada jaringan Blokchain. Semoga bermanfaat.
