C++ Hash table, Hash function, benchmark vs std::unordered_set and std::hash

Question

I wrote my own hash function and my own hash table.

My hash function seems to work surprisingly well!

Feel free to comment anything!

Hash function:

#ifndef __CLRS4_HASH_FUNCTION_H__
#define __CLRS4_HASH_FUNCTION_H__

#include <bit>
#include <common.h>

namespace frozenca::hard {

using namespace std;


template <size_t a> struct HashBase {
  constexpr size_t operator()(size_t k) const {
    return 2 * k * k + a * k;
  }
};

template <size_t a, size_t r> struct HashF {
  constexpr size_t operator()(size_t k) const {
    if constexpr (r > 0) {
      return HashF<a, r - 1>{}(k);
    } else {
      return HashBase<a>{}(k);
    }
  }
};

template <Scalar T, size_t a = 123UL, size_t r = 4UL> 
struct Hash {
  constexpr size_t operator()(const T& key) const {
    if constexpr (sizeof(T) == sizeof(size_t)) {
      return HashF<a + 128, r>{}(bit_cast<size_t>(key));
    } else if constexpr (sizeof(T) == sizeof(uint8_t)) {
      return HashF<a + 16, r>{}(static_cast<size_t>(bit_cast<uint8_t>(key)));
    } else if constexpr (sizeof(T) == sizeof(uint16_t)) {
      return HashF<a + 32, r>{}(static_cast<size_t>(bit_cast<uint16_t>(key)));
    } else if constexpr (sizeof(T) == sizeof(uint32_t)) {
      return HashF<a + 64, r>{}(static_cast<size_t>(bit_cast<uint32_t>(key)));
    } else {
      []<bool flag = false>() {
        static_assert(flag, "Not supported sizeof(T)");
      }();
    }
  }    
};


} // namespace frozenca::hard

#endif //__CLRS4_HASH_FUNCTION_H__

Hash table:

#ifndef __CLRS4_HASH_TABLE_H__
#define __CLRS4_HASH_TABLE_H__

#include <bit>
#include <common.h>
#include <hashfunction.h>
#include <iomanip>
#include <iostream>
#include <linkedlist.h>
#include <vector>

namespace frozenca::hard {

using namespace std;

namespace detail {

template <Containable K, typename V, typename Hasher, bool AllowDup>
requires Hashable<Hasher, K>
class HashTable {
  // invariant: V is either K or pair<const K, Value> for some Value type.
  static constexpr bool is_set_ = is_same_v<K, V>;

  using Node = ListNode<V>;

  LinkedList<V> values_;

  // invariant: K cannot be mutated
  // so if V is K, ListIter is const iterator.
  // if V is pair<const K, value>, ListIter is non-const iterator (but only
  // value can be mutated)
  using ListIter = ListIterator<V, is_set_>;

  // invariant: buckets_.size() == 0 or must be a power of 2
  // each "bucket" is a pair of two ListIter [begin, end)
  // invariant: begin <= end, and all iterators between begin and end
  // points to elements with the same hash value, with keys in sorted order.
  using Buckets = vector<ListIter>;
  Buckets buckets_;

  // invariant: buckets.size() == 0 or bucket_mask_ == buckets_.size() - 1
  size_t bucket_mask_ = 0;

  static constexpr size_t growth_factor_early_ = 4UL;
  static constexpr size_t growth_factor_ = 2UL;

  // ideally, this should be equal to half of the initial nonempty capacity of std::vector...
  static constexpr size_t initial_nonempty_bucket_count_ = 8UL;
  static constexpr size_t bucket_count_threshold_ = 128UL;

  static constexpr float max_load_factor_ = 1.0f;

  struct KeyProj {
    K operator()(const V &value) const noexcept {
      if constexpr (is_set_) {
        return value;
      } else {
        return value.first;
      }
    }
  };

  size_t get_hash(const K &key) const noexcept { return Hasher{}(key); }

  size_t bucket_from_key(const K &key) const noexcept {
    return get_hash(key) & bucket_mask_;
  }

  size_t bucket(const V &value) const noexcept {
    return bucket_from_key(KeyProj{}(value));
  }

public:
  using key_type = K;
  using value_type = V;
  using reference_type = V &;
  using const_reference_type = const V &;
  using iterator_type = ListIter;
  using const_iterator_type = ListIterator<V, true>;
  // hash tables have no reverse iterators!

  HashTable() = default;
  ~HashTable() = default;

private:
  void clone_buckets(const Buckets &other_buckets) {
    // clone bucket iterator pairs one by one
    // precondition: values_ are already cloned
    auto this_bucket_curr = values_.begin();

    buckets_.clear();
    buckets_.reserve(other_buckets.size());
    for (size_t i = 0; i < other_buckets.size(); i += 2) {
      auto this_bucket_begin = this_bucket_curr;
      auto other_bucket_curr = other_buckets[i];
      while (other_bucket_curr != other_buckets[i + 1]) {
        ++this_bucket_curr;
        ++other_bucket_curr;
      }
      auto this_bucket_end = this_bucket_curr;
      buckets_.push_back(this_bucket_begin);
      buckets_.push_back(this_bucket_end);
    }
    assert(this_bucket_curr == values_.end());
  }

public:
  HashTable(const HashTable &other) : values_{other.values_} {
    clone_buckets(other.buckets_);
  }
  HashTable &operator=(const HashTable &other) {
    values_ = other.values_;
    clone_buckets(other.buckets_);
    return *this;
  }
  HashTable(HashTable &&other) noexcept = default;
  HashTable &operator=(HashTable &&other) noexcept = default;

