Basic Hash Map (Hash Table) implementation in C++

HashMap.h

// Hash map class template
template <typename K, typename V, typename F = KeyHash<K>>
class HashMap {
public:
    HashMap() {
        // construct zero initialized hash table of size
        table = new HashNode<K, V> *[TABLE_SIZE]();
    }

    ~HashMap() {
        // destroy all buckets one by one
        for (int i = 0; i < TABLE_SIZE; ++i) {
            HashNode<K, V> *entry = table[i];
            while (entry != NULL) {
                HashNode<K, V> *prev = entry;
                entry = entry->getNext();
                delete prev;
            }
            table[i] = NULL;
        }
        // destroy the hash table
        delete [] table;
    }

    bool get(const K &key, V &value) {
        unsigned long hashValue = hashFunc(key);
        HashNode<K, V> *entry = table[hashValue];

        while (entry != NULL) {
            if (entry->getKey() == key) {
                value = entry->getValue();
                return true;
            }
            entry = entry->getNext();
        }
        return false;
    }

    void put(const K &key, const V &value) {
        unsigned long hashValue = hashFunc(key);
        HashNode<K, V> *prev = NULL;
        HashNode<K, V> *entry = table[hashValue];

        while (entry != NULL && entry->getKey() != key) {
            prev = entry;
            entry = entry->getNext();
        }

        if (entry == NULL) {
            entry = new HashNode<K, V>(key, value);
            if (prev == NULL) {
                // insert as first bucket
                table[hashValue] = entry;
            } else {
                prev->setNext(entry);
            }
        } else {
            // just update the value
            entry->setValue(value);
        }
    }

    void remove(const K &key) {
        unsigned long hashValue = hashFunc(key);
        HashNode<K, V> *prev = NULL;
        HashNode<K, V> *entry = table[hashValue];

        while (entry != NULL && entry->getKey() != key) {
            prev = entry;
            entry = entry->getNext();
        }

        if (entry == NULL) {
            // key not found
            return;
        }
        else {
            if (prev == NULL) {
                // remove first bucket of the list
                table[hashValue] = entry->getNext();
            } else {
                prev->setNext(entry->getNext());
            }
            delete entry;
        }
    }

private:
    // hash table
    HashNode<K, V> **table;
    F hashFunc;
};

Hey aozturk,

Your page has moved to here: https://medium.com/@aozturk/simple-hash-map-hash-table-implementation-in-c-931965904250

Cheers,

• Hershal

Hi Hershal,
Brilliant catch :) Many thanks.

Hi aozturk,

I was wondering how do you implement hashFunc?
Especially how to handle different types from template.

Many thanks.

Hi, thanks for asking.
The full project is here: HashMap project
and the related blog post of mine is here: blog post

Hi aozturk,
Excellent post and example.
But I actually tried to make a hash_func with with my Class using this and boos unordered_map, and I've waste days.
I think will not be so difficult for you as it is for me. But I don´t know how to start. Thank you for help.
I know I need a hash_func but don´t know with ou without the Node, or just the bitset.
I need something like this:

1. typedef std::unordered_map<bitset<300>, Node> myHashmap;
2. typedef std::unordered_map<int, myHashmap > myHashMap;

My class Node is like this:
class Node
{
public:
Node() { id = 0;}
virtual ~Node() {}
int getId(){return id;}
void setId(int id){this->id = id;}
bool operator==(const Node& node) const
{
return (id == node.id);
}
Node& operator=(const Node& node)
{
id = node.id;
return *this;
}
Node operator=(const Node &n)
{
id = n.id;
}
protected:

private:
    int id;

};