HASH TABLE & BINARY SEARCH TREE ? WHAT IS THAT?

HASH TABLE + BINARY SEARCH TREE ?

APAAN SIH ? ( in general  )

Halo semuanya ! Kali ini mimin Peik mau ngenalin kalian apa sih itu Hashing Table dan Binary Tree yang tentunya adalah topik lanjutan Data Structure . Para pembaca sebelumnya dituntut sudah mengerti cara kerja Data Structure secara dasar seperti protokol Linked List dan spesies-spesiesnya ya ! ^ 0 ^

A. Hashing Table / Hash Table

Apa sih ? Namanya makin aneh-aneh aja . Hash Table disini yang dimaksud bukan langsung menjadi hash yang kalian bayangkan MD5 , SHA1 dan sebagainya ya, lebih ke protokol cara kerjanya dulu !  ADALAH struktur data yang terdiri dari sebuah TABEL dan fungsi yang memetakan nilai KUNCI untuk setiap record dalam suatu angka . Ya intinya jadi kayak KAMUS gitu guys ! :o Jadi bisa diasumsikan bahwa nanti kalian tinggal memberikan sebuah (key) lalu kalian bakal diarahin ke entri tujuan yang mengandung key yang kalian kasih , sehingga AKSES DIPERMUDAH .

Sebelumnya , kalian wajib tahu juga cara kerja Hashing nih !
Nah idenya sih seperti mengubah string menjadi suatu bilangan dengan suatu fungsi lalu di modulo.
Nanti kompleksitas untuk setiap operasi adalah O(k) dimana K = panjang string .
Kalau hashing-nya sendiri adalah protokol pengubah objek menjadi serangkaian angka/karakter bahkan sejenisnya.
Misal , seperti:


arr["inipeik"] = 5;
printf("%d\n", arr["inipeik"]);


Collision Case