  [[nodiscard]] iterator_type begin() noexcept {
    return iterator_type(values_.begin());
  }

  [[nodiscard]] const_iterator_type begin() const noexcept {
    return const_iterator_type(values_.begin());
  }

  [[nodiscard]] const_iterator_type cbegin() const noexcept {
    return const_iterator_type(values_.cbegin());
  }

  [[nodiscard]] iterator_type end() noexcept {
    return iterator_type(values_.end());
  }

  [[nodiscard]] const_iterator_type end() const noexcept {
    return const_iterator_type(values_.end());
  }

  [[nodiscard]] const_iterator_type cend() const noexcept {
    return const_iterator_type(values_.end());
  }

  [[nodiscard]] bool empty() const noexcept { return values_.empty(); }

  [[nodiscard]] ptrdiff_t size() const noexcept { return values_.size(); }

  void clear() noexcept {
    values_.clear();
    buckets_.clear();
    bucket_mask_ = 0;
  }

  size_t bucket_count() const noexcept { return (buckets_.size() >> 1); }

  float load_factor() const noexcept {
    if (empty()) {
      return 0.0f;
    }
    return static_cast<float>(size()) / static_cast<float>(buckets_.size());
  }

  float max_load_factor() const noexcept { return max_load_factor_; }

private:
  [[nodiscard]] pair<bool, size_t> need_rehash() const noexcept {
    if (buckets_.empty()) {
      return {true, initial_nonempty_bucket_count_};
    } else {
      float next_load_factor =
          static_cast<float>(size() + 1) / static_cast<float>(bucket_count());
      if (next_load_factor >= max_load_factor_) {
        if (bucket_count() < bucket_count_threshold_) {
          return {true, bucket_count() * growth_factor_early_};
        } else {
          return {true, bucket_count() * growth_factor_};
        }
      } else {
        return {false, 0};
      }
    }
  }

  void rehash(size_t next_bucket_size) {
    assert(has_single_bit(next_bucket_size));
    buckets_.assign(next_bucket_size << 1, end());

    bucket_mask_ = next_bucket_size - 1;

    auto curr_it = begin();
    auto end_it = end();

    while (curr_it != end_it) {
      auto value = *curr_it;
      auto bucket_index = bucket(value);
      auto next_it = next(curr_it);

      auto &lo = buckets_[(bucket_index << 1)];
      auto &hi = buckets_[(bucket_index << 1) + 1];

      if (lo == hi) {
        assert(lo == end() && hi == end());
        lo = curr_it;
        hi = next_it;
        curr_it = next_it;
        continue;
      }

      // insertion point
      auto it = ranges::lower_bound(lo, hi, value, less<K>{}, KeyProj{});
      assert(it != next_it);
      if (it == curr_it) {
        assert(it == hi && hi != end());
        ++hi;
      } else if (it == lo) {
        assert(it != begin());
        auto &prev_hi = buckets_[(bucket(*prev(it)) << 1) + 1];
        assert(prev_hi == lo);
        values_.splice(it, curr_it, next_it);
        lo = curr_it;
        prev_hi = lo;
      } else {
        assert(hi != end());
        auto &next_hi = buckets_[(bucket(*hi) << 1) + 1];
        if (next_hi == curr_it) {
          ++next_hi;
        }
        values_.splice(it, curr_it, next_it);
      }

      curr_it = next_it;
    }
  }

  iterator_type find_key_in_bucket(size_t bucket_index,
                                   const K &key) const noexcept {
    auto value = [&]() {
      if constexpr (is_set_) {
        return key;
      } else {
        return V{key, key};
      }
    };
    return find_in_bucket(bucket_index, value());
  }

  iterator_type find_in_bucket(size_t bucket_index,
                               const V &value) const noexcept {
    auto lo = buckets_[bucket_index << 1];
    auto hi = buckets_[(bucket_index << 1) + 1];
    auto it = ranges::lower_bound(lo, hi, value, less<K>{}, KeyProj{});
    if (it == hi || (value != *it)) {
      return end();
    } else {
      return it;
    }
  }

  size_t erase_key_from_bucket(size_t bucket_index, const K &key) {
    auto lo = buckets_[bucket_index << 1];
    auto hi = buckets_[(bucket_index << 1) + 1];
    auto value = [&]() {
      if constexpr (is_set_) {
        return key;
      } else {
        return V{key, key};
      }
    };
    auto it = ranges::lower_bound(lo, hi, value(), less<K>{}, KeyProj{});
    if (it == hi || (value() != *it)) {
      return 0;
    } else {
      erase_from_bucket(bucket_index, it);
      return 1;
    }
  }

