Hashing With Separate Chaining In C.

As we know that in Hashing, we use a Hash Function that maps keys to certain values. Now, sometimes certain situation arises where these values which we obtain from our hash function collides, Well this conditions are termed as collisions. Now what can be done, so that collision can be prevented, well certain techniques are available which can prevent collisions and these techniques are as follows:

1 ) Closed Hashing, also called as Open Addressing.

2) Open Hashing, also called as Separate Chaining.

Separate Chaining / Open Hashing : 

The idea behind separate chaining is pretty straight forward, what we do in separate chaining is that we make each cell of hash table point to linked list data that corresponds to same hash value (i.e the value obtained from collision between to values.).

Following example can help us better understand the concept, lets create a hash function for N number of objects or numbers, that will be simply,

H.I = Key % N

Where,  H.I is the hash index.

               Key is any number from given set of numbers.

               N is the total of numbers of objects.

Now that we've a hash function let's take an example to start with the explanation, say we've the following sets of input for which we've to determine the hash table using separate chaining technique:

Let's take hash table with 7 buckets ( 0 , 1 , 2 , 3 , 4, 5 , 6 )  so value of N is 7, and the Keys being ( 14 , 16 , 21 , 24 , 18). Now to obtain the hash index for each of these keys we first need to put it in the H.I formula.

For Key = 14 and N =7  we have H.I = 0 ,

Similarly, for Key = 16 and N =7 , H.I = 2,

And for 21 H.I = 0 ,

For 24 H.I = 3 ,

Lastly for Key = 18 , H.I = 4

So, we can represent our Hash Table in like this.

As you can see in index 0 there is a collision between keys 14 and 21, but using separate chaining technique we simply linked the data(14 , 21) to the same hash value.

Hashing with separate chaining C code :

#include<stdio.h>
#include<stdlib.h>

//Declarations Necessary for the Implementation Part.
struct node
{
    int info;
    struct node*link;
};

//Function Declarations
int index(int item);
struct node * insert_sorted(struct node *index,int data);
void search(struct node * index,int item);
struct node*delete_node(struct node *index,int item);
void display(struct node * index);


int main()
{   int data,choice,ind,i;
    struct node * H[10];
    //Initialization
    for(i=0;i<10;i++)
    {
        H[i]=NULL;
    }

    while(1)
    {
        printf("Please select a choice\n");
        printf("1. Insert\n");
        printf("2. Search\n");
        printf("3. Delete\n");
        printf("4. Display\n");
        printf("5. Exit\n");
        scanf("%d",&choice);

    switch(choice)
    {
        case 1:
            {
                printf("Please enter the data\n");
                scanf("%d",&data);
                H[index(data)]=insert_sorted(H[index(data)],data);
                printf("\n\n");
                break;
            }
        case 2:
            {
                printf("Please enter the item\n");
                scanf("%d",&data);
                search(H[index(data)],data);
                printf("\n\n");
                break;
            }
        case 3:
            {
                printf("Please enter the item\n");
                scanf("%d",&data);
                H[index(data)]=delete_node(H[index(data)],data);
                printf("\n\n");
                break;
            }
        case 4:
            {
                printf("Please enter the index to display the link info's\n");
                scanf("%d",&ind);
                display(H[ind]);
                printf("\n\n");
                break;
            }

        case 5:
            {
                printf("Sankyu For Using the Program\n");
                printf("\n\n");
                return 0 ;
            }
        default:
            printf("Wrong Choice\n");
            printf("\n\n");
            break;
    }

    }
return 0;
}

//Function Definitions
int index(int item) //Hash Function
{
    return item%10;
}

struct node * insert_sorted(struct node *index,int data)
{
    struct node* temp=(struct node*)malloc(sizeof(struct node)),*p;
    if(temp==NULL)
    {
        printf("New Node Can't be created\n");
        return index;
    }
    //Inserting the Data.
    temp->info=data;

    //Creating the links.

    if(index==NULL)
        {
            temp->link=NULL;
            index=temp;
            return index;
        }
    else //Insertion in the rest nodes.
        {   //Inserting Data at the Beginning
            if(index->info>data)
                {
                    temp->link=index;
                    index=temp;
                    return index;
                }
            p=index;
            while(p->link!=NULL)
            {
                if(p->link->info<data) //This scans till the last node.
                    p=p->link;
                else
                {
                    temp->link=p->link;
                    p->link=temp;
                    return index;
                }
            }
            //This is to insert the data after the last node.
            p->link=temp;
            temp->link=NULL;
            return index;
        }
};

void search(struct node * index,int item)
{
    struct node *p=index;
    while(p!=NULL&&p->info<=item) //To decrease the search time by breaking
        //search when we get any data which is greater than the data. As after that data
        //We can't get the requested data since the nodes are sorted.
    {
        if(p->info==item)
        {
            printf("Successful Search\n");
            return; //So that the address of the node where the data is present is given to the user.
        }
        p=p->link;
    }

    printf("Unsuccessful Search\n");
    return;
};

struct node*delete_node(struct node *index,int item)
{   if(index==NULL)
    {
            printf("The Index is empty\n");
            return index;
    };

    struct node*p=index,* temp;
    //The starting node has the item itself
    if(p->info==item)
    {
        temp=p;
        index=temp->link;
        free(temp);
        return index;
    }
    while(p->link!=NULL)
    {
        if(p->link->info<=item) //So to stop search after getting a
                                //node greater than the data.
        {
            if(p->link->info==item)
            {
                temp=p->link;
                p->link=temp->link;
                free(temp);
                return index;
            }
            p=p->link;
        }
    }

    printf("Item doesn't exist\n");
    return index;
};

void display(struct node * index)
{
    if(index==NULL)
        {
            printf("Index is empty\n");
            return;
        }
    struct node*p=index;
    while(p!=NULL)
    {
        printf("%d ",p->info);
        p=p->link;
    }
    printf("\n");
    return;
};

Output for the above program is :