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:
Linear 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 find out by moving one place at a time until an unoccupied slot is found and key us saved.
- To search a key, computed hash value location is compared. If it
- Matches then return the value.
- Didn’t match then next address key is compared by moving one place at a time until key is found, or unoccupied slot is encountered.
Let’s look into below diagram to understand how linear probing works.
Linear 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 HashingLinearProbing: public Hashing
{
public:
HashingLinearProbing (int size);
~HashingLinearProbing ();
int linear_probing (int index);
void insert_data (int data);
void delete_data (int data);
bool search_data (int data);
};
Linear Probing Collision Resolution Class Helper Function
Let’s have a look into the helper function needed by the Linear Probing Class.
HashingLinearProbing::HashingLinearProbing (int size): Hashing (size)
{}
HashingLinearProbing::~HashingLinearProbing ()
{}
int HashingLinearProbing::linear_probing (int index)
{
return (index + 1) % 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 find out by moving one place at a time until an unoccupied slot is found and key us saved.
Let’s have a look at the sample function to insert an element in Hash Table.
void HashingLinearProbing::insert_data (int data)
{
if (get_entries () >= get_size ()) {
cout << "No space to insert, Hash table is full!!" << endl;
}
int index = hash_function (data);
while (m_hash_table[index] != 0) {
index = linear_probing (index);
}
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 key is compared by moving one place at a time 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 HashingLinearProbing::delete_data (int data)
{
int index = hash_function (data);
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 = linear_probing (index);
}
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 key is compared by moving one place at a time 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 HashingLinearProbing::search_data (int data)
{
int index = hash_function (data);
while (m_hash_table[index] != 0) {
if (m_hash_table[index] == data) {
cout << "Data " << data << " Found in hash table !!!" << endl;
return true;
}
index = linear_probing (index);
}
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 ()
{
HashingLinearProbing 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 345 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 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 !!!
