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.
Hash Table Implementation
Let’s have a look at the basic class definition of hash table.
class Hashing
{
private:
int* m_hash_table;
int m_entries;
int m_size;
int hash_function (int key);
public:
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 ();
};
Hash Table Class Helper Function
Let’s have a look at the helper functions needed by Hashing class.
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 an element “X” in hash table
- Pass the element “X” to hash function to calculate hash code.
- Insert the element “X” at the hash code index if the place is unoccupied else reject.
Please note that, implementation of Hash table shown here doesn’t handle collision resolution.
Let’s have a look at the sample function to insert an element in Hash Table.
/* In case of collision, we are rejecting key insertion in Hash table */
void Hashing::insert_data (int data)
{
int index = hash_function (data);
if (m_hash_table[index] != 0) {
cout << "collision occured for key " << data << " !!!" << endl;
} else {
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 else element “X” is not present in Hash table.
Let’s have a look at the sample function to delete an entry in hash table.
/* Since no collision is present in hash table, hence we can directly delete
* the entry if it is present */
void Hashing::delete_data (int data)
{
int index = hash_function (data);
if (m_hash_table[index] == 0) {
cout << "key " << data << " not present in hash map, nothing to delete !!!" << endl;
} else {
m_hash_table[index] = 0;
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 element “X” is present in Hash table.
Let’s have a look at the sample function to search an entry in hash table.
/* Since no collision is present in hash table, hence we can directly return
* success, if hash code index is occupied */
bool Hashing::search_data (int data)
{
int index = hash_function (data);
if (m_hash_table[index] == 0) {
cout << "key " << data << " not present in hash map, search fails !!!" << endl;
return false;
}
cout << "key " << data << " present in hash map, search successful !!!" << endl;
return true;
}
Let’s have a look at the sample main function which utilizes above Hash Table class.
int main ()
{
Hashing h(50);
h.insert_data (545);
h.insert_data (78);
h.insert_data (65);
h.insert_data (99);
h.insert_data (476);
h.insert_data (688);
h.insert_data (913);
h.print_element ();
h.search_data (67);
h.search_data (545);
h.search_data (476);
h.search_data (913);
h.delete_data (545);
h.delete_data (78);
h.delete_data (65);
h.delete_data (99);
h.delete_data (476);
h.delete_data (688);
h.delete_data (913);
}
Let’s analyze the output of above main function.
Printing Hash elements, size: 50 Entries: 7 Load factor: 14%
0
0 0 0 0 0 0 0 0 0 0
0 0 913 0 65 0 0 0 0 0
0 0 0 0 0 476 0 78 0 0
0 0 0 0 0 0 0 688 0 0
0 0 0 0 545 0 0 0 99
key 67 not present in hash map, search fails !!!
key 545 present in hash map, search successful !!!
key 476 present in hash map, search successful !!!
key 913 present in hash map, search successful !!!
