Struktur Data: Hash Table dan Binary Trees

Struktur Data: Hash Table dan Binary Trees

Keduanya merupakan jenis-jenis struktur data yang dapat dibuat. Lalu, apa itu hash table dan binary trees?

1. Hashing dan Hash Table

Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain.

Hash table menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Pada intinya hash table merupakan penyimpanan data menggunakan key value yang didapat dari nilai data itu sendiri. Dengan key value tersebut didapat hash value. Jadi hash function merupakan suatu fungsi sederhana untuk mendapatkan hash value dari key value suatu data.

Cara paling sederhana penggunaan hash table ialah dengan memodulus key valuenya dengan ukuran array yang dimiliki.

hash = key % ukuran

Namun, cara tersebut memiliki kelemahan yaitu akan sering terjadi collision. Collision artinya ada lebih dari satu data yang memiliki hash index yang sama. Untuk itu, perlu dilakukan beberapa implementasi hashing guna mencegah terjadinya collision. Implementasi-implementasi yang dapat dilakukan ialah dengan

1. Closed hashing
   Closed hashing akan mencari alamat lain jika alamat yang dituju sudah terisi. Beberapa teknik closed hashing antara lain
   
   
   1. Linear probing
      Linear probing akan mencari indeks+1 dari alamat yang telah terisi.
   2. Quadratic probing
      Quadratic probing akan mencari alamat baru sesuai dengan rumus yang telah ditentukan sendiri.
   3. Double hashing
      Double hashing akan mencari alamat baru dengan melakukan proses hashing lagi.
      
      
   Kelemahan dari closed hashing ialah ukuran array yang disediakan harus lebih besar dari data yang tersedia (boros memori).
   
   
2. Open hashing
   Open hashing dilakukan dengan cara membuat tabel yang digunakan untuk proses hashing menjadi sebuah array of pointers yang masing-masing pointernya diikuti oleh sebuah linked list.
   
   Kelemahan dari open hashing ialah penumpukan data (linked list panjang).

Lalu, apa bedanya sistem hashing dengan blockchain?

Blockchain adalah catatan transaksi digital terstruktur, dimana 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 lain-lain.

Di dalam blockchain, setiap node menyimpan data secara utuh. Hal ini berbeda dengan hashing yang mana datanya tersimpan di dalam node yang berbeda-beda.

2. Binary Trees

Setiap tree yang memiliki elemen sebanyak-banyaknya 2 "anak" disebut sebagai binary tree. Karena setiap elemennya hanya memiliki 2 anak, maka biasanya kedua anak tersebut disebut anak kiri dan anak kanan. Sedangkan Node yang paling atas disebut dengan root (akar).

Node yang paling tinggi disebut parent. Node dengan posisi yang sama disebut sibling. Node dengan posisi paling rendah disebut leaf.

Berikut merupakan contoh pengimplementasian binary tree pada bahasa C.

struct Node {
    int data;
    struct Node *left;
    struct Node *right;
};

struct Node *newNode (int data) {
    struct Node *node = (struct Node*) malloc (sizeof (struct Node));

    node->data = data;

    node->left = NULL;
    node->right = NULL;
    return (node);
}

int main () {
    struct node *root = newNode (1);

    // 2 dan 3 berubah menjadi anak kiri dan kanan dari 1
    root->left = newNode (2);
    root->right = newNode (3);

    // 4 berubah menjadi anak kiri dari 2
    root->left->left = newNode(4);

    getchar ();
}

Referensi

• https://informatika11d.wordpress.com/2012/11/22/struktur-data-hash-table/
• https://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm
• https://www.barantum.com/blog/blockchain-adalah/
• https://stackoverflow.com/questions/26415908/whats-the-difference-between-distributed-hashtable-technology-and-the-bitcoin-b/36430343
• https://www.geeksforgeeks.org/binary-tree-set-1-introduction/