Summary Data Structure: Hashing Table & Binary Tree

Hashing

Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil kunci dengan cepat. Dalam hashing, string karakter ditransformasikan menjadi nilai panjang yang biasanya lebih pendek atau kunci yang mewakili string asli. Hashing digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat menemukan item menggunakan kunci hash yang lebih pendek daripada menemukannya menggunakan nilai asli. Hashing juga dapat didefinisikan sebagai konsep mendistribusikan kunci dalam array yang disebut tabel hash menggunakan fungsi yang telah ditentukan yang disebut fungsi hash.

Hash Table

Hash table adalah struktur data yang mengimplementasikan tipe data abstrak array asosiatif, struktur yang dapat memetakan kunci ke nilai. Tabel hash menggunakan fungsi hash untuk menghitung indeks, juga disebut kode hash, ke dalam array dari ember atau slot, dari mana nilai yang diinginkan dapat ditemukan.

Implementasi Hash Table pada Blockchain

Peran penting kriptografi dalam jaringan blockchain terus berkembang tiada hentinya. Salah satunya adalah proses perhitungan sebuah data secara konkret dan unik. Metode ini dikenal dengan Hash, mungkin anda tak asing dengan kode unik yang banyak ditemukan di Blockchain dan itulah salah satu contoh Hash.

Nilai berharga sebuah data saat ini berpotensi dibobol atau diketahui oleh orang lain. Salah satu teknik mengakalinya ialah dengan pemberian kode unik. Ibarat peran dari sidik jari elektronik (digital fingerprint) pada data digital punya Anda.

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).

Password atau kode unik di blockchain punya nilai karakter yang lebih panjang dan menggunakan kode unik. Pastinya proses peretesan dengan aplikasi tebak saat ini jelas sangat lama dan bahkan mustahil. Itulah yang menjadi alasan bahwa Hash sangat penting dan dinilai sangat aman.

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.

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. Ia kata sebagai pengalih dan membuat Anda sulit diintai dan data serta privasi tetap aman di jaringan Blockchain.

Implementasi Hash Table di C menggunakan array

#include<stdio.h>

#define size 7

int arr[size];


void init()
{   
    int i;
    for(i = 0; i < size; i++)
        arr[i] = -1;
}

void insert(int value)
{   
    int key = value % size;
    
    if(arr[key] == -1)
    {   
        arr[key] = value;
        printf("%d inserted at arr[%d]\n", value,key);
    }
    else
    {   
        printf("Collision : arr[%d] has element %d already!\n",key,arr[key]);
        printf("Unable to insert %d\n",value);
    }
}

void del(int value)
{
    int key = value % size;
    if(arr[key] == value)
        arr[key] = -1;
    else
        printf("%d not present in the hash table\n",value);
}

void search(int value)
{
    int key = value % size;
    if(arr[key] == value)
        printf("Search Found\n");
    else
        printf("Search Not Found\n");
}

void print()
{
    int i;
    for(i = 0; i < size; i++)
        printf("arr[%d] = %d\n",i,arr[i]);
}

int main()
{
    init();
    insert(10); //key = 10 % 7 ==> 3
    insert(4);  //key = 4 % 7  ==> 4
    insert(2);  //key = 2 % 7  ==> 2
    insert(3);  //key = 3 % 7  ==> 3 (collision)

    printf("Hash table\n");
    print();
    printf("\n");

    printf("Deleting value 10..\n");
    del(10);
    printf("After the deletion hash table\n");
    print();
    printf("\n");

    printf("Deleting value 5..\n");
    del(5);
    printf("After the deletion hash table\n");
    print();
    printf("\n");

    printf("Searching value 4..\n");
    search(4);
    printf("Searching value 10..\n");
    search(10);

    return 0;
}

Hash Function

Ada banyak cara untuk mengaitkan string menjadi kunci. Berikut ini adalah beberapa metode penting untuk membangun hash function.

1. Mid-square

Mid-Square hashing adalah teknik hashing di mana kunci unik dihasilkan. Dalam teknik ini, nilai benih diambil dan dikuadratkan. Kemudian, beberapa digit dari tengah diekstraksi. Angka-angka yang diekstrak ini membentuk angka yang diambil sebagai benih baru. Teknik ini dapat menghasilkan kunci dengan keacakan tinggi jika nilai benih yang cukup besar diambil. Namun, itu memiliki batasan. Saat bijinya dikuadratkan, jika angka 6-digit diambil, maka persegi akan memiliki 12-digit. Ini melebihi kisaran tipe data int. Jadi, overflow harus diurus. Jika terjadi overflow, gunakan tipe data int panjang atau gunakan string sebagai perkalian jika luapan masih terjadi. Kemungkinan tabrakan di tengah-tengah hashing rendah, tidak usang. Jadi, dalam peluang, jika tabrakan terjadi, itu ditangani menggunakan beberapa peta hash.

2. Division (paling umum)

Jumlah lokasi memori yang tersedi dihitung, kemudian jumlah tersebut digunakan sebagai pembagi untuk membagi nilai yang asli dan menghasilkan sisa. Sisa tersebut adalah nilai hashnya. Secara umum, rumusnya h(k)= k mod m. Dalam hal ini m adalah jumlah lokasi memori yang tersedia pada array. Fungsi hash tersebut menempatkan record dengan kunci K pada suatu lokasi memori yang beralamat h(k). Metode ini sering menghasilkan nilai hash yang sama dari dua atau lebih nilai aslinya atau disebut dengan bentrokan. Karena itu, dibutuhkan mekanisme khusus untuk menangani bentrokan yang disebut kebijakan resolusi bentrokan.

3. Folding

Untuk mendapatkan alamat relatif, nilai key dibagi menjadi beberapa bagian, setiap bagian (kecuali bagian terakhir) mempunyai jumlah digit yang sama dengan alamat relatif. Bagian-bagian ini kemudian dilipat (seperti kertas) dan dijumlah. Hasilnya, digit yang tertinggi dibuang (bila diperlukan).

4. Digit Extraction

Menggunakan ekstraksi digit digit yang dipilih diekstraksi dari kunci dan digunakan sebagai alamat.

5. Hash Rotation

Metode rotasi umumnya tidak digunakan dengan sendirinya melainkan digabungkan dalam kombinasi dengan metode hashing lainnya. Ini sangat berguna ketika kunci ditugaskan secara serial

Tree

tree adalah abstract data type (ADT) yang banyak digunakan untuk mensimulasikan struktur hierarki pohon, dengan nilai root dan subtrees of children dengan node parent, direpresentasikan sebagai satu set node yang terhubung.

Struktur data pohon dapat didefinisikan secara rekursif sebagai kumpulan node (dimulai dari simpul akar), di mana setiap simpul adalah struktur data yang terdiri dari suatu nilai, bersama dengan daftar referensi ke node ("children"), dengan kendala yang tidak ada referensi digandakan, dan tidak ada yang menunjuk ke root

Binary Tree

Pohon yang unsurnya paling banyak memiliki 2 children disebut pohon biner (Binery Tree). Karena setiap elemen dalam pohon biner hanya dapat memiliki 2 children, biasanya disebut left children dan right children.