  iterator_type erase_from_bucket(size_t bucket_index, iterator_type iter) {
    auto &lo = buckets_[bucket_index << 1];
    if (iter == lo) {
      ++lo;
    }

    if (iter != begin()) {
      auto prev_bucket = bucket(*prev(iter));
      auto &prev_lo = buckets_[prev_bucket << 1];
      auto &prev_hi = buckets_[(prev_bucket << 1) + 1];
      if (iter == prev_hi) {
        ++prev_hi;
        if (iter == prev_lo) {
          ++prev_lo;
        }
      }
    }

    return values_.erase(iter);
  }

public:
  iterator_type find(const V &value) {
    return find_in_bucket(bucket(value), value);
  }

  const_iterator_type find(const V &value) const {
    return const_iterator_type(find_in_bucket(bucket(value), value));
  }

  [[nodiscard]] bool contains(const K &key) const noexcept {
    return find_key_in_bucket(bucket_from_key(key), key) != end();
  }

  conditional_t<AllowDup, iterator_type, pair<iterator_type, bool>>
  insert(const V &value) {
    auto [to_rehash, next_buckets_size] = need_rehash();
    if (to_rehash) {
      rehash(next_buckets_size);
    }

    // find insertion point
    auto bucket_index = bucket(value);
    auto &lo = buckets_[bucket_index << 1];
    auto &hi = buckets_[(bucket_index << 1) + 1];

    if (lo == hi) { // empty bucket
      values_.push_front(value);
      lo = begin();
      hi = next(lo);
      if constexpr (AllowDup) {
        return lo;
      } else {
        return {lo, true};
      }
    } else {
      auto it = ranges::lower_bound(lo, hi, value, less<K>{}, KeyProj{});
      if constexpr (!AllowDup) {
        if (it != hi && KeyProj{}(*it) == KeyProj{}(value)) {
          return {it, false};
        }
      }
      auto it_old = it;
      auto &prev_hi = (it_old != begin()) ? buckets_[(bucket(*prev(it_old)) << 1) + 1] : hi;
      it = values_.insert(it, value);
      if (lo == it_old) {
        lo = it;
      }
      if (prev_hi != hi && prev_hi == it_old) {
        prev_hi = it;
      }
      if constexpr (AllowDup) {
        return it;
      } else {
        return {it, true};
      }
    }
  }

  iterator_type erase(iterator_type iter) {
    if (iter == end()) {
      throw invalid_argument("attempt to erase end()");
    }
    return erase_from_bucket(bucket(*iter), iter);
  }

  size_t erase(const K &key) {
    auto bucket_index = bucket_from_key(key);
    if constexpr (AllowDup) {
      return erase_key_from_bucket(bucket_index, key);
    } else {
      // TODO: for HashMultiSet and HashMultiMap, optimize erase elements with
      // the same keys by implementing range erase...
      size_t erased = 0;
      while (erase_key_from_bucket(bucket_index, key)) {
        ++erased;
      }
      return erased;
    }
  }
};

} // namespace detail

template <Containable K, typename Hasher = Hash<K>>
using HashSet = detail::HashTable<K, K, Hasher, false>;

template <Containable K, typename Hasher = Hash<K>>
using HashMultiSet = detail::HashTable<K, K, Hasher, true>;

template <Containable K, Containable V, typename Hasher = Hash<K>>
using HashMap = detail::HashTable<K, pair<const K, V>, Hasher, false>;

template <Containable K, Containable V, typename Hasher = Hash<K>>
using HashMultiMap = detail::HashTable<K, pair<const K, V>, Hasher, true>;

} // namespace frozenca::hard

#endif //__CLRS4_HASH_TABLE_H__

Benchmark and test code:

#include <algorithm>
#include <chrono>
#include <functional>
#include <hashtable.h>
#include <iostream>
#include <list>
#include <numeric>
#include <random>
#include <ranges>
#include <test.h>
#include <unordered_set>
#include <util.h>
#include <vector>


namespace fc = frozenca;
using namespace std;

template <typename HashTableType> void hash_table_test(bool warmup = false) {
  constexpr int max_n = 100'000;
  constexpr int max_trials = 500;

  mt19937 gen(random_device{}());
  vector<float> durations_insert;
  vector<float> durations_find;
  vector<float> durations_erase;
  vector<int> v(max_n);
  iota(v.begin(), v.end(), 0);

  for (int t = 0; t < max_trials; ++t) {
    HashTableType h;

    float duration = 0.0f;
    ranges::shuffle(v, gen);
    for (auto num : v) {
      auto start = chrono::steady_clock::now();
      h.insert(num);
      auto end = chrono::steady_clock::now();
      duration +=
          chrono::duration_cast<chrono::duration<float, micro>>(end - start)
              .count();
    }
    durations_insert.push_back(duration);

    duration = 0.0f;
    ranges::shuffle(v, gen);
    for (auto num : v) {
      auto start = chrono::steady_clock::now();
      if (!h.contains(num)) {
        cout << "Verification fail!\n";
      }
      auto end = chrono::steady_clock::now();
      duration +=
          chrono::duration_cast<chrono::duration<float, micro>>(end - start)
              .count();
    }
    durations_find.push_back(duration);

    duration = 0.0f;
    ranges::shuffle(v, gen);
    for (auto num : v) {
      auto start = chrono::steady_clock::now();
      if (!h.erase(num)) {
        cout << "Verification fail!\n";
      }
      auto end = chrono::steady_clock::now();
      duration +=
          chrono::duration_cast<chrono::duration<float, micro>>(end - start)
              .count();
    }
    durations_erase.push_back(duration);
  }
  if (!warmup) {
    {
      auto stat = fc::get_statistics(durations_insert);
      fc::log("Time to insert {:6} elements:\n"
              "Average : {:10.4f} us,\n"
              "Stdev   : {:10.4f} us,\n"
              "95%     : {:10.4f} us,\n"
              "99%     : {:10.4f} us,\n"
              "99.9%   : {:10.4f} us,\n",
              fc::log_level::all, max_n, stat.average, stat.stdev,
              stat.percentile_95, stat.percentile_99, stat.percentile_999);
    }
    {
      auto stat = fc::get_statistics(durations_find);
      fc::log("Time to find {:6} elements:\n"
              "Average : {:10.4f} us,\n"
              "Stdev   : {:10.4f} us,\n"
              "95%     : {:10.4f} us,\n"
              "99%     : {:10.4f} us,\n"
              "99.9%   : {:10.4f} us,\n",
              fc::log_level::all, max_n, stat.average, stat.stdev,
              stat.percentile_95, stat.percentile_99, stat.percentile_999);
    }
    {
      auto stat = fc::get_statistics(durations_erase);
      fc::log("Time to erase {:6} elements:\n"
              "Average : {:10.4f} us,\n"
              "Stdev   : {:10.4f} us,\n"
              "95%     : {:10.4f} us,\n"
              "99%     : {:10.4f} us,\n"
              "99.9%   : {:10.4f} us,\n",
              fc::log_level::all, max_n, stat.average, stat.stdev,
              stat.percentile_95, stat.percentile_99, stat.percentile_999);
    }
  }
}

