# 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"

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

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].

## 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
*/
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