Open hashing or separate chaining

Open hashing is a collision avoidence method which uses array of linked list to resolve the collision.

It is also known as the separate chaining method (each linked list is considered as a chain).

Example

Let's assume table size as 3.

Then the array of linked list will be,

-------------         -------------
|           |         |           |
| chain[0]  |-------> |    NULL   |
|           |         |           |
-------------         -------------
-------------         -------------
|           |         |           |
| chain[1]  |-------> |    NULL   |
|           |         |           |
-------------         -------------
-------------         -------------
|           |         |           |
| chain[2]  |-------> |    NULL   |
|           |         |           |
-------------         -------------

Initialize each list to NULL.

i)Insert 6

Hash key = 6 % 3 = 0.

Hence add the node with data 6 in the chain[0].

 -------------         ----------------
 |           |         |     |        |
 | chain[0]  |-------> |  6  | NULL   |
 |           |         |     |        |
 -------------         ----------------
 -------------         -------------
 |           |         |           |
 | chain[1]  |-------> |    NULL   |
 |           |         |           |
 -------------         -------------
 -------------         -------------
 |           |         |           |
 | chain[2]  |-------> |    NULL   |
 |           |         |           |
 -------------         -------------

ii)Insert 12

Hash key = 12 % 3 = 0

Collision! Both 6 and 12 points to the hash index 0.

We can avoid the collision by adding data 12 at the end of the chain[0].

This how we can avoid the collision in separate chaining method.

-------------         ----------------        ----------------
|           |         |     |        |        |     |        |
| chain[0]  |-------> |  6  |        |------> |  12 | NULL   |
|           |         |     |        |        |     |        |
-------------         ----------------        ----------------
-------------         -------------
|           |         |           |
| chain[1]  |-------> |    NULL   |
|           |         |           |
-------------         -------------
-------------         -------------
|           |         |           |
| chain[2]  |-------> |    NULL   |
|           |         |           |
-------------         -------------

iii)Insert 10

Hash key = 10 % 3 = 1.

Hence add node with data 10 in the chain[1].

-------------         ----------------        ----------------
|           |         |     |        |        |     |        |
| chain[0]  |-------> |  6  |        |------> |  12 | NULL   |
|           |         |     |        |        |     |        |
-------------         ----------------        ----------------
-------------         ----------------
|           |         |     |        |
| chain[1]  |-------> |  10 |  NULL  |
|           |         |     |        |
-------------         ----------------
-------------         -------------
|           |         |           |
| chain[2]  |-------> |    NULL   |
|           |         |           |
-------------         -------------




Algorithm | Insert data into the separate chain

1. Declare an array of a linked list with the hash table size.

2. Initialize an array of a linked list to NULL.

3. Find hash key.

4. If chain[key] == NULL

     Make chain[key] points to the key node.

5. Otherwise(collision),

     Insert the key node at the end of the chain[key].




Separate chaining implementation in c

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

#define size 7

struct node
{
    int data;
    struct node *next;
};

struct node *chain[size];

void init()
{
    int i;
    for(i = 0; i < size; i++)
        chain[i] = NULL;
}

void insert(int value)
{
    //create a newnode with value
    struct node *newNode = malloc(sizeof(struct node));
    newNode->data = value;
    newNode->next = NULL;

    //calculate hash key
    int key = value % size;

    //check if chain[key] is empty
    if(chain[key] == NULL)
        chain[key] = newNode;
    //collision
    else
    {
        //add the node at the end of chain[key].
        struct node *temp = chain[key];
        while(temp->next)
        {
            temp = temp->next;
        }

        temp->next = newNode;
    }
}