int main() {
  cout << "Hash table demo\n";
  
  hash_table_test<unordered_set<int>>(true); // warm up for benchmarking

  cout << "Warming up complete...\n";
  cout << "frozenca::hard::HashSet<int, std::hash<int>> test\n";
  hash_table_test<fc::hard::HashSet<int, hash<int>>>();
  cout << "frozenca::hard::HashSet<int, frozenca::hard::Hash<int>> test\n";
  hash_table_test<fc::hard::HashSet<int>>();
  cout << "std::unordered_set<int, std::hash<int>> test\n";
  hash_table_test<unordered_set<int>>();
  cout << "std::unordered_set<int, frozenca::hard::Hash<int>> test\n";
  hash_table_test<unordered_set<int, fc::hard::Hash<int>>>();
}

Benchmark result: (vs MSVC 19.30, maximum optimization)

Hash table demo
Warming up complete...
frozenca::hard::HashSet<int, std::hash<int>> test
Time to insert 100000 elements:
Average : 11129.9814 us,
Stdev   :   745.3386 us,
95%     : 12301.9766 us,
99%     : 14613.7832 us,
99.9%   : 18612.5625 us,

Time to find 100000 elements:
Average :  7542.9609 us,
Stdev   :   990.0515 us,
95%     :  9194.5889 us,
99%     : 11024.5322 us,
99.9%   : 15658.9160 us,

Time to erase 100000 elements:
Average : 11663.7646 us,
Stdev   :  1049.9095 us,
95%     : 13522.2344 us,
99%     : 16001.2617 us,
99.9%   : 20226.8809 us,

frozenca::hard::HashSet<int, frozenca::hard::Hash<int>> test
Time to insert 100000 elements:
Average :  9270.6504 us,
Stdev   :   688.8071 us,
95%     :  9912.7852 us,
99%     : 13038.1484 us,
99.9%   : 18303.8477 us,

Time to find 100000 elements:
Average :  5941.1533 us,
Stdev   :  1220.2374 us,
95%     :  7597.7178 us,
99%     : 11102.8945 us,
99.9%   : 18782.1172 us,

Time to erase 100000 elements:
Average : 10355.5000 us,
Stdev   :  1355.5795 us,
95%     : 12458.6602 us,
99%     : 15833.0244 us,
99.9%   : 24981.8047 us,

std::unordered_set<int, std::hash<int>> test
Time to insert 100000 elements:
Average : 10443.4482 us,
Stdev   :  1285.1492 us,
95%     : 13116.2832 us,
99%     : 16005.8037 us,
99.9%   : 21033.7227 us,

Time to find 100000 elements:
Average :  7984.1167 us,
Stdev   :  2493.9968 us,
95%     : 13577.6309 us,
99%     : 16972.2930 us,
99.9%   : 20642.2012 us,

Time to erase 100000 elements:
Average : 10173.2090 us,
Stdev   :  2162.7844 us,
95%     : 14685.8486 us,
99%     : 19353.5996 us,
99.9%   : 24877.8906 us,

std::unordered_set<int, frozenca::hard::Hash<int>> test
Time to insert 100000 elements:
Average :  9688.3926 us,
Stdev   :  1292.5687 us,
95%     : 12687.8008 us,
99%     : 15429.7432 us,
99.9%   : 16860.0723 us,

Time to find 100000 elements:
Average :  7054.4985 us,
Stdev   :  2604.7942 us,
95%     : 12619.9922 us,
99%     : 19328.2285 us,
99.9%   : 20225.8516 us,

Time to erase 100000 elements:
Average :  9490.4697 us,
Stdev   :  2436.9521 us,
95%     : 14996.3457 us,
99%     : 20023.6582 us,
99.9%   : 22787.5410 us,

