C++ - Hash map implementation using smart pointers

Question

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!

Answer 1

I read both your reference implementers. They look more like Java that has been literally translated to C++. Though it may work neither of these are very good implementations and as such yours suffers from the same problems.

Design

Design of Hash

Your hash seems to have a limit on the number of elements.

if(size_v == capacity_v)
{
    throw std::length_error{"Capacity exceeded!\n"};
}

But there does not seem to be a need for this. Each bucket in the hash is basically a list of linked elements. So you can store as many members as you like per list. So there really is no need for a size.

Hashing function are hard to write. The version you use can be used as a reasonable one but under a few conditions. The main one is that the value you use to diveide by (and thus the number of buckets) should be a prime number.

std::size_t HashMap::hash_func(int key)
{
    return key % capacity_v;  // here capacity should be prime.
}                             // This will give you a much larger chance of 
                              // of not creating some pattern and using some
                              // buckets more than others.

I know this does not sound important but there is some significant maths done on this problem (make this prime it will save you a lot of headaches.

Alternatively you can use std::hash to generate you a better number that is less likely to clash (that use the module operator on that to get the actual index number).

Design of C++

You use std::shared_ptr to link all the elements in the list together. Personally I would have used a pointer (its self contained and you can control all the uses). But there is an argument for using a smart pointer (just not std::shared_ptr).

In this situation there is no sharing of the pointer. Each pointer is owned by exactly one parent. So use std::unique_ptr this will handle all the management of the pointer without the extra overhead needed by shared pointer.

Design of Interface

Your interface is put/get/erase.

The only big issue I see is the get(). What happens when you get a key that does not exist? You return a magic value (which is a bit of a code smell). How do you distinguish the magic value from a real value (do you prevent the magic value from being inserted?).

There is a small issue around put(). What happens if you put a key that already exists. Simply overwrite it? Sure that works. Might be nice to warn in this situation.

To me the put/get design has an issue for me in that it requires a two phase update. If I want to modify a key I first have to get the value associated with the key manipulate and then put the value back. In C++ we usually perform a retrieve from a container via a reference. That way once you have the value you can manipulate it directly. Also this makes it more efficient as you are not re-calculating the location using a hash and search on a list.

 int&  value = cont.get(23);
 value = value + 5; // update in place as we are using a reference.

It even looks really nice if you overload operator[] so it looks like a normal array accesses.

 int&  value = cont[23];
 value = value + 5; // update in place as we are using a reference.

 // Or simply
 cont[23] += 5;

Code Review

I would have put this class as a private member of HashMap.

class HashEntry {}

It does not seem to be leaked by any of the HashMap interfaces (which is good) so it does not need to be exposed to the user. Also by making it private you can remove the get/set methods which are completely useless in this context.

Sure you can keep this simple first time and just use int as the key and value. But in C++ when we make containers we usually create them generically so anything can be the key or value. I would have a look at templates.

    int key_v;
    int val_v;

OK. You can use a smart pointer to manage this chain.

    // 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;

But std::shared_ptr is the wrong smart pointer. Use std::unique_ptr.

OK I see why you had to use std::shared_ptr. You don't use references anywhere in your code. Which means that all values are copied on return. std::unique_ptr is non copyable which would be an issue here. You still need to use std::unique_ptr but you need to return by reference to make this work.

    std::shared_ptr<HashEntry> next() const

Prefer to use the initializer list.

HashMap::HashMap(std::size_t capacity)
{
    capacity_v = capacity;      // put this in the initializer list.
    map_v.resize(capacity_v);
}

This function does not change the state of the container. You can also mark it const.

std::size_t HashMap::hash_func(int key)
{
    return key % capacity_v;
}

OK. You do need to search the list to see if it exists and over-right on a push (would be nice to know if I did over-right).

// The function to insert key-value pair
void HashMap::put(int key, int val)
{
        while(node)
        {
            if(node->key() == key)
            {
                node->set_val(val);
                return;
            }
            pre = node;
            node = node->next();
        }

BUT I think it is a bad idea to add to the end.

        pre->set_next(std::make_shared<HashEntry>(key, val));

There is a concept of locality of reference. If you have used something then you will probably use it again soon (or a value close it). So if you put the value at the front a subsequent get (or over-righting put) will not have to perform as long of a search. So I would put the new value at the beginning of the chain.

In this function:

// Retrieve value based on key
int HashMap::get(int key)
{

I am not sure why you have this extra if statement

    if(node->next() == nullptr && node->key() == key)
    {
        return node->val();
    }

Seems redundant to me.

Answer 2

Good for the first try, but there are a lot of things to improve.

Too many indirections

std::shared_ptr -> std::unique_ptr, because no multithreading is perceived in the usage cases, std::unique_ptr is much more lightweight, albeit being a little bit harder to use. It compiles down to safe code written by hand.

std::vector<std::shared_ptr<HashEntry>> -> std::vector<HashEntry>, because backwards links are not established anyway, and resizing is never done.

Interface

Not generic (e.g. not a template).

I would rather return empty std::optional than print a message to stdout.

HashEntry should be private to the map.

I don't see any reason for hash_func to be public. It is not used outside of the class, nor is it stated that it is supposed to be used outside.

get should be const member too.

Doesn't provide any way to iterate over entire map.