void print()
{
    int i;

    for(i = 0; i < size; i++)
    {
        struct node *temp = chain[i];
        printf("chain[%d]-->",i);
        while(temp)
        {
            printf("%d -->",temp->data);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main()
{
    //init array of list to NULL
    init();

    insert(7);
    insert(0);
    insert(3);
    insert(10);
    insert(4);
    insert(5);

    print();

    return 0;
}

Output

chain[0]-->7 -->0 -->NULL

chain[1]-->NULL

chain[2]-->NULL

chain[3]-->3 -->10 -->NULL

chain[4]-->4 -->NULL

chain[5]-->5 -->NULL

chain[6]-->NULL





Searching a value from the hash table

1. Get the value

2. Compute the hash key.

3. Search the value in the entire chain. i.e. chain[key].

4. If found, print "Search Found"

5. Otherwise, print "Search Not Found"




Searching an element in separate chaining implementation

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

#define size 7

struct node
{
    int data;
    struct node *next;
};

struct node *chain[size];

void init()
{
    int i;
    for(i = 0; i < size; i++)
        chain[i] = NULL;
}

void insert(int value)
{
    //create a newnode with value
    struct node *newNode = malloc(sizeof(struct node));
    newNode->data = value;
    newNode->next = NULL;

    //calculate hash key
    int key = value % size;

    //check if chain[key] is empty
    if(chain[key] == NULL)
        chain[key] = newNode;
    //collision
    else
    {
        //add the node at the end of chain[key].
        struct node *temp = chain[key];
        while(temp->next)
        {
            temp = temp->next;
        }

        temp->next = newNode;
    }
}

/*
 * return 1, search found
 * return 0, Otherwise
 */
int search(int value)
{
    int key = value % size;
    struct node *temp = chain[key];
    while(temp)
    {
        if(temp->data == value)
            return 1;
        temp = temp->next;
    }
    return 0;
}

void print()
{
    int i;

    for(i = 0; i < size; i++)
    {
        struct node *temp = chain[i];
        printf("chain[%d]-->",i);
        while(temp)
        {
            printf("%d -->",temp->data);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main()
{
    //init array of list to NULL
    init();

    insert(7);
    insert(0);
    insert(3);
    insert(10);
    insert(4);
    insert(5);

    print();

    printf("Searching element 10\n");

    if(search(10))
        printf("Search Found\n");
    else
        printf("Search Not Found\n");

    return 0;
}

Output

chain[0]-->7 -->0 -->NULL

chain[1]-->NULL

chain[2]-->NULL

chain[3]-->3 -->10 -->NULL

chain[4]-->4 -->NULL

chain[5]-->5 -->NULL

chain[6]-->NULL

Searching element 10

Search Found





Removing an element from a separate chaining

To remove an element from the hash table, We need to find the correct chain. i.e. chain[value%key].

After the chain found, we have to use linked list deletion algorithm to remove the element.

1. Get the value

2. Compute the key.

3. Using linked list deletion algorithm, delete the element from the chain[key].

Linked List Deletion Algorithm: Deleting a node in the linked list

4. If unable to delete, print "Value Not Found"




Removing an element from a separate chaining implementation

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

#define size 7

struct node
{
    int data;
    struct node *next;
};

struct node *chain[size];

void init()
{
    int i;
    for(i = 0; i < size; i++)
        chain[i] = NULL;
}

void insert(int value)
{
    //create a newnode with value
    struct node *newNode = malloc(sizeof(struct node));
    newNode->data = value;
    newNode->next = NULL;

    //calculate hash key
    int key = value % size;

    //check if chain[key] is empty
    if(chain[key] == NULL)
        chain[key] = newNode;
    //collision
    else
    {
        //add the node at the end of chain[key].
        struct node *temp = chain[key];
        while(temp->next)
        {
            temp = temp->next;
        }

        temp->next = newNode;
    }
}

/*
 * return 1, successful delete
 * return 0, value not found
 */
int del(int value)
{
    int key = value % size;
    struct node *temp = chain[key], *dealloc;
    if(temp != NULL)
    {
        if(temp->data == value)
        {
            dealloc = temp;
            temp = temp->next;
            free(dealloc);
            return 1;
        }
        else
        {
            while(temp->next)
            {
                if(temp->next->data == value)
                {
                    dealloc = temp->next;
                    temp->next = temp->next->next;
                    free(dealloc);
                    return 1;
                }
                temp = temp->next;
            }
        }
    }

    return 0;
}

void print()
{
    int i;

    for(i = 0; i < size; i++)
    {
        struct node *temp = chain[i];
        printf("chain[%d]-->",i);
        while(temp)
        {
            printf("%d -->",temp->data);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main()
{
    //init array of list to NULL
    init();

    insert(7);
    insert(0);
    insert(3);
    insert(10);
    insert(4);
    insert(5);

    print();

    if(del(10))
    {
        printf("After Deletion of 10\n");
        print();
     }
    else
        printf("Value Not Present\n");

    return 0;
}

Output

chain[0]-->7 -->0 -->NULL

chain[1]-->NULL

chain[2]-->NULL

chain[3]-->3 -->10 -->NULL

chain[4]-->4 -->NULL

chain[5]-->5 -->NULL

chain[6]-->NULL

After Deletion of 10

chain[0]-->7 -->0 -->NULL

chain[1]-->NULL

chain[2]-->NULL

chain[3]-->3 -->NULL

chain[4]-->4 -->NULL

chain[5]-->5 -->NULL

chain[6]-->NULL




Useful Resources

https://en.wikipedia.org/wiki/Hash_table
Open hashing visualization
MIT OpenCourse - Hashing with Chaining

Topics You Might Like