Observations:

1. For int, my hash function is considerably better than std::hash<int>.

2. Comparing with std::unordered_set<int>, my hash table has roughly similar level of performance in inserting elements. Lookup was much faster, but erasing was slower.

Few TODOs:

1. Optimize erase(key) operation for HashMultiSet and HashMultiMap

2. Implement Hash function for other types (like std::basic_string, std::basic_string_view, etc)

Answer 1

My hash function seems to work surprisingly well!

[...]

My hash function and my hash table benchmark result for std::string:

(Generated 50000 random std::string with length 1~500, with char having values 32~126, and inserted them in random order, retrieved in random order, erased in random order. Repeated this 500 times)

It is no wonder it is working surprisingly well, as a completely random input is the best case scenario for a hash function. Almost any function will be fine then, including one that just returns the first std::size_t from the input, as that is then also guaranteed to be completely random.

The quality of a hash function is better measured by checking how well it does on almost identical inputs. Does it produce a very different output if you just change one bit in the input? What if I swap two parts of the input? What if you add 1 here and subtract 1 there? A good generic hash function has to cover these (and more) cases.

Finally, another nice property for hash functions to have is to be resistant against attacks. Even if you don't need cryptographic security, consider that if I can generate input such that all elements would get mapped to the same hash bucket, suddenly the application thinking it will get \$O(1)\$ performance out of its hash table will get \$O(N)\$ performance. Some hash non-cryptographic hash functions can therefore still be keyed, such that they will hash differently every time the application is started, and don't allow an attacker to guess what input would cause the undesired behavior.

Answer 2

I refactored my hash table, and extended hash function to support span-like types (like std::string)

Changes:

1. Hash buckets are now pair of ListNode* describing an inclusive range, instead of previous C++ STL like half-open range of iterators. This greatly reduced Hasher{}() function invocations (which must copy the key every time to inspect byte representation of the key). Using pointers instead of iterators has another huge advantage, because I can denote empty bucket as just a pair of nullptr.

2. Implemented range erase

3. Fixed hash function to deal with equivalence of negative zero and positive zero of floating point types

4. Simplified hash function family

5. Added hash function support for span-like types.

TODO: Support HashMap and HashMultiMap

Hash function:

#ifndef __CLRS4_HASH_FUNCTION_H__
#define __CLRS4_HASH_FUNCTION_H__

#include <bit>
#include <cstring>
#include <common.h>
#include <span>

namespace frozenca::hard {

using namespace std;
namespace detail {

inline constexpr size_t hash_a_base = 123UL;

template <size_t a> struct HashFunc {
  constexpr size_t operator()(size_t k) const noexcept {
    return 2 * k * k + a * k;
  }
};

template <unsigned_integral T, size_t a> struct HashBase {
  constexpr size_t operator()(T k) const noexcept {
    return HashFunc<a + sizeof(T) * 16>{}(static_cast<size_t>(k));
  }
};

template <Scalar T, size_t a> struct HashImpl {
  constexpr size_t operator()(const T &key) const noexcept {
    if constexpr (sizeof(T) == sizeof(uint64_t)) {
      return HashBase<uint64_t, a>{}(bit_cast<uint64_t>(key));
    } else if constexpr (sizeof(T) == sizeof(uint8_t)) {
      return HashBase<uint8_t, a>{}(bit_cast<uint8_t>(key));
    } else if constexpr (sizeof(T) == sizeof(uint16_t)) {
      return HashBase<uint16_t, a>{}(bit_cast<uint16_t>(key));
    } else if constexpr (sizeof(T) == sizeof(uint32_t)) {
      return HashBase<uint32_t, a>{}(bit_cast<uint32_t>(key));
    } else {
      []<bool flag = false>() {
        static_assert(flag, "Not supported sizeof(T)");
      }
      ();
    }
  }
};

template <SpanType T>
using SpanBaseType = remove_pointer_t<decltype(data<T>(declval<T>()))>;
template <size_t a> struct HashSpan {
  size_t operator()(span<const size_t> arr) const noexcept {
    size_t val = arr.size();
    for (auto num : arr) {
      val = detail::HashBase<size_t, a>{}(num + val);
    }
    return val;
  }
};

} // namespace detail

template <typename T, size_t a = detail::hash_a_base> struct Hash {
  constexpr size_t operator()(const T &key) const noexcept requires(Scalar<T>) {
    // negative zero -> positive zero for floating points
    if constexpr (is_same_v<T, float>) {
      return detail::HashImpl<T, a>{}(key == 0.0f ? 0.0f : key);
    } else if constexpr (is_same_v<T, double>) {
      return detail::HashImpl<T, a>{}(key == 0.0 ? 0.0 : key);
    } else if constexpr (is_same_v<T, long double>) {
      return detail::HashImpl<T, a>{}(key == 0.0l ? 0.0l : key);
    } else {
      return detail::HashImpl<T, a>{}(key);
    }
  }

  constexpr size_t operator()(const T &key) const noexcept requires(SpanType<T>) {
    using base_type = detail::SpanBaseType<T>;

    auto num_bytes = key.size() * sizeof(base_type);

    if (num_bytes == 0) {
      return 0UL;
    } else {
      auto num_words = num_bytes / sizeof(size_t);
      size_t val = 0;
      if (num_words) {
        val = detail::HashSpan<a>{}(span{reinterpret_cast<const size_t *>(key.data()), num_words});
      }
      auto last_bytes = num_bytes % sizeof(size_t);
      if (last_bytes) {
        size_t last_word = 0;
        memcpy(&last_word, key.data() + num_words, last_bytes);
        return detail::HashBase<size_t, a>{}(last_word + val);
      } else {
        return val;
      }
    }
  }
};

} // namespace frozenca::hard

