Quick and dirty separately-chained Hashtable.

hashtable.cpp

#include <functional>
#include <iostream>
#include <stdexcept>
#include <string>

template <typename Key, typename Value>
class HashTable {
 public:
  using size_t       = unsigned long;
  using HashFunction = std::function<size_t(const Key&)>;

  static const size_t LOAD_FACTOR      = 5;
  static const size_t GROWTH_FACTOR    = 2;
  static const size_t SHRINK_THRESHOLD = 4;
  static const size_t MINIMUM_CAPACITY = 8;

  explicit HashTable(size_t capacity       = LOAD_FACTOR * MINIMUM_CAPACITY,
                     HashFunction pre_hash = std::hash<Key>{})
  : _size(0)
  , _capacity(capacity / LOAD_FACTOR)
  , _threshold(capacity)
  , _nodes(new Node*[_capacity])
  , _pre_hash(pre_hash) {
    _make_null();
  }

  ~HashTable() {
    _clear();
  }

  bool insert(const Key& key, const Value& value) {
    auto index = _hash(key);

    for (auto node = _nodes[index]; node; node = node->next) {
      if (node->key == key) {
        node->value = value;
        return false;
      }
    }

    auto new_node = new Node{key, value, _nodes[index]};
    _nodes[index] = new_node;

    if (++_size == _threshold) {
      _reallocate(_capacity * GROWTH_FACTOR);
    }

    return true;
  }

  bool contains(const Key& key) const noexcept {
    auto index = _hash(key);
    for (auto node = _nodes[index]; node; node = node->next) {
      if (node->key == key) return true;
    }

    return false;
  }

  Value& get(const Key& key) noexcept {
    auto index = _hash(key);
    for (auto node = _nodes[index]; node; node = node->next) {
      if (node->key == key) {
        return node->value;
      }
    }

    throw std::invalid_argument("No such key!");
  }

  const Value& get(const Key& key) const noexcept {
    auto index = _hash(key);
    for (auto node = _nodes[index]; node; node = node->next) {
      if (node->key == key) {
        return node->value;
      }
    }

    throw std::invalid_argument("No such key!");
  }

  Value& operator[](const Key& key) {
    auto index = _hash(key);

    for (auto node = _nodes[index]; node; node = node->next) {
      if (node->key == key) {
        return node->value;
      }
    }

    auto new_node = new Node{key, Value(), _nodes[index]};
    _nodes[index] = new_node;

    if (++_size == _threshold) {
      _reallocate(_capacity * GROWTH_FACTOR);
    }

    return new_node->value;
  }

  void erase(const Key& key) {
    auto index = _hash(key);

    Node* previous = nullptr;
    for (auto node = _nodes[index]; node; previous = node, node = node->next) {
      if (node->key == key) {
        if (previous) {
          previous->next = node->next;
        } else {
          _nodes[index] = node->next;
        }

        delete node;

        if (--_size == _threshold / SHRINK_THRESHOLD) {
          _reallocate((_size / LOAD_FACTOR) * GROWTH_FACTOR);
        }
        return;
      }
    }

    throw std::invalid_argument("No such key!");
  }

  void clear() {
    _clear();
    _reallocate(MINIMUM_CAPACITY);
  }

  size_t size() const noexcept {
    return _size;
  }

  bool is_empty() const noexcept {
    return size() == 0;
  }

 private:
  struct Node {
    const Key key;
    Value value;
    Node* next;
  };

  size_t _hash(const Key& key) const noexcept(noexcept(_pre_hash)) {
    static const size_t a = 69;
    static const size_t b = 99;
    static const size_t p = 2147483647;

    return ((a * _pre_hash(key) + b) % p) % _capacity;
  }

  // size_t _fast_hash(const Key& key) {
  //   static const size_t a         = 99;
  //   static const size_t b         = 123;
  //   static const size_t word_size = sizeof(size_t) * 8;
  //
  //   auto intermediate = static_cast<size_t>(a * _pre_hash(key) + b);
  //
  //   return intermediate >> (word_size - _table_bits);
  // }

  void _reallocate(size_t new_capacity) {
    if (new_capacity < MINIMUM_CAPACITY) {
      new_capacity = MINIMUM_CAPACITY;
    }
    if (new_capacity == _capacity) return;

    auto old          = _nodes;
    auto old_capacity = _capacity;

    _capacity  = new_capacity;
    _threshold = _capacity * LOAD_FACTOR;

    _nodes = new Node*[_capacity];
    _make_null();

    _rehash(old, old_capacity);
  }

  void _rehash(Node** old, size_t old_capacity) {
    for (size_t old_index = 0; old_index < old_capacity; ++old_index) {
      for (auto node = old[old_index]; node;) {
        auto new_index = _hash(node->key);
        auto next      = node->next;

        node->next        = _nodes[new_index];
        _nodes[new_index] = node;

        node = next;
      }
    }
  }

  void _clear() {
    for (size_t index = 0; index < _capacity; ++index) {
      for (auto node = _nodes[index]; node;) {
        auto next = node->next;
        delete node;
        node = next;
      }
    }

    delete[] _nodes;
  }

  void _make_null() {
    for (size_t index = 0; index < _capacity; ++index) {
      _nodes[index] = nullptr;
    }
  }

  size_t _size;
  size_t _capacity;
  size_t _threshold;

  Node** _nodes;
  HashFunction _pre_hash;
};

auto main() -> int {
  HashTable<int, std::string> table;

  table[0] = "zero";
  table[1] = "one";
  table.insert(2, "two");

  std::cout << std::boolalpha << std::endl;

  std::cout << table.get(0) << std::endl;
  std::cout << table.contains(2) << std::endl;
  std::cout << table.contains(5) << std::endl;

  std::cout << table.contains(1) << std::endl;
  table.erase(1);
  std::cout << table.contains(1) << std::endl;
}