Hashing table & Binary Tree

Hashing and Hash Table

Hashing adalah transformasi string karakter menjadi nilai panjang tetap yang lebih pendek atau menjadi sebuah kunci yang mewakili string aslinya. Hashing digunakakn untuk mengindeks dan mengambil item dalam database karena lebih cepat menemukan item menggunakan kunci hahs yang lebih pendek daripada menemunkannya mengginakan nilai asli. Hashing juga bisa didefinisikan sebagai konsep yang mendistribusikan kunci ke dalam array yang biasa disebut "Hash Table" yang menggunakan sebuah fungsi yang biasa disebut "Hash Function". Hash Table ada table yang berupa array yang merupakan tempat dimana kita menyimpan string yang asli. Index yang terdapat pada tabel adalah hashed key atau key yang telah didapat melalui suatu proses sementara isi dari array tersebut adalah original stringnya. Biasanya ukuran dari Hash Table ini cukup kecil sehingga memungkinkan untuk menghasilkan hashed key atau kunci yang sama.

Hash Function

Ada berbagai macam cara untuk transformasi string untuk menjadi sebuah key. Berikut adalah beberapa method yang penting untuk membentuk Hash Function :

  1. Mid-square
  2. Division
  3. Folding
  4. Digit Extraction
  5. Rotating Hash

Collision

Pada sebelumnya sudah saya katakan bahwa akan ada kemungkinan untuk suatu string menghasilkan key yang sama. Hal ini biasa disebut Collision. Untuk mengatasi hal tersebut maka 2 cara untuk mengatasi kejadian ini :
  • Linear Probing
          Mencari slot kosong disebelahnya dan memasukkannya pada slot kosong tersebut.
  • Chaining
          Meletakkan string pada slot tersebut dengan cara chained list (linked list).

Trees & Binary Tree

Untuk memahami Trees & Binary Tree, lebih baik kita memahami terlebih dahuli bagaimana konsep dari Tree dan Binary Tree. Berikut gambar dari konsep Trees dan Binary Tree.
Berikut sebuah codingan simple tree di 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);   
  root->left        = newNode(2); 
  root->right       = newNode(3); 
  root->left->left  = newNode(4); 

  getchar(); 
  return 0; 
}

Komentar

Posting Komentar

Postingan populer dari blog ini

AVL Tree

Gambar
Pada dasarnya AVL Tree ini adalah Binary Search Tree namun yang lebih seimbang atau balance karena pasti total node kiri dan kanan selisih tingginya tidak akan lebih dari 1. Sedangkan di BST bisa saja tinggi node kiri dan kanan tidak seimbang sehingga bisa menyebabkan proses pencarian, insert, maupun delete lebih lama yaitu n sedangkan dengan AVL Tree proses pencarian,insert, atau delete menjadi log n. Contoh hasil BST jika dengan insert 2, 5, 7, 8, 13: Contoh hasil AVL Tree jika dengan insert yang sama: Untuk menyeimbangkan node tersebut, AVL Tree menggunakan rotasi atau rotation. Rotation ini dibagi menjadi 2 yaitu single rotation dan double rotation. rotation ini terjadi akibat perbedaan selisih tinggi node kiri dan kanan yang lebih dari 1. Contoh single rotation Contoh double rotation
Baca selengkapnya

HEAP and TRIES

Gambar
HEAP Heaps adalah binary tree yang nodenya dapat direpresentasikan dalam sebuah array. Type of Heap A. Max Heap Max yang berarti parentnya lebih besar daripada childnya. Elemen terbesar pada Max Heap terdapat di root tree dan semakin kebawah artinya semakin kecil. B. Min Heap Min yang berarti parentnya lebih kecil daripada childnya. Elemen terbesar pada Min Heap terdapat di root tree dan semakin kebawah artinya semakin besar. Heap dapat diimplementasikan menggunakan linked list tapi lebih mudah menggunakan array. C. Min Max Heap Ini adalah case unik atau spesial dari heap. Max dan min bergantian pada setiap level. Urutan level dari heap berupa min(dimulai dari root) lalu max lalu min lagi dan seterusnya. Pada bagian min akan selalu ganjil dan max akan selalu genap. Di dalam heap terdapat 2 metode yaitu insertion dan deletion. Max Heap Insertion step 1 : membuat node baru di akhir dari heap step 2 : memasukkan nilai baru ke node tersebut ste...
Baca selengkapnya

Summary

Gambar
Linked List Pada pertemuan kedua kelas besar kemarin saya belajar mengenai cara membuat linked list di C. Setelah saya mempelajarinya kemarin, saya juga mencoba membuat linked list buatan saya sendiri. Berikut codingan linked list saya : #include<stdio.h> #include<stdlib.h> #include<string.h> struct Node{ int test; char nama[1000]; struct Node *next; }*head,*curr,*tail,*temp1,*temp2; void pushhead(int a,char nama[]){ curr = (struct Node*)malloc(sizeof(struct Node)); curr -> test = a; strcpy(curr->nama,nama); if(head==NULL){ head=curr; tail=curr; tail->next=NULL; } else{ curr->next = head; head = curr; } } void pushtail(int a,char nama[]){ curr = (struct Node*)malloc(sizeof(struct Node)); curr -> test = a; strcpy(curr->nama,nama); if(head==NULL){ head=curr; tail=curr; tail->next=NULL; } else{ tail->next = curr; curr->next=NULL; tail = curr; } } void poptail(){ curr=head; while(curr->next->nex...
Baca selengkapnya