by Hashing is a technique used to search an specific item in large group of items. Hashing uses hash table to perform search in an constant O(1) time. Hashing uses hash functions to fill items in a hash table. To search, each key is passed into the same hash function which computes an index which provides the corresponding value location.
Before going ahead have a look into Hashing Explanation.
Let’s have a look at the ideal Hash Table.
Collision
At times Hash Functions can generate same Hash code for different set of keys. In this case, both the keys needs to be placed at the same location. This scenario where multiple keys hash codes are same is called Collision.
Collision Resolution
A collision in hashing occurs when couple of keys have same hash codes. To handle such scenarios following collision resolution techniques can be used:
Separate Chaining
This is one of the most common collision resolution technique which uses a linked list to store all the keys having same hash code. In this case, each place in Hash table can be a linked list.
- In separate chaining, each key is inserted into a linked list present at the hash code location in hash table.
- While searching for a key,
- Linked list is identified using the hash code generated by the hash function for the key.
- Key is searched in the linked list by traversing through it.
Let’s have a look into the below diagram to understand how separate chaining stores and searches the data.
Separate Chaining Collision Resolution Implementation
Let’s have a look at the basic class definition of Hashing with Separate Chaining collision resolution. Before going ahead have a look into Linked List Implementation.
#include "LinkedList.h"
#define HASHING_SEPARATE_CHAINING_MAX_ENTRIES 10
class HashingSeparateChaining
{
private:
LinkedList* m_hash_table[HASHING_SEPARATE_CHAINING_MAX_ENTRIES];
int m_entries;
int m_size;
int hash_function (int key);
public:
HashingSeparateChaining ();
~HashingSeparateChaining ();
int get_size ();
int get_entries ();
int get_load_factor ();
void insert_data (int data);
void delete_data (int data);
bool search_data (int data);
void print_element ();
};
Separate Chaining Collision Resolution Class Helper Function
Let’s have a look at the helper functions needed by Hashing class.
HashingSeparateChaining::HashingSeparateChaining (): m_entries(0), m_size(HASHING_SEPARATE_CHAINING_MAX_ENTRIES)
{
for (int i = 0; i < HASHING_SEPARATE_CHAINING_MAX_ENTRIES; i++)
{
m_hash_table[i] = NULL;
}
}
HashingSeparateChaining::~HashingSeparateChaining ()
{
for (int i = 0; i < HASHING_SEPARATE_CHAINING_MAX_ENTRIES; i++)
{
if (m_hash_table[i]) {
delete_all_node (&m_hash_table[i]->next);
}
m_hash_table[i] = NULL;
}
}
int HashingSeparateChaining::get_size ()
{
return m_size;
}
int HashingSeparateChaining::get_entries ()
{
return m_entries;
}
int HashingSeparateChaining::get_load_factor ()
{
cout << "For Separate Chaining Load factor is not applicable !!" << endl;
return 0;
}
int HashingSeparateChaining::hash_function (int key)
{
return (key % get_size ());
}
void HashingSeparateChaining::print_element ()
{
cout << "Printing Hash elements, size: " << get_size () <<
" Entries: " << get_entries () << " Load factor: " << get_load_factor () << "%" << endl;
int size = get_size ();
for (int i = 0; i < size; i++)
{
if (m_hash_table[i]) {
print_linked_list (m_hash_table[i]);
} else {
cout << "NULL" << endl;
}
}
cout << endl;
}
Inserting an element in Hash Table
To insert an element “X” in hash table
- Pass the element “X” to hash function to calculate hash code.
- Insert the element “X” in the Linked List at the hash code index.
Let’s have a look at the sample function to insert an element in Hash Table.
void HashingSeparateChaining::insert_data (int data)
{
int index = hash_function (data);
if (m_hash_table[index]) {
cout << "collision occured for key " << data << ", handling it !!!" << endl;
}
insert_at_begining (&m_hash_table[index], data);
m_entries++;
}
Deleting an element in Hash Table
To delete an element “X” in Hash table
- Pass the element “X” to hash function and calculate the hash code of element “X”.
- If hash table is occupied at hash code index then delete the entry from the LinkedList at the hash code index location.
Let’s have a look at the sample function to delete an entry in hash table.
void HashingSeparateChaining::delete_data (int data)
{
int index = hash_function (data);
if (!m_hash_table[index]) {
cout << "key " << data << " not present in hash map, nothing to delete !!!" << endl;
return;
}
if (delete_searched_node (&m_hash_table[index], data)) {
cout << "key " << data << " present in hash map, deleted !!!" << endl;
m_entries--;
}
}
Searching an element in Hash Table
To search an element “X” in Hash table
- Pass the element “X” to hash function and calculate the hash code of element “X”.
- If hash table is occupied at hash code index then search for element “X” in LinkedList present in Hash code index.
Let’s have a look at the sample function to search an entry in hash table.
bool HashingSeparateChaining::search_data (int data)
{
int index = hash_function (data);
if (!m_hash_table[index]) {
cout << "key " << data << " not present in hash map!!!" << endl;
return false;
}
if (search_element (m_hash_table[index], data)) {
cout << "key " << data << " present in hash map!!!" << endl;
return true;
}
return false;
}
Let’s have a look at the sample main function which utilizes above Hash Table class.
int main ()
{
HashingSeparateChaining h;
h.print_element ();
h.insert_data (45);
h.insert_data (145);
h.insert_data (345);
h.insert_data (454);
h.insert_data (456);
h.insert_data (458);
h.insert_data (449);
h.insert_data (450);
h.print_element ();
h.search_data (913);
h.search_data (450);
h.search_data (45);
h.delete_data (913);
h.delete_data (345);
}
Let’s analyze the output of above main function.
Printing Hash elements, size: 10 Entries: 0 Load factor: For Separate Chaining Load factor is not applicable !!
0%
NULL
NULL
NULL
NULL
NULL
NULL
NULL
NULL
NULL
NULL
collision occured for key 145, handling it !!!
collision occured for key 345, handling it !!!
Printing Hash elements, size: 10 Entries: 8 Load factor: For Separate Chaining Load factor is not applicable !!
0%
450
NULL
NULL
NULL
454
345 145 45
456
NULL
458
449
key 913 not present in hash map!!!
Found the searched data: 450
key 450 present in hash map!!!
Found the searched data: 45
key 45 present in hash map!!!
key 913 not present in hash map, nothing to delete !!!
Node found, going to delete
key 345 present in hash map, deleted !!!
