What exactly is hash table chaining?
Chaining serves as a method for avoiding collisions in hash tables.
A collision happens when two different keys are hashed to the same index within a hash table. This poses a problem as each slot in the hash table is intended to accommodate only a single element.
The chaining method
The hash table in the chaining method consists of an array of linked lists, where each index maintains its individual linked list.
All key-value pairs that correspond to the same index will be placed within the linked list associated with that index.
The Advantages of Chaining
- Insertion in a hash table always occurs in O(1) through chaining because linked lists allow insertion in constant time.
- A chained hash table can theoretically grow indefinitely as long as there is enough space.
- A chained hash table will never need to be resized.
Implementation of Chaining
Let's create a hash function to guarantee that our hash table contains 'N' buckets.
To insert a new node into the hash table, the initial step involves identifying the hash index corresponding to the provided key. Alternatively, this can be calculated by utilizing the hash function.
Example: hashIndex = key % noOfBuckets
Place the new node at the end of the list in the bucket matching the calculated hash index.
To remove a node from a hash table, the process involves determining the hash index for the key, navigating to the associated bucket based on this index, locating the node with the specified key within the bucket's list, and then eliminating it if it exists.
Algorithm
For Insert:
Example
Begin
Declare Function Insert(int k, int v)
int hash_v = HashFunc(k)
HashTableEntry* p = NULL
HashTableEntry* en = ht[hash_v]
while (en!= NULL)
p = en
en= en->n
if (en == NULL)
en = new HashTableEntry(k, v)
if (p == NULL)
ht[hash_v] = en
else
p->n= en
else
en->v = v
End.
For Delete:
Example
Begin
Declare Function Remove(int k)
int hash_v = HashFunc(k)
HashTableEntry* en = ht[hash_v]
HashTableEntry* p= NULL
if (en == NULL or en->k != k)
Print "No Element found at key"
return
while (en->n != NULL)
p = en
en = en->n
if (p != NULL)
p->n = en->n
delete en
Print "Element Deleted"
End.
For Search:
Example
Begin
Declare function SearchKey(int k)
int hash_v = HashFunc(k)
bool flag = false
HashTableEntry* en = ht[hash_v]
if (en != NULL)
while (en != NULL)
if (en->k == k)
flag = true
if (flag)
Print "Element found at key"
Print en->v
en = en->n
if (!flag)
Print "No Element found at key"
End.
Example
#include <iostream>
const int T_S = 200;
using namespace std;
struct HashTableEntry {
int v, k;
HashTableEntry *n;
HashTableEntry *p;
HashTableEntry(int k, int v) {
this->k = k;
this->v = v;
this->n = NULL;
}
};
class HashMapTable {
public:
HashTableEntry **ht, **top;
HashMapTable() {
ht = new HashTableEntry*[T_S];
for (int i = 0; i < T_S; i++)
ht[i] = NULL;
}
int HashFunc(int key) {
return key % T_S;
}
void Insert(int k, int v) {
int hash_v = HashFunc(k);
HashTableEntry* p = NULL;
HashTableEntry* en = ht[hash_v];
while (en!= NULL) {
p = en;
en = en->n;
}
if (en == NULL) {
en = new HashTableEntry(k, v);
if (p == NULL) {
ht[hash_v] = en;
} else {
p->n = en;
}
} else {
en->v = v;
}
}
void Remove(int k) {
int hash_v = HashFunc(k);
HashTableEntry* en = ht[hash_v];
HashTableEntry* p = NULL;
if (en == NULL || en->k != k) {
cout<<"No Element found at key "<<k<<endl;
return;
}
while (en->n != NULL) {
p = en;
en = en->n;
}
if (p != NULL) {
p->n = en->n;
}
delete en;
cout<<"Element Deleted"<<endl;
}
void SearchKey(int k) {
int hash_v = HashFunc(k);
bool flag = false;
HashTableEntry* en = ht[hash_v];
if (en != NULL) {
while (en != NULL) {
if (en->k == k) {
flag = true;
}
if (flag) {
cout<<"Element found at key "<<k<<": ";
cout<<en->v<<endl;
}
en = en->n;
}
}
if (!flag)
cout<<"No Element found at key "<<k<<endl;
}
~HashMapTable() {
delete [] ht;
}
};
int main() {
HashMapTable hash;
int k, v;
int c;
while (1) {
cout<<"1.Insert element into the table"<<endl;
cout<<"2.Search element from the key"<<endl;
cout<<"3.Delete element at a key"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Enter your choice: ";
cin>>c;
switch(c) {
case 1:
cout<<"Enter element to be inserted: ";
cin>>v;
cout<<"Enter key at which element to be inserted: ";
cin>>k;
hash.Insert(k, v);
break;
case 2:
cout<<"Enter key of the element to be searched: ";
cin>>k;
hash.SearchKey(k);
break;
case 3:
cout<<"Enter key of the element to be deleted: ";
cin>>k;
hash.Remove(k);
break;
case 4:
exit(1);
default:
cout<<"\nEnter correct option\n";
}
}
return 0;
}
Output
Output
1. Insert element into the table
2. Search element from the key
3. Delete element at a key
4. Exit
Enter your choice: 1
Enter element to be inserted: 2
Enter key at which element to be inserted: 1
1. Insert element into the table
2. Search element from the key
3. Delete element at a key
4. Exit
Enter your choice: 1
Enter element to be inserted: 3
Enter key at which element to be inserted: 4
1. Insert element into the table
2. Search element from the key
3. Delete element at a key
4. Exit
Enter your choice: 1
Enter element to be inserted: 7
Enter key at which element to be inserted: 6
1. Insert element into the table
2. Search element from the key
3. Delete element at a key
4. Exit
Enter your choice: 1
Enter element to be inserted: 8
Enter key at which element to be inserted: 9
1. Insert element into the table
2. Search element from the key
3. Delete element at a key
4. Exit
Enter your choice: 2
Enter key of the element to be searched: 6
Element found at key 6: 7
1. Insert element into the table
2. Search element from the key
3. Delete element at a key
4. Exit
Enter your choice: 2
Enter key of the element to be searched: 7
No Element found at key 7
1. Insert element into the table
2. Search element from the key
3. Delete element at a key
4. Exit
Enter your choice: 3
Enter key of the element to be deleted: 9
Element Deleted
1. Insert element into the table
2. Search element from the key
3. Delete element at a key
4. ExitC
Enter your choice: 4
Time Complexity:
- Search : O (1+(n/m))
- Delete : O (1+(n/m))
- where n = Number of slots in Hash table m = Number of keys to be inserted Here n/m is the Load Factor.
- Load Factor must be as small as possible.