#endif //__CLRS4_HASH_FUNCTION_H__

Hash Table:

#ifndef __CLRS4_HASH_TABLE_H__
#define __CLRS4_HASH_TABLE_H__

#include <bit>
#include <common.h>
#include <hashfunction.h>
#include <iomanip>
#include <iostream>
#include <linkedlist.h>
#include <vector>

namespace frozenca::hard {

using namespace std;

namespace detail {

template <Containable K, typename V, typename Hasher, bool AllowDup>
requires Hashable<Hasher, K>
class HashTable {
  // invariant: V is either K or pair<const K, Value> for some Value type.
  static constexpr bool is_set_ = is_same_v<K, V>;

  using Node = ListNode<V>;

  LinkedList<V> values_;

  // invariant: K cannot be mutated
  // so if V is K, ListIter is const iterator.
  // if V is pair<const K, value>, ListIter is non-const iterator (but only
  // value can be mutated)
  using ListIter = ListIterator<V, is_set_>;

  // invariant: buckets_.size() == 0 or must be a power of 2
  // each "bucket" is a pair of two ListNode* [begin, before_end]
  // this is inclusive range to minimize invocation of Hasher{}().
  // invariant: for empty bucket, begin == before_end == nullptr
  // invariant: for nonempty bucket, begin <= before_end,
  //  and all node pointers between points to elements
  // with the same hash value, with keys in sorted order.
  using Buckets = vector<Node *>;
  Buckets buckets_;

  // invariant: buckets.size() == 0 or bucket_mask_ == buckets_.size() - 1
  size_t bucket_mask_ = 0;

  static constexpr size_t growth_factor_early_ = 4UL;
  static constexpr size_t growth_factor_ = 2UL;

  // ideally, this should be equal to half of the initial nonempty capacity of
  // std::vector...
  static constexpr size_t initial_nonempty_bucket_count_ = 8UL;
  static constexpr size_t bucket_count_threshold_ = 128UL;

  static constexpr float max_load_factor_ = 1.0f;

  // note that each invocation of Hasher{}(key) copies key every time!
  size_t bucket(const K &key) const noexcept {
    return Hasher{}(key)&bucket_mask_;
  }

  size_t bucket(const V &value) const noexcept requires(!is_set_) {
    return bucket(value.first);
  }

public:
  using key_type = K;
  using value_type = V;
  using reference_type = V &;
  using const_reference_type = const V &;
  using iterator_type = ListIter;
  using const_iterator_type = ListIterator<V, true>;
  // hash tables have no reverse iterators!

  HashTable() = default;
  ~HashTable() = default;

public:
  HashTable(const HashTable &other) : values_{other.values_} {
    buckets_.clear();
    rehash(other.bucket_count());
  }
  HashTable &operator=(const HashTable &other) {
    values_ = other.values_;
    buckets_.clear();
    rehash(other.bucket_count());
    return *this;
  }
  HashTable(HashTable &&other) noexcept = default;
  HashTable &operator=(HashTable &&other) noexcept = default;

  [[nodiscard]] iterator_type begin() noexcept {
    return iterator_type(values_.begin());
  }

  [[nodiscard]] const_iterator_type begin() const noexcept {
    return const_iterator_type(values_.begin());
  }

  [[nodiscard]] const_iterator_type cbegin() const noexcept {
    return const_iterator_type(values_.cbegin());
  }

  [[nodiscard]] iterator_type end() noexcept {
    return iterator_type(values_.end());
  }

  [[nodiscard]] const_iterator_type end() const noexcept {
    return const_iterator_type(values_.end());
  }

  [[nodiscard]] const_iterator_type cend() const noexcept {
    return const_iterator_type(values_.end());
  }

  [[nodiscard]] bool empty() const noexcept { return values_.empty(); }

  [[nodiscard]] ptrdiff_t size() const noexcept { return values_.size(); }

  void clear() noexcept {
    values_.clear();
    buckets_.clear();
    bucket_mask_ = 0;
  }

  size_t bucket_count() const noexcept { return (buckets_.size() >> 1); }

  float load_factor() const noexcept {
    if (empty()) {
      return 0.0f;
    }
    return static_cast<float>(size()) / static_cast<float>(buckets_.size());
  }

  float max_load_factor() const noexcept { return max_load_factor_; }

private:
  [[nodiscard]] pair<bool, size_t> need_rehash() const noexcept {
    if (buckets_.empty()) {
      return {true, initial_nonempty_bucket_count_};
    } else {
      float next_load_factor =
          static_cast<float>(size() + 1) / static_cast<float>(bucket_count());
      if (next_load_factor >= max_load_factor_) {
        if (bucket_count() < bucket_count_threshold_) {
          return {true, bucket_count() * growth_factor_early_};
        } else {
          return {true, bucket_count() * growth_factor_};
        }
      } else {
        return {false, 0UL};
      }
    }
  }

