Short Note On Hashing.

Question

Hash Table is a data structure which stores data in an associative manner. In a hash table, data is stored in an array format, where each data value has its own unique index value.

A data structure in which insertion and search operations are very fast irrespective of the size of the data. Hash Table uses an array as a storage medium and uses hash technique to generate an index where an element is to be inserted or is to be located.

Hashing:-

Hashing is the function or routine used to assign the key values to the each entity in the database. Using hashing, We can easily access or search the values from database.
Hashing is implemented by using Hash Table data structure. Item are in the (key,value) format.

Applications of Hashing:-

• Hash tables are generally used to implement associative arrays because of their constant amortized time search and insertion. Hashing is used in them to index and retrieve items.
• Hashing as a method is used in comparing strings by generating rolling hash as part of Rabin-Karp algorithm.
• Hashing algorithms(Hash functions) are widely used in cryptography. These include the message-digest hash functions like MD5 used for hashing digital signatures into a shorter value called a  message-digest.
• Consistent hashing, a special kind of hashing is used to map values to  cache machines.

Basic Operations:-

Following are the basic primary operations of a hash table.

• Search − Searches an element in a hash table.

• Insert − inserts an element in a hash table.

• Delete − Deletes an element from a hash table.

Search Operation:-

An element is to be searched, compute the hash code of the key passed and locate the element using that hash code as index in the array. Use linear probing to get the element ahead if the element is not found at the computed hash code.

The code snippet for search operation is given below:-

    struct DataItem *search(int key)

       {
    int hashIndex = hashCode(key);   //get the hash
    while(hashArray[hashIndex] != NULL)   //move in array until an empty

 

            {
   if(hashArray[hashIndex]->key == key)
   return hashArray[hashIndex];   //go to next cell
   ++hashIndex;   //wrap around the table
    hashIndex %= SIZE;
           }
    return NULL;       
      }

Insert Operation:-

An element is to be inserted, compute the hash code of the key passed and locate the index using that hash code as an index in the array. Use linear probing for empty location, if an element is found at the computed hash code.

The code snippet for Insertion operation is given below:-

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)

           {
   ++hashIndex;  //wrap around the table
   hashIndex %= SIZE;
           }
   hashArray[hashIndex] = item;       

}

Delete Operation:-

An element is to be deleted, compute the hash code of the key passed and locate the index using that hash code as an index in the array.

The code snippet for Delete operation is given below:

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;
               }
     ++hashIndex;  //wrap around the table
     hashIndex %= SIZE;
        } 
     return NULL;        

 } 

Go through this video:-