top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Short Note On Hashing.

0 votes
1,030 views

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:-


posted May 9, 2017 by Raju Raj

  Promote This Article
Facebook Share Button Twitter Share Button LinkedIn Share Button


Related Articles

BINARY SEARCH TREE (BST)

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties −

  • The left sub-tree of a node has a key less than or equal to its parent node's key.

  • The right sub-tree of a node has a key greater than to its parent node's key.

 

Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree and can be defined as −

            left_subtree (keys)  ≤  node (key)  ≤  right_subtree (keys)

Representation

BST is a collection of nodes arranged in a way where they maintain BST properties. Each node has a key and an associated value. While searching, the desired key is compared to the keys in BST and if found, the associated value is retrieved.

Following is a pictorial representation of BST

observe that the root node key (27) has all less-valued keys on the left sub-tree and the higher valued keys on the right sub-tree.

Various Operations on a Binary Search Tree

The various operations that can be performed on a binary search tree are --

   a)searching for a data

   b)inserting any data into it

   c)deleting any data from it

   d)traversing the tree

a)Searching in a Binary Tree - Searching for a data in a binary search tree is much faster than in arrays or linked lists.

      Algorithm- The sequence of steps to be followed in searching the binary search are as follows:

      1)Start from the root node.

     2)Suppose if the data to be searched is ITEM then,it is compared with the value of the root node. If the ITEM is less than the value in the root node, choose the left sub-tree of the root node. If the data to be searched (ITEM) is greater than the value in the root node, choose the right sub tree of that root node.

     3) Step 2 is repeated till the ITEM is not found or we reach the leaf node.         

b)Insertion of Data into a Binary search Tree - The insertion operation on a binary search tree is very simple.

Algorithm- The sequence of steps to be followed in performing the insertion operation on a binary search tree are as follows.      
1)Start from the root node.

2)If the data to be inserted is ITEM, compare this with the value of the root node.

      a)If they are the same, just stop because the item already exists.

      b)If they are different and if the data to be inserted(ITEM) is less than the value of the root node, choose the left sub-tree.

      c)If the data to be inserted (ITEM) is greater than the value of the root node, choose the right sub-tree.

3) Repeat Step 2 until the leaf node is encountered where the item has to be inserted.

c) Deletion of a Node from a Binary Search Tree - Another useful operation that can be performed on a binary search tree is to delete a node from it. Here, deletion of a node N depends on the number of its children.

There are 3 cases that can occur.

case 1: N is a leaf node.

case 2: N has exactly one child.

case 3: N has two children.

d) Traversal Operation on Binary Search Tree - All the traversal operations are applicable in binary search trees. The in-order traversal on the binary search tree gives the sorted order of data in ascending order.

Applications of a Binary Search Tree (BST)

A Binary Search Tree (BST) can have the following applications.

  1) Searching for an element.

  2) Sorting a set of data

  3) Removing the redundancies from a collection of data.

 

/* Program to build a binary search tree from arrays */

#include <stdio.h>
#include <conio.h>
#include <alloc.h>

struct node
{
    struct node *left ;
    char data ;
    struct node *right ;
} ;

struct node * buildtree ( int ) ;
void inorder ( struct node * ) ;

char a[ ] = {
            'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0', 'H', '\0',
            '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0', '\0'
            } ;

void main( )
{
    struct node *root ;

    clrscr( ) ;

    root = buildtree ( 0 ) ;
    printf ( "In-order Traversal:\n" ) ;
    inorder ( root ) ;

    getch( ) ;
}
struct node * buildtree ( int n )
{
    struct node *temp = NULL ;
    if ( a[n] != '\0' )
    {
        temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
        temp -> left = buildtree ( 2 * n + 1 ) ;
        temp -> data = a[n] ;
        temp -> right = buildtree ( 2 * n + 2 ) ;
    }
    return temp ;
}

void inorder ( struct node *root )
{
    if ( root != NULL )
    {
        inorder ( root -> left ) ;
        printf ( "%c\t", root -> data ) ;
        inorder ( root -> right ) ;
    }
}
Go through this video:-
https://www.youtube.com/watch?v=MVAlC3zQBYg

READ MORE

A Queue is a linear data structure. It is a list in which all insertions to the queue are performed at one end and all the deletions are performed at the other end. The element in the queue are processed in the same order in which they were received. Hence it is called a First In First Out(FIFO) list.

Applications of Queue

  1. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
  2. In real life, Call Center phone systems will use Queues, to hold people calling them in an order, until a service representative is free.
  3. Handling of interrupts in real-time systems.

Basic operation 

  • enqueue() − add (store) an item to the queue.

  • dequeue() − remove (access) an item from the queue.

Enqueue Operation

Queues maintain two data pointers, front and rear.

The steps should for enqueue (insert) data into a queue −

Step 1 − Check if the queue is full.

Step 2 − If the queue is full, produce overflow error and exit.

Step 3 − If the queue is not full, increment rear pointer to point the next empty space.

Step 4 − Add data element to the queue location, where the rear is pointing.

Step 5 − return success.

Dequeue Operation