  // find insertion point in inclusive range [lo, hi]
  // and whether there is already the same key
  pair<const_iterator_type, bool> find_insertion_point(Node *lo, Node *hi,
                                          const K &key) const noexcept {
    assert(lo && hi && hi != end().node_);
    auto curr = lo; // this is Node*, not iterator_type
    while (true) {
      if (curr->key_ >= key) {
        return {const_iterator_type(curr), curr->key_ == key};
      } else if (curr == hi) {
        return {const_iterator_type(hi->next_), false};
      }
      curr = curr->next_;
    }
  }

  // from first, find the first iterator which has the first different key
  // and that bucket index (to cache it)
  pair<iterator_type, size_t>
  find_next_key(iterator_type first) const noexcept {
    assert(first != end());
    auto iter = first;
    ++iter;
    while (iter != end()) {
      if (*iter != *first) {
        return {iter, bucket(*iter)};
      }
      ++iter;
    }
    return {end(), static_cast<size_t>(-1)};
  }

  void rehash(size_t next_bucket_size) {
    assert(has_single_bit(next_bucket_size));
    buckets_.assign(next_bucket_size << 1, nullptr);

    bucket_mask_ = next_bucket_size - 1;

    auto curr_it = begin();

    size_t cached_bucket_index = 0;
    bool cached = false;

    while (curr_it != end()) {
      auto bucket_index = cached ? cached_bucket_index : bucket(*curr_it);
      auto [next_it, next_bucket_index] = find_next_key(curr_it);
      cached = true;
      cached_bucket_index = next_bucket_index;

      auto &lo = buckets_[(bucket_index << 1)];
      auto &hi = buckets_[(bucket_index << 1) + 1];

      if (!lo) { // empty bucket
        assert(!hi);
        lo = curr_it.node_;
        hi = next_it.node_->prev_;
      } else { // find insertion point
        auto [where, unuse] = find_insertion_point(lo, hi, *curr_it);
        bool to_prepend = (where.node_ == lo);
        bool to_append = (where.node_ == hi->next_);
        assert(where != next_it);
        if (where == curr_it) {
          assert(!to_prepend && to_append);
          // don't splice, just adjust hi
          hi = where.node_;
        } else {
          values_.splice(where, curr_it, next_it);
          if (to_prepend) {
            lo = curr_it.node_;
          }
          if (to_append) {
            hi = where.node_->prev_;
          }
        }
        
      }
      curr_it = next_it;
    }
  }

  iterator_type find_in_bucket(size_t bucket_index,
                               const K &key) const noexcept {
    auto lo = buckets_[bucket_index << 1];
    auto hi = buckets_[(bucket_index << 1) + 1];
    if (!lo) { // empty bucket
      return end();
    }
    auto curr = lo;
    while (true) {
      if (curr->key_ == key) {
        return iterator_type(curr);
      } else if (curr->key_ > key || curr == hi) { // not found
        return end();
      }
      curr = curr->next_;
    }
  }

  size_t erase_from_bucket(size_t bucket_index, const K &key) {
    auto &lo = buckets_[bucket_index << 1];
    auto &hi = buckets_[(bucket_index << 1) + 1];
    if (!lo) { // empty bucket
      return 0;
    }
    auto curr = lo;
    while (true) {
      if (curr->key_ == key) { // found starting point
        break;
      } else if (curr->key_ > key || curr == hi) { // not found
        return 0;
      }
      curr = curr->next_;
    }
    if (curr == hi) {
      auto first = iterator_type(curr);
      auto last = iterator_type(hi->next_);
      erase_from_bucket(bucket_index, first, last);
      return 1;
    }

    size_t count = 1;

    auto last = curr->next_;
    while (last != hi->next_ && last->key_ == key) {
      last = last->next_;
      ++count;
    }
    erase_from_bucket(bucket_index, curr, last);
    return count;
  }

  iterator_type erase_from_bucket(size_t bucket_index, iterator_type iter) {
    return erase_from_bucket(bucket_index, iter, next(iter));
  }

  iterator_type erase_from_bucket(size_t bucket_index, iterator_type first,
                                  iterator_type last) {
    auto &lo = buckets_[bucket_index << 1];
    auto &hi = buckets_[(bucket_index << 1) + 1];
    assert(lo && hi);
    bool adjust_lo = (lo == first.node_);
    bool adjust_hi = (hi == last.node_->prev_);
    bool empty_bucket = adjust_lo && adjust_hi;
    if (empty_bucket) {
      lo = nullptr;
      hi = nullptr;
    } else if (adjust_lo) {
      lo = last.node_;
    } else if (adjust_hi) {
      hi = first.node_->prev_;
    }
    auto res = values_.erase(first, last);
    
    return res;
  }

public:
  iterator_type find(const V &value) {
    return find_in_bucket(bucket(value), value);
  }

  const_iterator_type find(const V &value) const {
    return const_iterator_type(find_in_bucket(bucket(value), value));
  }

  [[nodiscard]] bool contains(const K &key) const noexcept {
    return find_in_bucket(bucket(key), key) != end();
  }

