Summary of Hashing in Data Structure

What is Hashing?

  • Hashing is the process of mapping large amount of data item to smaller table with the help of hashing function.
  • Hashing is also known as Hashing Algorithm or Message Digest Function.
  • It is a technique to convert a range of key values into a range of indexes of an array.
  • It is used to facilitate the next level searching method when compared with the linear or binary search.
  • Hashing allows to update and retrieve any data entry in a constant time O(1).
  • Constant time O(1) means the operation does not depend on the size of the data.
  • Hashing is used with a database to enable items to be retrieved more quickly.
  • It is used in the encryption and decryption of digital signatures.

What is Hash Function?

  • A fixed process converts a key to a hash key is known as a Hash Function.
  • This function takes a key and maps it to a value of a certain length which is called a Hash value or Hash.
  • Hash value represents the original string of characters, but it is normally smaller than the original.
  • It transfers the digital signature and then both hash value and signature are sent to the receiver. Receiver uses the same hash function to generate the hash value and then compares it to that received with the message.
  • If the hash values are same, the message is transmitted without errors.

What is Hash Table?

  • Hash table or hash map is a data structure used to store key-value pairs.
  • It is a collection of items stored to make it easy to find them later.
  • It uses a hash function to compute an index into an array of buckets or slots from which the desired value can be found.
  • It is an array of list where each list is known as bucket.
  • It contains value based on the key.
  • Hash table is used to implement the map interface and extends Dictionary class.
  • Hash table is synchronized and contains only unique elements.


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");
   }
}

source:


Comments

Post a Comment

Popular posts from this blog

Pengertian kelas besar tentang head, curr, tail

Image
  The topic I learn today in Big class is about the concept position of where will our pointer be directed at when we have head, curr, and tail.   Let say we have a singly link list that we want to make a push insertion.To make it happen we need to know where our address is first before we start making push insertion. The push insertion will be pushing from the front(beginning) and make a pop will be delete address. struct node{   int data; // value   struct node *next, *prev; // address }*head,*curr,*tail; void push(int a) {     curr = (struct Data*)malloc(sizeof(struct Data));//create address     curr->value = a;//insert value input a         if(head==NULL){// if head don have any address then we create one         head = tail = curr;     }     else{         tail->next = curr;// move tail to curr         curr->...
Read more

AVL TREE

Image
AVL TREE is pretty similar to binary search tree but AVL can adjust the balance of the tree automatically The root of the node AVL tree is 0 The leaf of the right or leaf of the left is 1. if the leaf is more than 1 the tree will automatically adjust the balance The above picture is from the right node input and will be rotating to the left. and this other picture is node from the left side and the rotation will be going to the right. the correct solution of the wrong AVL tree is below:- here another example :- Example of Single rotation below example of Doubly rotation Source: https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm https://en.wikipedia.org/wiki/File:AVL_Tree_Example.gif AVL TREE PPT binus https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
Read more

Binary Search Tree(BNS)

Image
BNS is also known as versions of sorted version of binary tree for the node of the left subtree is contain smaller number than those store in x for the node of the right subtree is contain greater number than those store in x there are three operation in BNS: insert() search() remove() The insert of BNS is to store is done recursively. let the new node's key be X, then we have a number of 30 of the beginning of the first node. if the node key input is smaller it will move the node to the left subtree side, if the node key is greater than it will move to the right subtree side. here is the example:- Now we will discuss search of BNS or can be call find of BNS. The search is pretty easy it just finds the node key of the X in the tree. if the search found the node it search then it will print the "the node key is found in the tree". The search algorithm is pretty much similar to insert but it job not to insert but to find only. La...
Read more