A HashTable optimised for a large in-memory storage

Question

I've been making this pet project of mine which is an implementation of a HashTable for a very specific purpose: storing huge amounts of objects in-memory (think Redis). I ended up with this implementation in C++ which is in my opinion a very basic and generic Java-inspired HashTable using buckets. I'd like to hear advice on what to do next to make those narrow optimizations and what approaches are the best to try out. Also I've strived to make my code in the spirit of STL, and I don't think I managed to do that properly (C++ isn't my main language, I actually come from Python).

You can clone the code with tests here (github link, cmake 3.13 or higher required)

#pragma once
//
// Created by korbiwe on 2019-02-05.
//

#include <functional>
#include <vector>
#include <list>
#include <string>

#include "util.h"

namespace lib {

namespace {
using index_t = unsigned;
};


template<class Key, class T, class Hash = std::hash<T>>
class HashTable {
public:
  using key_t = Key;
  using mapped_t = T;
  using pair_t = std::pair<const Key, T>;
  using bucket_t = std::list<pair_t>;
  using table_t = std::vector<bucket_t>;
  using reference = pair_t&;
  using const_reference = const pair_t&;

  explicit HashTable(size_t capacity = 8, double load_factor = 0.75);

  T& at(const Key& key);

  T& operator[](const Key& key);

  void erase(const Key& key);

  void insert(const pair_t& pair);

  size_t size() const;

  bool empty() const;

private:
  void _expand_and_rehash();

  const bucket_t& _resolve_key(const Key& key) const;

  bucket_t& _resolve_key(const Key& key);

  size_t _capacity;
  size_t _size = 0;
  double _load_factor;
  table_t _table;
  Hash _hash_f;
};

template<class Key, class T, class Hash>
HashTable<Key, T, Hash>::HashTable(size_t capacity, double load_factor) :
    _capacity(round_up_to_power_of_two(capacity)),
    _load_factor(load_factor),
    _table(table_t(_capacity)) {

}

template<class Key, class T, class Hash>
void HashTable<Key, T, Hash>::insert(const HashTable::pair_t& pair) {
  Key key = pair.first;
  T value = pair.second;

  bucket_t& bucket = _resolve_key(key);
  bucket.push_back(pair);

  _size++;

  if (_size > _capacity * _load_factor)
    _expand_and_rehash();

}

template<class Key, class T, class Hash>
T& HashTable<Key, T, Hash>::at(const Key& key) {
  bucket_t& bucket = _resolve_key(key);
#ifdef DEBUG
  std::cout << "Lookup in a bucket with " << std::to_string(bucket.size()) << " elements.";
#endif
  auto found = std::find_if(bucket.begin(), bucket.end(), [&key](pair_t pair) { return pair.first == key; });
  if (bucket.empty() || found == bucket.end()) {
    throw std::out_of_range("HashTable::at");
  }
  return found->second;
}

template<class Key, class T, class Hash>
void HashTable<Key, T, Hash>::_expand_and_rehash() {
#ifdef DEBUG
  std::cout << "Rehashing at capacity "
            << std::to_string(_capacity)
            << " and size "
            << std::to_string(_size)
            << "."
            << std::endl;

  std::cout << "Load factor at "
            << std::to_string(static_cast<double>(_size) / _capacity)
            << " before rehashing"
            << std::endl;
#endif

  table_t temporary = _table;
  _capacity *= 2;
  _table = table_t(_capacity);
  for (bucket_t bucket : temporary) {
    if (bucket.empty()) continue;

    for (pair_t entry : bucket) {
      bucket_t& new_bucket = _resolve_key(entry.first);
      new_bucket.push_back(entry);
    }
  }

#ifdef DEBUG
  std::cout
          << "... and "
          << std::to_string(static_cast<double>(_size) / _capacity)
          << " after rehashing."
          << std::endl;
#endif
}

template<class Key, class T, class Hash>
T& HashTable<Key, T, Hash>::operator[](const Key& key) {
  bucket_t& bucket = _resolve_key(key);
#ifdef DEBUG
  std::cout << "Lookup in a bucket with " << std::to_string(bucket.size()) << " elements.";
#endif
  auto found = std::find_if(bucket.begin(), bucket.end(), [&key](const pair_t& pair) { return pair.first == key; });
  if (bucket.empty() || found == bucket.end()) {
    pair_t& default_ = bucket.emplace_back(key, T());
    return default_.second;
  }
  return found->second;
}

template<class Key, class T, class Hash>
bool HashTable<Key, T, Hash>::empty() const {
  return _size == 0;
}

template<class Key, class T, class Hash>
size_t HashTable<Key, T, Hash>::size() const {
  return _size;
}

template<class Key, class T, class Hash>
void HashTable<Key, T, Hash>::erase(const Key& key) {
  bucket_t& bucket = _resolve_key(key);
  auto found = std::find_if(bucket.begin(), bucket.end(), [&key](const pair_t& pair) { return pair.first == key; });
  if (bucket.empty() || found == bucket.end()) {
    throw std::out_of_range("HashTable::erase");
  }
  bucket.erase(found);
}

template<class Key, class T, class Hash>
const typename HashTable<Key, T, Hash>::bucket_t& HashTable<Key, T, Hash>::_resolve_key(const Key& key) const {
  return _table[_hash_f(key) % _capacity];
}

template<class Key, class T, class Hash>
typename HashTable<Key, T, Hash>::bucket_t& HashTable<Key, T, Hash>::_resolve_key(const Key& key) {
  return _table[_hash_f(key) % _capacity];
}

}; // end namespace lib

Answer 1

Missing includes:

#include <cstddef>
#include <stdexcept>
#include <utility>

#ifdef DEBUG
#include <iostream>
#endif

Also, std::size_t is misspelt throughout.

---

We seem to be missing const overloads for at() and operator[]. They are certainly worth having.

---

There's a few instances of the code to find a particular key within a bucket:

auto found = std::find_if(bucket.begin(), bucket.end(),
                          [&key](const pair_t& pair) { return pair.first == key; });

(my linebreak added for legibility).

It's probably worth refactoring that into a small function of its own (remember that it's almost certainly going to be inlined, making no change to the object code).