  conditional_t<AllowDup, iterator_type, pair<iterator_type, bool>>
  insert(const V &value) {
    auto [to_rehash, next_buckets_size] = need_rehash();
    if (to_rehash) {
      rehash(next_buckets_size);
    }

    // find insertion point
    auto bucket_index = bucket(value);
    auto &lo = buckets_[bucket_index << 1];
    auto &hi = buckets_[(bucket_index << 1) + 1];

    if (!lo) { // empty bucket
      assert(!hi);
      values_.push_front(value);
      lo = begin().node_;
      hi = lo;
      if constexpr (AllowDup) {
        return lo;
      } else {
        return {lo, true};
      }
    } else {
      assert(lo && hi);

      auto [where, exist] = find_insertion_point(lo, hi, value);
      if constexpr (!AllowDup) {
        if (exist) {
          return {where, false};
        }
      }
      bool to_prepend = (where.node_ == lo);
      bool to_append = (where.node_ == hi->next_);

      auto it = values_.insert(where, value);

      if (to_prepend) {
        lo = it.node_;
      }
      if (to_append) {
        hi = where.node_->prev_;
      }

      if constexpr (AllowDup) {
        return it;
      } else {
        return {it, true};
      }
    }
  }

  iterator_type erase(iterator_type iter) {
    if (iter == end()) {
      throw invalid_argument("attempt to erase end()");
    }
    return erase_from_bucket(bucket(*iter), iter);
  }

  size_t erase(const K &key) { return erase_from_bucket(bucket(key), key); }
};

} // namespace detail

template <Containable K, typename Hasher = Hash<K>>
using HashSet = detail::HashTable<K, K, Hasher, false>;

template <Containable K, typename Hasher = Hash<K>>
using HashMultiSet = detail::HashTable<K, K, Hasher, true>;

template <Containable K, Containable V, typename Hasher = Hash<K>>
using HashMap = detail::HashTable<K, pair<const K, V>, Hasher, false>;

template <Containable K, Containable V, typename Hasher = Hash<K>>
using HashMultiMap = detail::HashTable<K, pair<const K, V>, Hasher, true>;

} // namespace frozenca::hard

#endif //__CLRS4_HASH_TABLE_H__

My hash function and my hash table benchmark result for std::string:

(Generated 50000 random std::string with length 1~500, with char having values 32~126, and inserted them in random order, retrieved in random order, erased in random order. Repeated this 500 times)

Hash table demo with std::string
Warming up complete...
frozenca::hard::HashSet<std::string, std::hash<std::string>> test
Time to insert  50000 elements:
Average : 58592.2188 us,
Stdev   :  2774.5254 us,
95%     : 63202.5195 us,
99%     : 70312.5078 us,
99.9%   : 79550.0156 us,

Time to find  50000 elements:
Average : 36074.1875 us,
Stdev   :  1510.9355 us,
95%     : 39154.5820 us,
99%     : 41042.9727 us,
99.9%   : 45367.8125 us,

Time to erase  50000 elements:
Average : 40471.9219 us,
Stdev   :  1902.4161 us,
95%     : 44516.4336 us,
99%     : 47488.4688 us,
99.9%   : 50228.4531 us,

frozenca::hard::HashSet<std::string, frozenca::hard::Hash<std::string>> test
Time to insert  50000 elements:
Average : 30567.8418 us,
Stdev   :  2257.5991 us,
95%     : 35208.6367 us,
99%     : 39465.7930 us,
99.9%   : 45245.4531 us,

Time to find  50000 elements:
Average : 24192.7207 us,
Stdev   :  1669.9611 us,
95%     : 27080.4473 us,
99%     : 32450.9141 us,
99.9%   : 35331.5742 us,

Time to erase  50000 elements:
Average : 28387.8301 us,
Stdev   :  2175.6450 us,
95%     : 32882.5078 us,
99%     : 36856.3984 us,
99.9%   : 44376.5977 us,

std::unordered_set<std::string, std::hash<std::string>> test
Time to insert  50000 elements:
Average : 55769.9688 us,
Stdev   :  2516.8420 us,
95%     : 59751.8398 us,
99%     : 64048.1680 us,
99.9%   : 77419.1094 us,

Time to find  50000 elements:
Average : 35935.7969 us,
Stdev   :  1540.6226 us,
95%     : 39028.7422 us,
99%     : 41202.4336 us,
99.9%   : 50968.5391 us,

Time to erase  50000 elements:
Average : 39205.8672 us,
Stdev   :  1748.9017 us,
95%     : 42696.1328 us,
99%     : 45552.7930 us,
99.9%   : 46976.0430 us,

std::unordered_set<std::string, frozenca::hard::Hash<std::string>> test
Time to insert  50000 elements:
Average : 27687.9648 us,
Stdev   :  1865.7733 us,
95%     : 30989.4961 us,
99%     : 35184.9844 us,
99.9%   : 46163.4570 us,

Time to find  50000 elements:
Average : 23816.4434 us,
Stdev   :  1131.9313 us,
95%     : 26007.1602 us,
99%     : 28692.7910 us,
99.9%   : 30869.2227 us,

Time to erase  50000 elements:
Average : 26908.7305 us,
Stdev   :  1578.6808 us,
95%     : 30157.9668 us,
99%     : 32330.1035 us,
99.9%   : 37666.9805 us,

My hash set has similar level of performance vs. std::unordered_set, but for long std::strings, my hash function was much faster than std::hash<std::string>