Hash Table

1. Hash Table

• Hashing adalah teknik yang digunkan untuk menyimpan dan mengambil kunci dalam jangka waktu  yang cepat. 

• Dalam hashing, sebuah data misalnya string dapat diambil bagiannya(karakter) kemudian dijadikan key untuk disimpan pada table

• Hashing menggunakan indek untuk mengambil data pada penyimpanan untuk mempercepat pencaharian menggunakan hashed yang lebih pendek daripada nilai yang sebenarnya(lebih panjang).

• Hashing juga bisa disebut konsep mendistribusikan indeks kedalam sebuah hash table menggunakan fungsi yang disebut hash function.

2. Hash Function
Ada banyak cara hashing string menjadi key.
- Mid-Square
- Division
- Digit Extraction
- Rotating Hash

-Mid-Square 
   Key yang didapat dikudratkan kemudian diambil bagian tengah dari key 
   contohnya: key 3121 di kuadratkan menjadi 9740641 sehingga diambil bagian tengahnya 406
   Penggunaan kuadrat agar address yang didapatkan itu berbeda meskipun nilai keynya berdekatan. Pada praktiknya lebih efisien memilih pangkat 2 untuk ukuran tabel dan mengekstrak bagian tengah dalam representasi bit dari key yang dikuadratkan. Bagian tengahnya dapat di ekstrak dengan operasi mask dan shift.  
- Division
   Membagi String atau identifier dengan operator modulus. Ini adalah cara sederhana mendapatkan hash key. Penggunaan modulus ini agar address yang diinput dapat kita kendalikan indexnya. Misalnya kita memiliki hash table dengan ukuran 10 sehingga jika kita memasukkan nilai pada hash table cukup di modulus 10 sehingga address yang didapat tidak melebihi 10.
-Folding 
     Membagi string/identifier menjadi beberapa bagian, kemudian menggabungkannya untuk mendapat hash key. Contohnya kita memiliki hash table dengan 100 lokasi, kemudian diberikan hash value 5678,321. Karena cuman ada 100 lokasi sehinggan kita akan membaginya dimana setiap bagian memiliki 2 digit. 5678 dibagi menjadi 56 dan 78 kemudian dijumlahkan menjadi 134 maka didapatkan hash value 34 dengan mengabaikan 100-nya.
- Digit Extraction
     Mengambil digit yang ditentukan sebagai hash address. Contohnya 14568, jika kita mengekstrak digit ke 1,3,5 maka kita akan mendapatkan hash code 158.
- Rotating Hash
       Langkah-langkahnya:
       1. Gunakan hash method apapun
       2. Setelah mendapat hash code/address dari hash method, lakukan rotation
       3. Rotation dilakukan dengan meng-shift digit untuk mendapatkan hash address baru.
       Contoh : hash address = 20021, hasil rotasinya 12002 (folding)

3. Collision
    Collision adalah kondisi dimana data yang mau kita simpan memiliki hash key yang sama sehingga terjadi collision. Cara mengatasinya adalah denga Linear Probing yaitu mencari slot kosong selanjutkannya dengan pindah ke indeks selanjutnya. Chaining, menempatkan data dalam linked list sehingga datanya dinamis.

Source Code Hash Table:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 15

struct Data{
char key[100];
int value;
Data *next;
}*head[SIZE], *tail[SIZE];

Data *newData(char key[], int value){
Data *temp = (Data*) malloc (sizeof(Data));
strcpy(temp->key,key);
temp->value= value;
temp->next=NULL;
return temp;
}

//fungsi untuk mendapatkan nilai index dengan hashing. Metode yang digunakan adalah division
int getHash(char key[]){
int hash=0;
for(int i =0;i<strlen(key);i++){
hash += key[i];
}
return hash;
}

void insert(char key[], int value){
//Cara mengatasi collision dengan metode chaining dengan menyambungkan valuenya //dengan linkedlist
Data *curr= newData(key,value);
int index = getHash(key) % SIZE;
if(head[index]==NULL){
head[index]=curr;
}
else{
Data *temp = head[index];
while(temp->next){
temp=temp->next;
}
temp->next=curr;
}
}

void display(){
for(int i=0;i<SIZE;i++){
if(head[i]!=NULL){
Data *temp = head[i];
while(temp){
printf("%s %d ", temp->key, temp->value);
temp= temp->next;
}
printf("\n");
}
else{
printf("- \n");
}
}
printf("\n");
}

Data *get(char key[]){
int index = getHash(key) % SIZE;
Data *temp = head [index];
while(temp!=NULL && strcmp(key, temp->key)!=0){
temp=temp->next;
}
return temp;
}

int main(){
insert("A",20);
insert("a",21);
    insert("TeST",11);
    display();
    
    Data *found = get("a");
    if(found == NULL) printf("no data found\n");
    else{
    printf("Found: %d", found->value);
}

}

Implementasi Hashing pada Blockchain

Transaksi dimasukkan sebagai input kemudian outputnya adalah kode unik dengan panjang yang tetap . Contoh algoritma hashing yang dipakai adalah SHA-256 (secure hashing algorithm) sehinggan output memiliki panjang 256. Hash function yang digunakan untuk kriptografi disebut Cryptographic Hash Function. Cryptographic hash function memiliki beberapa properti yaitu:
1. Detetministic : berapa kalipun kita memasukkan data yang sama, outputnya tetap sama
2. Quick computation : proses output harus cepat agar sistem efisien
3. Pre-image Resistance : infeasible artinya tidak bisa menentukan input data dari output
4. A Small Change in input changes the output : perubahan kecil merubah semua output
5. Collision resistant : setiap hash unik
6. Puzzle friendly : dengan fungsi matematika disambungkan nilai hashnya

Pada blockchain setiap block memiliki hash untuk blok data disampingnya sehingga jika 1 blok data diubah maka blok data yang terhubung akan terubah semua sehingga susah dibobol.