Accessing data from the queue is a process of two tasks − access the data where front is pointing and remove the data after access.

Step 1 − Check if the queue is empty.

Step 2 − If the queue is empty, produce underflow error and exit.

Step 3 − If the queue is not empty, access the data where front is pointing.

Step 4 − Increment front pointer to point to the next available data element.

Step 5 − Return success.

 

Array Implementation Of Queue

#include <stdio.h>

#define MAX 50

int queue_array[MAX];

int rear = - 1;

int front = - 1;

main()

{

    int choice;

    while (1)

    {

        printf("1.Insert element to queue \n");

        printf("2.Delete element from queue \n");

        printf("3.Display all elements of queue \n");

        printf("4.Quit \n");

        printf("Enter your choice : ");

        scanf("%d", &choice);

        switch (choice)

        {

            case 1: insert();

            break;

            case 2: delete();

            break;

            case 3: display();

            break;

            case 4: exit(1);

            default: printf("Wrong choice \n");

        }   /*End of switch*/

    }   /*End of while*/

}   /*End of main()*/

insert()

{

    int add_item;

    if (rear == MAX - 1)

       {         

    printf("Queue Overflow \n");        

       }

    else

    {

        if (front == - 1)           

           {

        /*If queue is initially empty */

        front = 0;

        printf("Inset the element in queue : ");

        scanf("%d", &add_item);

        rear = rear + 1;

        queue_array[rear] = add_item;

           }

    }

} /*End of insert()*/

 

delete()

{

    if (front == - 1 || front > rear)

    {

        printf("Queue Underflow \n");

        return ;

    }

    else

    {

  printf("Element deleted from queue is : %d\n", queue_array[front]);

  front = front + 1;

    }

} /*End of delete() */

display()

{

    int i;

    if (front == - 1)        

       {

        printf("Queue is empty \n");

       }

    else

    {

        printf("Queue is : \n");

        for (i = front; i <= rear; i++)

            {

            printf("%d ", queue_array[i]);             

            printf("\n");

            }

    }

}

  Analysis of Queue

  • Enqueue : O(1)
  • Dequeue : O(1)
  • Size       : O(1)

Please go through video:

https://www.youtube.com/watch?v=okr-XE8yTO8

 

READ MORE

Quick Sort

Quick sort is a very popular sorting method. This sort name comes from the fact that quick sort can sort a list of data elements significantly faster than any of the common sorting algorithms. This sorting uses a strategy called divide and conquer. It is based on the principle that is faster and easier to sort two small arrays than one larger one. 

The sequence of steps required to perform a quick sort operation on a set of elements of  the array are as follows.

  1. A pivot item near the middle of the array is chosen. Let it be x.
  2. Now scan the array from left to right until some element e.g., ai>x is encountered.
  3. Now scan the array from right to left until some element e.g.,aj<x is encountered.
  4. Now exchange the items ai and aj.
  5. Again repeat steps 2 to 4 until the scan operation meets somewhere in the middle of the array.

Quick sort is also called partition exchange sort and it was invented by C.A.R. Hoare. The average execution time of quick sort is O(n(log2n)2) and this sort is good for large sorting jobs.

Pictorial Representation

 

 

Quick Sort Algorithm

1. If n < = 1, then return.

2. Pick any element V in a[]. This is called the pivot.

3. Rearrange elements of the array by moving all elements xi > V right of V and all elements x­i < = V left of V. If the place of the V after re-arrangement is j, all elements with value less than V, appear in a[0], a[1] . . . . a[j – 1] and all those with value greater than V appear in a[j + 1] . . . . a[n – 1].

4. Apply quick sort recursively to a[0] . . . . a[j – 1] and to a[j + 1] . . . . a[n – 1].

Program for Quick Sort 

#include <stdio.h>

void quick_sort(int[], int, int);
int partition(int[], int, int);

int main() 
{
    int a[50], n, i;

    printf("How many elements?");
    scanf("%d", & n);
    printf("\nEnter array elements:");

    for  (i = 0; i < n; i++)
    {
        scanf("%d", & a[i]);
    }

    quick_sort(a, 0, n - 1);

    printf("\nArray after sorting:");

    for (i = 0; i < n; i++)
    {  
        printf("%d ", a[i]);
    }


    return 0;
}

 

void quick_sort(int a[], int l, int u) 
{
    int j;

    if  (l < u) 
    {
        j = partition(a, l, u);
        quick_sort(a, l, j - 1);
        quick_sort(a, j + 1, u);
    }
}

 

int partition(int a[], int l, int u) 
{
    int v, i, j, temp;
    v = a[l];
    i = l;
    j = u + 1;

    do 
    {
        do
        {
            i++;
        }

        while (a[i] < v && i <= u);

        do
        {
            j--;
        }

        while (v < a[j]);

        if  (i < j)
        {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    } 

    while (i < j);

    a[l] = a[j];
    a[j] = v;

    return (j);

}

The complexity of the quick sort algorithm is given in the following table.

AlgorithmWorst caseAverage caseBest case
Quick sortO(n)2log2nlog2n
READ MORE
...