Nah , kalau di Hash Table , keys nya akan diproses untuk menghasilkan suatu indeks baru pada elemen yang dibutuhkan . TAPI PERLU DIPERHATIKAN , kalau terdapat indeks yang sama yang dihasilkan dari hashing , dapat terjadi adanya collision . Untuk menghindari ini , harus dipilih hash function yang sesuai.
Solusi pertama adalah dengan menggunakan teknik CHAINING ( sumber dari https://www.programiz.com/dsa/hash-table )

Jika fungsi hashing menghasilkan index yang sama pada elemen-elemen , elemen-elemen tersebut akan disimpan di INDEKS YANG SAMA dengan menggunakan doubly linked list .

// Implementing hash table in C

#include <stdio.h>
#include <stdlib.h>

struct set
{
  int key;
  int data;
};
struct set *array;
int capacity = 10;
int size = 0;

int hashFunction(int key)
{
  return (key % capacity);
}
int checkPrime(int n)
{
  int i;
  if (n == 1 || n == 0)
  {
    return 0;
  }
  for (i = 2; i < n / 2; i++)
  {
    if (n % i == 0)
    {
      return 0;
    }
  }
  return 1;
}
int getPrime(int n)
{
  if (n % 2 == 0)
  {
    n++;
  }
  while (!checkPrime(n))
  {
    n += 2;
  }
  return n;
}
void init_array()
{
  capacity = getPrime(capacity);
  array = (struct set *)malloc(capacity * sizeof(struct set));
  for (int i = 0; i < capacity; i++)
  {
    array[i].key = 0;
    array[i].data = 0;
  }
}

void insert(int key, int data)
{
  int index = hashFunction(key);
  if (array[index].data == 0)
  {
    array[index].key = key;
    array[index].data = data;
    size++;
    printf("\n Key (%d) has been inserted \n", key);
  }
  else if (array[index].key == key)
  {
    array[index].data = data;
  }
  else
  {
    printf("\n Collision occured  \n");
  }
}

void remove_element(int key)
{
  int index = hashFunction(key);
  if (array[index].data == 0)
  {
    printf("\n This key does not exist \n");
  }
  else
  {
    array[index].key = 0;
    array[index].data = 0;
    size--;
    printf("\n Key (%d) has been removed \n", key);
  }
}
void display()
{
  int i;
  for (i = 0; i < capacity; i++)
  {
    if (array[i].data == 0)
    {
      printf("\n array[%d]: / ", i);
    }
    else
    {
      printf("\n key: %d array[%d]: %d \t", array[i].key, i, array[i].data);
    }
  }
}

int size_of_hashtable()
{
  return size;
}

int main()
{
  int choice, key, data, n;
  int c = 0;
  init_array();

  do
  {
    printf("1.Insert item in the Hash Table"
         "\n2.Remove item from the Hash Table"
         "\n3.Check the size of Hash Table"
         "\n4.Display a Hash Table"
         "\n\n Please enter your choice: ");

    scanf("%d", &choice);
    switch (choice)
    {
    case 1:

      printf("Enter key -:\t");
      scanf("%d", &key);
      printf("Enter data -:\t");
      scanf("%d", &data);
      insert(key, data);

      break;

    case 2:

      printf("Enter the key to delete-:");
      scanf("%d", &key);
      remove_element(key);

      break;

    case 3:

      n = size_of_hashtable();
      printf("Size of Hash Table is-:%d\n", n);

      break;

    case 4:

      display();

      break;

    default:

      printf("Invalid Input\n");
    }

    printf("\nDo you want to continue (press 1 for yes): ");
    scanf("%d", &c);

  } while (c == 1);
}

Solusi kedua adalah dengan menggunakan Open Addressing . Pada teknik ini , semua elemen akan disimpan di dalam hash table itu sendiri. Ukuran dari tabelnya pastinya harus lebih besar sama dengan total keys . Nah salah satunya adalah dengan menggunakan Linear Probing .

Intinya dia akan melakukan pengecekan pada slot selanjutnya dimana:

func(k, i) = (newfunc(k) + i) mod m

//newfunc adalah fungsi baru

Adapun quadratic probing dan double hashing technique untuk me-resolve collision case ini juga ^0^.

Blockchain Case

Pada blockchain , implementasi hash table ini sebenarnya dipakai , namun lebih distributif makanya disebut dengan DHT ( Distributed Hash Table ).
DHT disini protokolnya sama dengan Hash Table biasa yakni menyimpan suatu nilai key yang terdapat di berbagai jumlah nodes pada network dengan menggunakan deterministic algorithm , dimana algoritma ini akan menghasilkan output yang sama .



Lalu juga digunakan adanya routing algorithm yang akan melakukan request pada hash table tanpa mengetahui setiap node di network. Contohnya saja yang dipakai adalah Chord DHT .







B. Binary Search Tree

Nah , mimin harap kalian semua jadi mengerti apa itu Hash Table . Sekarang kita move on ke topik selanjutnya yakni Binary Tree ! Apa sih Binary Search Tree itu sendiri ?

Oke sebelum kalian paham BST ini , kalian harus tahu apa itu Tree?
Tree sendiri bisa dikatakan sebagai suatu struktur data berupa bentuk pohon terbalik yang menggambarkan hubungan hierarkis antar elemen.



Nah kalau pada Binary Tree sendiri , dia hanya memiliki maksimal 2 cabang saja.


Oke sekarang kita masuk pada pembahasan Binary Search Tree , konsepnya sama saja dengan Binary Tree namun terdapat aturan bahwa setiap child node di sebelah kiri harus lebih kecil nilainya dari pada root node dan vice-versa !




Pada Binary Search Tree , terdapat 3 cara unutk melakukan traversing ,yakni:
1. Pre-order = print data lalu traverse ke kiri lalu traverse ke kanan
2. In-Order =  traverse kiri , print data , lalu traverse kanan
3. Post-order  = traverse kiri, traverse kanan lalu print data













Sumber :
https://www.programiz.com/dsa/hash-table
https://www.geeksforgeeks.org/implementing-hash-table-open-addressing-linear-probing-cpp/
http://kupaskode.blogspot.com/2015/09/tentang-hashing.html
https://visualgo.net/id/hashtable?slide=11-4
https://www.geeksforgeeks.org/hashing-data-structure/
https://stackoverflow.com/questions/31930046/what-is-a-hash-table-and-how-do-you-make-it-in-c
https://stackoverflow.com/questions/26415908/whats-the-difference-between-distributed-hashtable-technology-and-the-bitcoin-b
https://www.slideshare.net/lmatteis/kudos-a-peertopeer-discussion-system-based-on-social-voting/4-distributed_hash_tablepeersblockchainkeykeygetkeyputkey_val
https://www.mahirkoding.com/struktur-data-binary-search-tree-bst/