A hash table mostly compatible with the C++11 std::unordered_map interface, but with much higher performance for many workloads.
This hash table uses open addressing with linear probing and backshift deletion. Open addressing and linear probing minimizes memory allocations and achieves high cache efficiency. Backshift deletion keeps performance high for delete heavy workloads by not clobbering the hash table with tombestones.
HashMap
is mostly compatible with the C++11 container interface. The
main differences are:
Key
and T
needs to be default constructible.erase
.Member functions:
HashMap(size_type bucket_count, key_type empty_key);
Construct a HashMap
with bucket_count
buckets and empty_key
as
the empty key.
The rest of the member functions are implemented as for
std::unordered_map
.
using namespace rigtorp;
// Hash for using std::string as lookup key
struct Hash {
size_t operator()(int v) { return v * 7; }
size_t operator()(const std::string &v) { return std::stoi(v) * 7; }
};
// Equal comparison for using std::string as lookup key
struct Equal {
bool operator()(int lhs, int rhs) { return lhs == rhs; }
bool operator()(int lhs, const std::string &rhs) {
return lhs == std::stoi(rhs);
}
};
// Create a HashMap with 16 buckets and 0 as the empty key
HashMap<int, int, Hash, Equal> hm(16, 0);
hm.emplace(1, 1);
hm[2] = 2;
// Iterate and print key-value pairs
for (const auto &e : hm) {
std::cout << e.first << " = " << e.second << "\n";
}
// Lookup using std::string
std::cout << hm.at("1") << "\n";
// Erase entry
hm.erase(1);
A benchmark src/HashMapBenchmark.cpp
is included with the sources. The
benchmark simulates a delete heavy workload where items are repeatedly inserted
and deleted.
I ran this benchmark on the following configuration:
isolcpus
for running the benchmarkWhen working set fits in L3 cache (HashMapBenchmark -c 100000 -i 100000000
):
Implementation | mean ns/iter | max ns/iter |
---|---|---|
HashMap | 24 | 1082 |
absl::flat_hash_map | 24 | 2074 |
google::dense_hash_map | 49 | 689846 |
std::unordered_map | 67 | 10299 |
When working set is larger than L3 cache (HashMapBenchmark -c 10000000 -i 1000000000
):
Implementation | mean ns/iter | max ns/iter |
---|---|---|
HashMap | 75 | 19026 |
absl::flat_hash_map | 101 | 19848 |
google::dense_hash_map | 111 | 226083255 |
std::unordered_map | 408 | 22422 |
HashMap has been cited by the following papers:
This project was created by Erik Rigtorp <[email protected]>.