Hashing Table & Binary Tree

Halo teman-teman, pada kesempatan kali ini saya ingin berbagi tentang Hashing dan Binary Tree, dan implementasi Hashing Table dalam blockchain.

Hashing

Hashing adalah proses memetakan sejumlah besar item data ke tabel yang lebih kecil dengan bantuan fungsi hashing. Ini adalah teknik untuk mengubah rentang nilai kunci menjadi rentang indeks array.

Ini digunakan untuk memfasilitasi metode pencarian tingkat selanjutnya jika dibandingkan dengan pencarian linear atau biner. Hashing memungkinkan untuk memperbarui dan mengambil entri data apa pun dalam waktu konstan O (1). Waktu konstan O (1) berarti operasi tidak tergantung pada ukuran data. Hashing digunakan dengan database untuk memungkinkan item diambil lebih cepat.

Ini digunakan dalam enkripsi dan dekripsi tanda tangan digital.

Hash Function

Proses tetap yang mengubah kunci ke kunci hash dikenal sebagai Fungsi Hash. Fungsi ini mengambil kunci dan memetakannya ke nilai dengan panjang tertentu yang disebut nilai Hash atau Hash. Nilai hash mewakili string karakter asli, tetapi biasanya lebih kecil dari aslinya. Ini mentransfer tanda tangan digital dan kemudian nilai hash dan tanda tangan dikirim ke penerima. Penerima menggunakan fungsi hash yang sama untuk menghasilkan nilai hash dan kemudian membandingkannya dengan yang diterima dengan pesan. Jika nilai hash sama, pesan dikirim tanpa kesalahan.

Hash Table

Hash Table adalah jenis struktur data yang digunakan untuk menyimpan dan mengakses data dengan sangat cepat. Penyisipan data dalam tabel didasarkan pada nilai kunci. Karenanya setiap entri dalam tabel hash didefinisikan dengan beberapa kunci. Dengan menggunakan data kunci ini dapat dicari dalam tabel hash dengan beberapa perbandingan kunci dan kemudian waktu pencarian tergantung pada ukuran hash table.

Contoh implementasi dalam C :

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

#define SIZE 20

struct DataItem {
   int data;   
   int key;
};

struct DataItem* hashArray[SIZE]; 
struct DataItem* dummyItem;
struct DataItem* item;

int hashCode(int key) {
   return key % SIZE;
}

struct DataItem *search(int key) {
   //get the hash 
   int hashIndex = hashCode(key);  
 
   //move in array until an empty 
   while(hashArray[hashIndex] != NULL) {
 
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex]; 
   
      //go to next cell
      ++hashIndex;
  
      //wrap around the table
      hashIndex %= SIZE;
   }        
 
   return NULL;        
}

void insert(int key,int data) {

   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data;  
   item->key = key;

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty or deleted cell
   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
      //go to next cell
      ++hashIndex;
  
      //wrap around the table
      hashIndex %= SIZE;
   }
 
   hashArray[hashIndex] = item;
}

struct DataItem* delete(struct DataItem* item) {
   int key = item->key;

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty
   while(hashArray[hashIndex] != NULL) {
 
      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex]; 
   
         //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem; 
         return temp;
      }
  
      //go to next cell
      ++hashIndex;
  
      //wrap around the table
      hashIndex %= SIZE;
   }      
 
   return NULL;        
}

void display() {
   int i = 0;
 
   for(i = 0; i<SIZE; i++) {
 
      if(hashArray[i] != NULL)
         printf(" (%d,%d)",hashArray[i]->key,hashArray[i]->data);
      else
         printf(" ~~ ");
   }
 
   printf("\n");
}

int main() {
   dummyItem = (struct DataItem*) malloc(sizeof(struct DataItem));
   dummyItem->data = -1;  
   dummyItem->key = -1; 

   insert(1, 20);
   insert(2, 70);
   insert(42, 80);
   insert(4, 25);
   insert(12, 44);
   insert(14, 32);
   insert(17, 11);
   insert(13, 78);
   insert(37, 97);

   display();
   item = search(37);

   if(item != NULL) {
      printf("Element found: %d\n", item->data);
   } else {
      printf("Element not found\n");
   }

   delete(item);
   item = search(37);

   if(item != NULL) {
      printf("Element found: %d\n", item->data);
   } else {
      printf("Element not found\n");
   }
}

Hash table menggunakan fungsi hash untuk menghitung indeks ke dalam array dari ember atau slot, dari mana nilai yang diinginkan dapat ditemukan. tetapi block chain adalah buku besar digital di mana transaksi yang dilakukan dalam bitcoin atau mata uang digital lain dicatat secara kronologis dan terbuka.

Binary Tree

Binary Tree adalah struktur data hierarkis di mana setiap simpul memiliki paling banyak dua anak yang umumnya disebut anak kiri dan anak kanan.

Setiap node berisi tiga komponen:

- Pointer ke subtree kiri

- Pointer ke subtree kanan

- Elemen data

Node paling atas di pohon disebut root. Pohon kosong diwakili oleh pointer NULL.

Jenis - Jenis Binary Tree

Contoh implementasi binary tree dalam C :




struct node 

{

    int data;

    struct node *left;

    struct node *right;

};

  

/* newNode() allocates a new node with the given data and NULL left and 

   right pointers. */

struct node* newNode(int data)

{

  // Allocate memory for new node 

  struct node* node = (struct node*)malloc(sizeof(struct node));

  

  // Assign data to this node

  node->data = data;

  

  // Initialize left and right children as NULL

  node->left = NULL;

  node->right = NULL;

  return(node);

}

  

  

int main()

{

  /*create root*/

  struct node *root = newNode(1);  

  /* following is the tree after above statement 

  

        1

      /   \

     NULL  NULL  

  */

    

  

  root->left        = newNode(2);

  root->right       = newNode(3);

  /* 2 and 3 become left and right children of 1

           1

         /   \

        2      3

     /    \    /  \

    NULL NULL NULL NULL

  */

  

  

  root->left->left  = newNode(4);

  /* 4 becomes left child of 2

           1

       /       \

      2          3

    /   \       /  \

   4    NULL  NULL  NULL

  /  \

NULL NULL

*/

  

  getchar();

  return 0;

}