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_tableOpen hashing visualization
MIT OpenCourse - Hashing with Chaining