I am trying a simple Hash Map implementation in c++. I have used this and this as reference. The implemented design uses a class HashEntry
to manage individual key-value pair. The class HashMap
handles the map itself. The map has functions to insert(put
) a key-value pair, to retrieve(get
) value based on a key and to erase(erase
) a key-value pair. It also keeps track of its size
and capacity
. Here is the commented code:
#include <iostream>
#include <memory>
#include <vector>
#include <cstddef>
#include <stdexcept>
#include <climits>
// Class for individual entries of key-value pair
class HashEntry
{
int key_v;
int val_v;
// The smart pointer to handle multiple keys with same hash value.
// This will be used to create a linkedlist.
std::shared_ptr<HashEntry> next_v;
public:
HashEntry(int key, int val) : key_v{key}, val_v{val}
{}
int key() const
{
return key_v;
}
int val() const
{
return val_v;
}
std::shared_ptr<HashEntry> next() const
{
return next_v;
}
void set_val(int val)
{
val_v = val;
}
void set_next(std::shared_ptr<HashEntry> next)
{
next_v = next;
}
};
// Class for the Hash Map
class HashMap
{
std::vector<std::shared_ptr<HashEntry>> map_v;
std::size_t capacity_v{0};
std::size_t size_v{0};
public:
HashMap(std::size_t);
std::size_t hash_func(int);
std::size_t size() const;
void put(int, int);
int get(int);
bool erase(int);
};
HashMap::HashMap(std::size_t capacity)
{
capacity_v = capacity;
map_v.resize(capacity_v);
}
// The hashing function
std::size_t HashMap::hash_func(int key)
{
return key % capacity_v;
}
std::size_t HashMap::size() const
{
return size_v;
}
// The function to insert key-value pair
void HashMap::put(int key, int val)
{
// If capacity is reached, throw exception
if(size_v == capacity_v)
{
throw std::length_error{"Capacity exceeded!\n"};
}
std::size_t hash_value = hash_func(key);
// If the hash_value has never been set before, use that space
// for key-value pair. Otherwise, add to the list.
if(map_v[hash_value] == nullptr)
{
map_v[hash_value] = std::make_shared<HashEntry>(key, val);
}
else
{
auto node = map_v[hash_value];
std::shared_ptr<HashEntry> pre = nullptr;
while(node)
{
if(node->key() == key)
{
node->set_val(val);
return;
}
pre = node;
node = node->next();
}
pre->set_next(std::make_shared<HashEntry>(key, val));
}
size_v++;
}
// Retrieve value based on key
int HashMap::get(int key)
{
auto hash_value = hash_func(key);
auto node = map_v[hash_value];
// If node is not set, nothing to retrieve.
// Otherwise, check the key and if required, the associated list.
// If not found, report the issue.
if(node == nullptr)
{
std::cout << "Key not found! Returning INT_MIN for: " << key << "\n";
return INT_MIN;
}
if(node->next() == nullptr && node->key() == key)
{
return node->val();
}
else
{
while(node)
{
if(node->key() == key)
{
return node->val();
}
node = node->next();
}
}
std::cout << "Key not found! Returning INT_MIN for: " << key << "\n";
return INT_MIN;
}
// Remove key-value pair based on key
bool HashMap::erase(int key)
{
auto hash_value = hash_func(key);
// If no value is set against hash value, there is nothing to erase.
// Otherwise, check if keys match and if yes, proceed to erase.
// Otherwise, check the list for a match and if there is a match,
// proceed to erase.
// Otherwise, return false.
if(map_v[hash_value] == nullptr)
{
return false;
}
else if(map_v[hash_value]->key() == key)
{
map_v[hash_value] = map_v[hash_value]->next();
size_v--;
return true;
}
else if(map_v[hash_value]->next())
{
auto pre = map_v[hash_value];
auto node = map_v[hash_value]->next();
while(node)
{
if(node->key() == key)
{
pre->set_next(node->next());
size_v--;
return true;
}
pre = node;
node = node->next();
}
}
return false;
}
int main()
{
HashMap hm1{10};
std::cout << "Size: " << hm1.size() << "\n";
for(int i = 0; i < 10; i++)
{
hm1.put(i, i + 10);
}
std::cout << "Size: " << hm1.size() << "\n";
std::cout << "Get: " << hm1.get(6) << "\n";
std::cout << "Erase: " << std::boolalpha << hm1.erase(6) << "\n";
std::cout << "Size: " << hm1.size() << "\n";
// Check the output of get() after key is erased
std::cout << "Get: " << hm1.get(6) << "\n";
// Try adding a key which will have same hash_value as another key
// Also try retrieving both keys
hm1.put(15, 25);
std::cout << "Size: " << hm1.size() << "\n";
std::cout << "Get: " << hm1.get(15) << "\n";
std::cout << "Get: " << hm1.get(5) << "\n";
// Erase a pair existing in the list and see how all keys in the list behave.
std::cout << "Erase: " << std::boolalpha << hm1.erase(5) << "\n";
std::cout << "Size: " << hm1.size() << "\n";
std::cout << "Get: " << hm1.get(5) << "\n";
std::cout << "Get: " << hm1.get(15) << "\n";
return 0;
}
Questions:
1) Is the implementation correct for an open hashing (closed addressing) hash map?
2) The function get
returns an INT_MIN
if it has no other choice. The other possible ways to handle this scenario could be using std::optional
, throw an exception, change the function to not return anything, or return a bool. Is there any other smarter/ more elegant way?
3) Any better suggestions for hash_func
. Is there any good reading material on how to select a good hashing function or is it just a matter of experience?
If possible, kindly provide general reviews and suggestions. Thank you!