Hashing is a data structure that uses a hash function to map data to a location in the data structure. The hash function takes the data as input and returns an index in the data structure where the data should be stored. However, there can be cases where two different data elements map to the same index in the data structure. This is known as a collision.
For example, suppose we have a hash table with 10 buckets and a hash function that maps data elements to the buckets based on their value. If two data elements have the same hash value, they will be stored in the same bucket, causing a collision.
Collision Resolution Techniques
If there is a collision, we need to resolve it for the data structure to work correctly. There are several techniques to handle collisions in hashing:
- Open Addressing
- Separate Chaining
Open Addressing in Hashing
Open addressing is also known as closed hashing. In open addressing all the keys are stored directly into the hash table. When situation arises where two keys are mapped to the same position, the algorithm searches for the next empty slot in the hash table for storing the key.
There are several techniques for open addressing:
- Linear Probing: In linear probing, if a collision occurs, the algorithm searches for the next empty slot in the hash table by moving one position at a time.
- Quadratic Probing: In quadratic probing, if a collision occurs, the algorithm searches for the next empty slot in the hash table by moving to the next position using a quadratic function.
- Double Hashing: In double hashing, if a collision occurs, the algorithm searches for the next empty slot in the hash table by moving to the next position using a second hash function.
Algorithm of Open Addressing
The algorithm of open addressing is as follows:
1. Calculate the hash value of the key. 2. If the slot is empty, store the key in that slot. 3. If the slot is not empty, use a probing technique to find the next empty slot. 4. Repeat steps 2 and 3 until an empty slot is found.
Example of Open Addressing
Following code demonstrates the open addressing technique using linear probing in C, C++, Python, Java programming languages.
//C Program#include <stdio.h>#include <stdlib.h>#define SIZE 10intcustomHash(int key){return key % SIZE;}intprobe(int H[],int key){int index =customHash(key);int i =0;while(H[(index + i)% SIZE]!=0)
i++;return(index + i)% SIZE;}voidinsert(int H[],int key){int index =customHash(key);if(H[index]!=0)
index =probe(H, key);
H[index]= key;}intsearch(int H[],int key){int index =customHash(key);int i =0;while(H[(index + i)% SIZE]!= key)
i++;return(index + i)% SIZE;}intmain(){int HT[10]={0};insert(HT,12);insert(HT,25);insert(HT,35);insert(HT,26);insert(HT,45);insert(HT,55);insert(HT,65);insert(HT,75);insert(HT,85);insert(HT,95);int result =search(HT,26);if(result ==-1)printf("Key not found\n");elseprintf("Key found at index: %d\n", result);return0;}
Output
The output obtained is as follows −
Key found at index: 7
Separate Chaining in Hashing
Separate chaining is also known as open hashing, in this techniques each slot in the hash table is a linked list. When a collision occurs, the data elements are stored in the linked list at that slot. This allows multiple data elements to be stored at the same index in the hash table.
Separate chaining is a simple and effective technique for handling collisions in hashing. It allows for efficient storage and retrieval of data elements, even when collisions occur.
Types of Separate Chaining
There are several types of separate chaining techniques:
- Simple chaining: In simple chaining, each slot in the hash table is a linked list that stores the data elements that map to that slot.
- Dynamic hashing: In dynamic hashing, the hash table is dynamically resized to accommodate more data elements as needed.
- Extendible hashing: In extendible hashing, the hash table is divided into blocks, and each block stores a subset of the data elements.
Algorithm of Separate Chaining
The algorithm of separate chaining is as follows:
1. Calculate the hash value of the key. 2. Store the key in the linked list at that index. 3. If the linked list is empty, create a new node and store the key in that node. 4. If the linked list is not empty, append the key to the end of the linked list.
Example of Separate Chaining
Following code demonstrates the separate chaining technique using linked list in C, C++, Python, Java programming languages.
//C Program#include <stdio.h>#include <stdlib.h>structNode{int data;structNode* next;};#define SIZE 10intcustomHash(int key){return key % SIZE;}voidinsert(structNode* H[],int key){int index =customHash(key);structNode* newNode =(structNode*)malloc(sizeof(structNode));
newNode->data = key;
newNode->next = H[index];
H[index]= newNode;}intsearch(structNode* H[],int key){int index =customHash(key);structNode* temp = H[index];while(temp !=NULL){if(temp->data == key)return index;
temp = temp->next;}return-1;}intmain(){structNode* HT[10];for(int i =0; i < SIZE; i++)
HT[i]=NULL;insert(HT,12);insert(HT,25);insert(HT,35);insert(HT,26);insert(HT,45);insert(HT,55);insert(HT,65);insert(HT,75);insert(HT,85);insert(HT,95);int result =search(HT,85);if(result ==-1)printf("Key not found\n");elseprintf("Key found at index: %d\n", result);return0;}
Output
The output obtained is as follows −
Key found at index: 5
Open Addressing Vs Separate Chaining
| Open Addressing | Separate Chaining |
|---|---|
| Each slot in the hash table stores a single data element. | Each slot in the hash table stores a linked list of data elements. |
| Requires additional probing to find an empty slot when a collision occurs. | Does not require additional probing, as data elements are stored in a linked list. |
| Can lead to clustering of data elements in the hash table. | Does not lead to clustering, as data elements are stored in separate linked lists. |
| Can be less memory efficient, as each slot stores only one data element. | Can be more memory efficient, as each slot stores a linked list of data elements. |
| Can be faster for small hash tables with few collisions. | Can be faster for large hash tables with many collisions. |
Conclusion
Collision in hashing occurs when two different data elements map to the same index in the data structure. This can be resolved using collision resolution techniques like open addressing and separate chaining. These techniques allow for efficient storage and retrieval of data elements, even when collisions occur.