Skip to main content

Hash Table

Hash Table 

Hash table kind of data structure that use an associative array, meaning that a hash table can map a value to a certain index/key. Usually this will use a hash function to find out to index/key of a certain value. Hash Table is used speed up searching so that it can reach O(n). In hash table we will find two new term such as :

  • Collision : Is where our hash function generate the same key for two different value. Usually such collision will be handled with some kind of collision handling in the code.
  • Hash Function : A function that will generate key for a value.


Hash Function

A hash function is usually used to find out the key or index of a certain value. This key will be sued to insert our data into the table. Also there is no hash function that will not generate any collision, meaning that our code will have to be able to handle collision. There are many method that can be used to generate hash key :

  1. Division : a Mod b (a is our value, b is the size of our table usually a prime number)
  2. Multiplication : floor ( n ( k A mode 1))
    1. n : is the size of out table
    2. k : is the value
    3. A : is a random number between 0 and 1
  3. etc.

Collision

Collision is caused by a hash function that generate a same key for 2 or more different value. Usually this will be resolved in two different way : 

  1. Separate Chaining
In separate chaining if there are a collision the inserted data will be chained to the old data like a linked list (https://en.wikipedia.org/wiki/Hash_table#Collision_resolution)
  1. Open Addressing


Is where we compute the key again so that we will get an empty space in our table. There are 3 usually used method for this type :

    1. Linear Probing : Is where we add 1 to our key until we get an empty space in the table
    2. Quadratic Probing : Is where we add successive value(1,2,3,...) to our key until we get an empty space in out table.
    3. Double Hashing : where we rehash out key with a different hash function.
Below is a code for a hash table with separate chaining to resolve the collision : 


#include <stdio.h>
#include <malloc.h> //we need to use malloc to create a new node
#define SIZE 20

struct Node{
int value; //using the separate chaining concept to address collision
Node *next;
};

Node *table[SIZE]; // make out table (can only accept pointer)

Node *createNode(int val){
Node *node = (Node*)malloc(sizeof(Node));
node->value=val; // function to make a new node
node->next=NULL;
return node;
}

int hash(int value){
return value % SIZE; //our hash function
}

void insert(int val){
Node *node=createNode(val);
int key = hash(node->value);
if(table[key]==NULL){
table[key]=node; //if the table is null then just insert 
}else {
if(table[key]->next==NULL){
table[key]->next=node; 
}else { //use separate chaining for collision handling
Node *curr=table[key];
while(curr->next!=NULL){
curr=curr->next;
}
curr->next=node;
}
}
}

void del(int val){
int key = hash(val);
if(table[key]==NULL){
return ;
}else{
if(table[key]->value==val){
if(table[key]->next==NULL){
table[key]=NULL;
}else {
Node *del = table[key];
table[key]=table[key]->next;
free(del);
del = NULL;
}
}else {
Node *del=table[key]->next;
Node *prev=table[key];
while(del->value!=val && del!=NULL){
del = del->next;
prev = prev->next;
}
prev->next = del->next;
free(del);
del=NULL;
}
}
}

void init(){
for(int i=0;i<SIZE;i++){
table[i] = NULL; //function to initialize out table;
}
}

void view(){
for(int i=0;i<SIZE;i++){
if(i+1<10){
printf("%d  | ", i+1);
}else {
printf("%d | ", i+1);
}
Node *curr=table[i];
while(curr!=NULL){ //function to view our table
printf("%d -> ", curr->value);
curr=curr->next;
}
printf("\n");
}
}

void cls(){
for(int i=0;i<35;i++){
printf("\n");
}
}


int main(){
int input;
int menu;
init();
while(1){
cls();
view();
printf("1. Insert\n");
printf("2. Delete\n");
printf("3. Exit\n");
printf(">> ");
scanf("%d", &menu); getchar();
if(menu==3){
break;
}
switch(menu){
case 1:
printf("Insert data : ");
scanf("%d", &input);
insert(input);
break;
case 2:
printf("Input data : ");
scanf("%d", &input);
del(input);
break;
}
}
return 0;
}

Comments

Post a Comment

Popular posts from this blog

Linked List Linked List a sequence of data structure connected together via links. In C a list is usually composed of multiple type of data so we usually use struct so that we can insert multiple amount of data into a single list, also our list also contain a reference(pointer in C) to the next list. So because of this reference our list linked to one another and that is also why this is called linked list. Also in linked list there is another reference that is Head and Tail . Head point to the first list in our linked list and Tail point to the last of our list in the linked list. Now Linked List usually have 2 type that is : 1. Single Linked List 2. Double/Doubly Linked List Single Linked List A single linked list have only one reference that is a reference to the next list. So we could think that a single linked list is like an array.  As seen a single linked list only contain one reference that point to the next list. Also in our tail the next poin...
Post a Comment
Read more
Stack & Queue Stack Stack is type of data structure that store it's data in an orderly manner. Data in stack can only be removed and added from one end of the data. This is called LIFO (Last in First Out) Meaning that the last data that enter will be the first one to be removed. Stack can be implemented with array or linked list. Stack is usually used in backtracking algorithm and also used when making a recursive function (Depth First Search). Queue Queue is also a type of data structure but it's main difference from stack is that in queue data can only be added from behind and data can only be removed from the front of the queue just like a real life queue. This is called FIFO (First In First Out) meaning that the first data that is inserted will be the one that is removed first. Also like stack queue can be implemented with array or linked list. Now queue is used in an algorithm called Breath First Search. Queue also have another type called Circular Que...
Post a Comment
Read more

AVL dan B-Tree

AVL TREE In Computer Science term an AVL tree is a type of self-balancing binary tree. The word AVL come from it's inventor  A delson- V elsky and  L andis. It's the first of such Data Structure. The term self-balancing mean that an AVL tree will maintain both of it's subtree height so that their height diffenrence will be 1, -1, or 0. This is called the balance facotr of an AVL tree. Basically an AVL tree is like an Binary Search Tree but with an self-balancing function built into it.  Why Use an AVL Tree The reasoning to why we must balance the tree if it's not balanced is so that the time complexity for the operation (Search, Insert, Delete) will always be at O(log n) instead of the usual O(h) (where h is the height of the tree ) for the worst case scenario.  Example of a skewed tree For the tree above say that we want to search for the node 74 that we have to traverse the entire tree to find said note but if it's an AVL tree then We on...
Post a Comment
Read more