HashTable

#include <iostream>

template <class KeyType, class ValueType>
struct Node {
    KeyType key_;
    ValueType value_;
    Node<KeyType, ValueType> *next_{nullptr};

    Node(KeyType key, ValueType value) {
        key_ = key;
        value_ = value;
    }
};

template <class KeyType, class ValueType, class Func = std::hash<KeyType>>
class HashTable {
    size_t count_;
    size_t capacity_;
    Node<KeyType, ValueType> **entries_;
    Func hash_function_;
    double factor_;

public:
    HashTable() {
        capacity_ = 100;
        factor_ = 0.5;
        count_ = 0;
        entries_ = new Node<KeyType, ValueType> *[capacity_];
        for (int i = 0; i < capacity_; ++i) {
            entries_[i] = nullptr;
        }
    }

    explicit HashTable(Func func) {
        capacity_ = 100;
        factor_ = 0.5;
        count_ = 0;
        entries_ = new Node<KeyType, ValueType> *[capacity_];
        for (int i = 0; i < capacity_; ++i) {
            entries_[i] = nullptr;
        }
        hash_function_ = func;
    }

    HashTable(size_t size, double factor, Func func = std::hash<KeyType>()) {
        capacity_ = size;
        count_ = 0;
        if (factor > 1 || factor <= 0) {
            factor_ = 0.5;
        } else {
            factor_ = factor;
        }
        entries_ = new Node<KeyType, ValueType> *[size];
        for (size_t i = 0; i < size; ++i) {
            entries_[i] = nullptr;
        }
        hash_function_ = func;
    }

    ~HashTable() {
        for (int i = 0; i < capacity_; ++i) {
            if (entries_[i] != nullptr) {
                clear(entries_[i]);
            }
        }
        delete[] entries_;
    }

    void insert(KeyType key, ValueType value) {
        size_t hash = hash_function_(key);
        size_t index = indexFor(hash, capacity_);

        auto current_node = entries_[index];
        while (current_node != nullptr) {
            if (hash_function_(current_node->key_) == hash && key == current_node->key_) {
                current_node->value_ = value;
                return;
            }
            current_node = current_node->next_;
        }
        ensureRehash();
        index = indexFor(hash, capacity_);

        auto new_node = new Node<KeyType, ValueType>(key, value);
        new_node->next_ = entries_[index];

        entries_[index] = new_node;
        count_++;
    }

    ValueType *find(KeyType key) {
        size_t hash = hash_function_(key);
        size_t index = indexFor(hash, capacity_);

        auto current_node = entries_[index];

        while (current_node != nullptr) {
            if (hash_function_(current_node->key_) == hash && key == current_node->key_) {
                return &(current_node->value_);
            }
            current_node = current_node->next_;
        }

        return nullptr;
    }

    void erase(KeyType key) {
        size_t hash = hash_function_(key);
        size_t index = indexFor(hash, capacity_);

        Node<KeyType, ValueType> *prior_node = nullptr;
        auto current_node = entries_[index];
        while (current_node != nullptr) {
            if (hash_function_(current_node->key_) == hash && key == current_node->key_) {
                if (prior_node == nullptr) {
                    entries_[index] = entries_[index]->next_;
                } else {
                    prior_node->next_ = current_node->next_;
                }
                delete current_node;
                count_--;
                return;
            }
            prior_node = current_node;
            current_node = current_node->next_;
        }
    }

    Node<KeyType, ValueType> &operator[](uint64_t hash) {
        if (hash < 0 || hash >= capacity_) {
            throw std::out_of_range("");
        }
        if (entries_[hash] == nullptr) {
            throw std::runtime_error("");
        }
        return *(entries_[hash]);
    }

    Node<KeyType, ValueType> at(uint64_t hash) {
        if (hash < 0 || hash >= capacity_) {
            throw std::out_of_range("");
        }
        if (entries_[hash] == nullptr) {
            throw std::runtime_error("");
        }
        return *(entries_[hash]);
    }

    size_t size() const {
        return count_;
    }

    size_t capacity() const {
        return capacity_;
    }

private:
    void clear(Node<KeyType, ValueType> *node) {
        if (node == nullptr) {
            return;
        }
        clear(node->next_);
        delete node;
    }

    void ensureRehash() {
        if (count_ < capacity_ * factor_) {
            return;
        }
        size_t new_capacity = capacity_ * 2;
        auto new_entries = new Node<KeyType, ValueType> *[new_capacity];

        for (size_t i = 0; i < new_capacity; ++i) {
            new_entries[i] = nullptr;
        }

        for (size_t idx = 0; idx < capacity_; ++idx) {
            if (entries_[idx] == nullptr) {
                continue;
            }
            auto current_node = entries_[idx];

            while (current_node != nullptr) {
                auto temp_node = current_node;
                current_node = current_node->next_;
                size_t rehash_idx = indexFor(hash_function_(temp_node->key_), new_capacity);
                temp_node->next_ = new_entries[rehash_idx];
                new_entries[rehash_idx] = temp_node;
            }
        }
        capacity_ = new_capacity;
        delete[] entries_;
        entries_ = new_entries;
    }

    size_t indexFor(size_t hash, size_t capacity) const {
        return hash % capacity;
    }
};