HashMap.h

A hash table mostly compatible with the C++11 std::unordered_map interface, but with much higher performance for many workloads.

Implementation

This hash table uses open addressing with linear probing and backshift deletion. Open addressing and linear probing minimizes memory allocations and achives high cache effiency. Backshift deletion keeps performance high for delete heavy workloads by not clobbering the hash table with tombestones.

Usage

HashMap is mostly compatible with the C++11 container interface. The main differences are:

• A key value to represent the empty key is required.
• Key and T needs to be default constructible.
• Iterators are invalidated on all modifying operations.
• It's invalid to perform any operations with the empty key.
• Destructors are not called on 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.

Example

// Create a HashMap with 16 buckets and 0 as the empty key
HashMap<int, int> 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";
}

// Erase entry
hm.erase(1);

Benchmark

The benchmark first inserts 1M random entries in the table and then removes the last inserted item and inserts a new random entry 1 billion times. This is benchmark is designed to simulate a delete heavy workload.

Implementation	ns/iter
HashMap	77
google::dense_hash_map	122
std::unordered_map	220

About

This project was created by Erik Rigtorp <erik@rigtorp.se>.