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:
Quadratic Probing
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 calculated by adding successive polynomial value to the hash code at a time until an unoccupied slot is found, and key is saved.
For eg: hash_code + 12, hash_code + 22, hash_code + 32 …
- To search a key, computed hash value location is compared. If it
- Matches then return the value.
- Didn’t match then next address is calculated by adding successive polynomial value to the hash code at a time until an unoccupied slot is found and key us saved.
For eg: hash_code + 12, hash_code + 22, hash_code + 32 …
until key is found, or unoccupied slot is encountered.
Let’s look into below diagram to understand how quadratic probing works.
Quadratic Probing Collision Resolution Implementation
Let’s have a look at the basic class definition of Hashing with Linear Probing 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 HashingQuadraticProbing: public Hashing
{
public:
HashingQuadraticProbing (int size);
~HashingQuadraticProbing ();
int quadratic_probing (int index, int loop);
void insert_data (int data);
void delete_data (int data);
bool search_data (int data);
};
Quadratic Probing Collision Resolution Class Helper Function
Let’s have a look into the helper functions needed by the Quadratic Probing class.
HashingQuadraticProbing::HashingQuadraticProbing (int size): Hashing (size)
{}
HashingQuadraticProbing::~HashingQuadraticProbing ()
{}
int HashingQuadraticProbing::quadratic_probing (int index, int loop)
{
return (index + (loop * loop)) % get_size ();
}
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 calculated by adding successive polynomial value to the hash code at a time until an unoccupied slot is found, and key is saved.
For eg: hash_code + 12, hash_code + 22, hash_code + 32 …
Let’s have a look at the sample function to insert an element in Hash Table.
void HashingQuadraticProbing::insert_data (int data)
{
if (get_entries () >= get_size ()) {
cout << "No space to insert, Hash table is full!!" << endl;
}
int index = hash_function (data);
int loop = 1;
while (m_hash_table[index] != 0) {
index = quadratic_probing (index, loop);
loop++;
}
m_hash_table[index] = data;
m_entries++;
}
Deleting an element in Hash Table
- To delete a key, computed hash value location is compared. If it
- Matches then delete the value.
- Didn’t match then next address is calculated by adding successive polynomial value to the hash code at a time until an unoccupied slot is found and key us saved.
For eg: hash_code + 12, hash_code + 22, hash_code + 32 …
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 HashingQuadraticProbing::delete_data (int data)
{
int index = hash_function (data);
int loop = 1;
while (m_hash_table[index] != 0) {
if (m_hash_table[index] == data) {
m_hash_table[index] = 0;
m_entries--;
cout << "Data " << data << " Found in hash table, deleting !!!" << endl;
return;
}
index = quadratic_probing (index, loop);
loop++;
}
cout << "Data " << data << " Not Found in hash table, nothing to delete !!!" << endl;
}
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 calculated by adding successive polynomial value to the hash code at a time until an unoccupied slot is found and key us saved.
For eg: hash_code + 12, hash_code + 22, hash_code + 32 …
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 HashingQuadraticProbing::search_data (int data)
{
int index = hash_function (data);
int loop = 1;
while (m_hash_table[index] != 0) {
if (m_hash_table[index] == data) {
cout << "Data " << data << " Found in hash table !!!" << endl;
return true;
}
index = quadratic_probing (index, loop);
loop++;
}
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 ()
{
HashingQuadraticProbing 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 145 0 0 449
345 450 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 0 0 0 0 0 0 0
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 !!!
