A simple hash map implementation.

HashMap.hpp

#include <cstddef>
#include <functional>
#include <vector>

template <typename K, typename V>
class HashMap
{
public:
    HashMap(size_t capacity = initial_capacity)
        : nodes_(capacity) {
    }

    virtual ~HashMap() {
        // free all nodes
        for(auto head : nodes_) {
            auto node = head;
            while(node != nullptr) {
                auto tmp = node;
                node = node->next;
                delete tmp;
            }
        }
    }

    // insert a key-value pair
    void insert(const K& key, const V& value) {
        (*this)[key] = value;
    }

    // delete a key-value pair by key
    void erase(const K& key) {
        const auto index = get_index_by_key(key);
        
        // find node with matching key value
        Node* prev = nullptr;
        auto node = nodes_[index];
        while(node != nullptr) {
            if(node->key == key) {
                break;
            }
            prev = node;
            node = node->next;
        }
        
        // if the node exists, delete it from the linked list
        if(node) {
            if(prev) {
                prev->next = node->next;
            } else {
                nodes_[index] = node->next;
            }
            delete node;
            size_--;
        }
    }

    V& operator[](const K& key) {
        const auto index = get_index_by_key(key);
        
        // find node with matching key value
        auto node = nodes_[index];
        while(node != nullptr) {
            if(node->key == key) {
                break;
            }
            node = node->next;
        }
        
        // if the node does not exist, create a new one and add it to the head of the linked list
        if(node == nullptr) {
            node = new Node;
            node->key = key;
            node->next = nodes_[index];
            nodes_[index] = node;
            size_++;

            if(size_ >= capacity() * load_factor) {
                rehash();
            }
        }
        return node->value;
    }

    // return the number of nodes
    size_t size() const {
        return size_;
    }

    size_t capacity() const {
        return nodes_.size();
    }

private:
    struct Node {
        K     key;            // store key value of this key-value pair
        V     value;          // store value
        Node* next = nullptr; // point to next node, if it does not exist, the value should be nullptr
    };

    // get the array(nodes_) index by key
    size_t get_index_by_key(const K& key) {
        if constexpr ((initial_capacity & (initial_capacity - 1)) == 0) {
            return std::hash<K>{}(key) & (capacity() - 1); // capacity() is a power of 2.
        } else {
            return std::hash<K>{}(key) % capacity();
        }
    }

    // expands the capacity and rehash the table
    void rehash() {
        std::vector<Node*> old = nodes_;
        nodes_.resize(2 * capacity()); // expand to double capacity
        for(auto head : old) {
            auto node = head;
            while(node != nullptr) {
                insert(node->key, node->value);
                node = node->next;
            }
        }
    }

    size_t             size_ = 0; // sotre the number of all nodes
    std::vector<Node*> nodes_;    // store linked lists

    static constexpr size_t initial_capacity = 1 << 4; // must be a power of 2.
    static constexpr float  load_factor      = 0.75f;
};