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 into 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:
Double Hashing
In this collision resolution technique of hashing, all keys are stored in the hash table. In this method,
- To insert a key if the computed hash value location in hash table is
- Unoccupied then save the key in this position.
- Occupied then next address is find out by using a second hash function multiplied by the step until an unoccupied slot is found.
for eg: hash_fun1 + hash_fun2 * 1, hash_fun1 + hash_fun2 * 2, hash_fun1 + hash_fun2 * 3 ..
- To search a key, computed hash value location is compared. If it
- Matches then return the value.
- Didn’t match then next address is find out by using a second hash function multiplied by the step
for eg: hash_fun1 + hash_fun2 * 1, hash_fun1 + hash_fun2 * 2, hash_fun1 + hash_fun2 * 3 ..
until key is found, or unoccupied slot is encountered.
Let’s look into below diagram to understand how double hashing works.
Double Hashing Collision Resolution Implementation
Let’s have a look at the basic class definition of Hashing with Double Hashing collision resolution. Before going ahead have a look into Hashing Implementation.
class Hashing
{
public:
int* m_hash_table;
int m_entries;
int m_size;
int hash_function (int key);
Hashing (int size);
~Hashing ();
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 ();
};
class HashingDoubleHashing: public Hashing
{
public:
HashingDoubleHashing (int size);
~HashingDoubleHashing ();
int second_hash_function (int key);
void insert_data (int data);
void delete_data (int data);
bool search_data (int data);
};
Double Hashing Collision Resolution Class Helper Function
Let’s have a look into the helper function needed by the Double Hashing Class.
HashingDoubleHashing::HashingDoubleHashing (int size): Hashing (size)
{}
HashingDoubleHashing::~HashingDoubleHashing ()
{}
int HashingDoubleHashing::second_hash_function (int key)
{
return (key % (get_size () - 3));
}
Hashing::Hashing (int size): m_entries(0), m_size (size)
{
m_hash_table = new int[size];
for (int i = 0; i < size; i++)
{
m_hash_table[i] = 0;
}
}
Hashing::~Hashing ()
{
if (m_hash_table) {
delete[] m_hash_table;
}
}
int Hashing::get_size ()
{
return m_size;
}
int Hashing::get_entries ()
{
return m_entries;
}
int Hashing::get_load_factor ()
{
return ((float)m_entries / get_size ()) * 100;
}
int Hashing::hash_function (int key)
{
return (key % get_size ());
}
void Hashing::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++)
{
cout << m_hash_table[i] << " ";
if (i % 10 == 0)
cout << endl;
}
cout << endl;
}
Inserting an element in Hash Table
- To insert a key if the computed hash value location in hash table is
- Unoccupied then save the key in this position.
- Occupied then next address is find out by using a second hash function multiplied by the step until an unoccupied slot is found.
for eg: hash_fun1 + hash_fun2 * 1, hash_fun1 + hash_fun2 * 2, hash_fun1 + hash_fun2 * 3 ..
Let’s have a look at the sample function to insert an element in Hash Table.
void HashingDoubleHashing::insert_data (int data)
{
int index = hash_function (data);
if (m_hash_table[index] != 0) {
int index_start = index;
int index_second = second_hash_function (data);
int count = 1;
while (m_hash_table[index] != 0) {
index = (index_start + index_second * count) % get_size ();
count++;
}
}
m_hash_table[index] = data;
m_entries++;
}
Deleting an entry in Hash Table
- To delete a key, computed hash value location is compared. If it
- Matches then return the value.
- Didn’t match then next address is find out by using a second hash function multiplied by the step
for eg: hash_fun1 + hash_fun2 * 1, hash_fun1 + hash_fun2 * 2, hash_fun1 + hash_fun2 * 3 ..
until key is found and deleted, or unoccupied slot is encountered.
Let’s have a look at the sample function to delete an entry in hash table.
void HashingDoubleHashing::delete_data (int data)
{
int index = hash_function (data);
if (m_hash_table[index] != 0) {
int index_start = index;
int index_second = second_hash_function (data);
int count = 1;
while (m_hash_table[index] != 0) {
if (m_hash_table[index] == data) {
cout << "Data " << data << " Found in hash table, deleting !!!" << endl;
m_hash_table[index] = 0;
m_entries--;
return;
}
index = (index_start + index_second * count) % get_size ();
count++;
}
}
cout << "Data " << data << " Not Found in hash table, nothing to delete !!!" << endl;
return;
}
Searching an element in Hash Table
- To search a key, computed hash value location is compared. If it
- Matches then return the value.
- Didn’t match then next address is find out by using a second hash function multiplied by the step
for eg: hash_fun1 + hash_fun2 * 1, hash_fun1 + hash_fun2 * 2, hash_fun1 + hash_fun2 * 3 ..
until key is found, or unoccupied slot is encountered.
Let’s have a look at the sample function to search an entry in hash table.
bool HashingDoubleHashing::search_data (int data)
{
int index = hash_function (data);
if (m_hash_table[index] != 0) {
int index_start = index;
int index_second = second_hash_function (data);
int count = 1;
while (m_hash_table[index] != 0) {
if (m_hash_table[index] == data) {
cout << "Data " << data << " Found in hash table !!!" << endl;
return true;
}
index = (index_start + index_second * count) % get_size ();
count++;
}
}
cout << "Data " << data << " Not Found in hash table !!!" << endl;
return false;
}
Let’s have a look at the sample main function which utilizes above Hash Table class.
int main ()
{
HashingDoubleHashing h (100);
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: 100 Entries: 0 Load factor: 0%
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Printing Hash elements, size: 100 Entries: 8 Load factor: 8%
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 45 0 0 0 449
450 0 0 0 454 0 456 0 458 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 145 0 0 0 0 0 345
Data 913 Not Found in hash table !!!
Data 450 Found in hash table !!!
Data 45 Found in hash table !!!
Data 913 Not Found in hash table, nothing to delete !!!
Data 345 Found in hash table, deleting !!!