That's frequently followed by

  if (bucket.empty() || found == bucket.end()) {

There's no value in the bucket.empty() test - if the bucket was empty, then found will inevitable be bucket.end(). (There's no benefit to moving the bucket.empty() test before the std::find_f(); just remove it).

---

We could make the member function signatures much easier to read by including the definitions within the class body. For example, compare this:

template<class Key, class T, class Hash>
const typename HashTable<Key, T, Hash>::bucket_t& HashTable<Key, T, Hash>::_resolve_key(const Key& key) const {
  return _table[_hash_f(key) % _capacity];
}

template<class Key, class T, class Hash>
typename HashTable<Key, T, Hash>::bucket_t& HashTable<Key, T, Hash>::_resolve_key(const Key& key) {
  return _table[_hash_f(key) % _capacity];
}

with:

private:

    const bucket_t& _resolve_key(const Key& key) const
    {
        return _table[_hash_f(key) % _capacity];
    }

    bucket_t& _resolve_key(const Key& key)
    {
        return _table[_hash_f(key) % _capacity];
    }

---

To reduce copying, I think insert() should take its argument by value, and then std::move() it:

void HashTable<Key, T, Hash>::insert(HashTable::pair_t pair)
{
    bucket_t& bucket = _resolve_key(pair.first);
    bucket.push_back(std::move(pair));

In passing, should insert() allow us to add elements with keys that are already in the bucket? That's not what std::unordered_map::insert() does.

_expand_and_rehash() is another function where we could usefully move instead of copying. We should be able to get the whole class working with move-only types; it's worth adding tests that instantiate and use the class with T as (say) std::unique_ptr and dealing with copies until that works.

---

Since this is intended to hold "huge amounts" of entries, we really need a reserve() member, for those cases where we construct before knowing how many elements we'll add (e.g. when a HashTable is a member of some other object).

Consider the usage pattern (mainly the mix of insert, lookup, and erase) to decide whether std::list is the appropriate type for bucket_t. We might want to implement our own (perhaps a "chunked list", for example, to reduce the number of individual allocations).

---

It's just style, but I'm not a big fan of prefixing the private members with _. It makes the code look like Python rather than C++, and hurts readability.

I have a simple theory that if we need a mnemonic to keep track of which identifiers are which, then there's probably too much in the class and we need to think about splitting its responsibilities.

---

Final thought: I'm not sure what I'm missing, but I don't see anything here that makes this class any more suitable than std::unordered_map for "huge numbers of objects". That suggests we need to add some comments to point out the adaptations.

Answer 2

In your constructor, you can construct _table with just _table(capacity).

In _expand_and_rehash, you're making copies of vectors you don't need to make. First, you can move table to temporary using table_t temporary = std::move(table);. When copying the data to the new table, you're creating copies of the lists. Use a rerefences in those loop: for (const bucket_t &bucket : temporary) and for (const pair_t &entry : bucket). Then replace new_bucket.push_back with new_bucket.emplace_back, which will avoid another potential copy.

You might be able to defer the check for a rehash which is made in insert to the next insert. (i.e., check for if a rehash is necessary at the start of insert, rather than at the end.) The downside is that you wouldn't be able to insert an object already in the HashTable. Which brings up an important point: you currently allow duplicates. If you insert the same thing twice, you'll get two copies of that key in the HashTable. Is that what you want? (erase will delete the first one it finds if there is more than one.)

There's no need to check bucket.empty() after your various calls to find_if, since if the bucket is empty the find_if won't find what you're looking for and will return bucket.end() (which you're already checking for).

In insert, you can remove the local value variable, which is unused. There's no real reason to have key in there, either, since it is only used once.