Fast and memory efficient c++ flat hash table/map/set
High-performance, memory-efficient C++ open addressing flat hash table emhash is a family of high-performance, header-only hash table implementations designed for maximum performance and memory efficiency. Through innovative collision resolution strategies and cache optimization techniques, emhash demonstrates exceptional performance across various benchmarks.
EMH_HIGH_LOAD macro (available in hash_table5/7/8) or max_load_factor() (emhash6/7)sizeof(key) % 8 != sizeof(value) % 8hash_map saves 1/3 memory compared to hash_mapshrink_to_fit() releases unused memory| Feature | Description |
|---|---|
insert_unique |
Direct insertion without lookup (performance boost) |
try_get |
Returns pointer to value, nullptr if key not found |
try_set |
Set value if key exists, do nothing if it doesn't (emhash5/8, emilib1/2/3) |
set_get |
Updates value and returns old value (emhash5/8, emilib1/2/3) |
_erase |
Delete operation returning void (faster) |
| LRU Mode | Enable LRU cache optimization with EMH_LRU_SET |
emhash is header-only — just copy one .hpp file to your project:
…#include "emhash/hash_table7.hpp" // Or emhash/hash_table[5-8].hpp…More examples: docs/examples/
If you're not sure which version to use, start with
emhash7— no tombstones means stable performance under mixed insert/erase workloads, with native high load factor support (0.9+).
Choose by your primary workload pattern, not key type:
…| Version | Best For | Key Strengths | Weaknesses |
|---|---|---|---|
| emhash5 | Small tables, memory-constrained | Small-size optimization (EMH_SMALL_SIZE), 3-way hybrid probing |
Slower than emhash6 at high load factor |
| emhash6 | Find/erase-heavy, integer keys | Bitmask-accelerated empty-slot search, fastest find/erase | Extra memory for bitmask array |
| emhash7 | General purpose, mixed workloads | Chain repair on erase (no tombstones), stable at 0.9+ LF | Erase slightly slower than emhash5/6 |
| emhash8 | Iteration-heavy, large KV types | Split-index + dense pairs, sequential iteration, fast copy/move | Extra memory for separate index array |
| emilib2/3 | Read-heavy at scale (GCC) | SIMD group probing (16 buckets/cycle), excellent iteration | Tombstone accumulation under mixed workloads; insert slower on Clang; emilib2ss may hang under extreme hash collision attack — use emilib2o or emilib2s |
| emilib4 | Experimental Swiss-table variant | Fast insert on Clang, dense iteration | Tombstone accumulation (no backward shift); no try_set/set_get/_erase; fixed LF 0.875 |
| Feature | emhash5 | emhash6 | emhash7 | emhash8 | emilib1/2/3 | emilib4 |
|---|---|---|---|---|---|---|
| High load factor (0.9+) | ✅ | ✅ | ✅ | ✅ | ✅ | ❌ |
try_set |
✅ | ❌ | ❌ | ✅ | ✅ | ❌ |
set_get |
✅ | ❌ | ❌ | ✅ | ✅ | ❌ |
| Custom allocator | ✅ | ✅ | ✅ | ✅ | ❌ | ❌ |
| SIMD acceleration | ❌ | ❌ | ❌ | ❌ | ✅ | ✅ |
| No tombstones | ✅ | ✅ | ✅ | ✅ | ❌ | ❌ |
| Dense pairs iteration | ❌ | ❌ | ❌ | ✅ | ✅ | ✅ |
See Performance Overview for detailed benchmark numbers.
The test suite is in tests/ and requires no third-party dependencies — only emhash/emilib headers.
cd tests
# Build all tests
cmake -B build && cmake --build build --config Release
# Run via custom targets
cmake --build build --target quick_test # Unit + memory tests (fast feedback)
cmake --build build --target stress_test # Stress tests
cmake --build build --target attack_test # Hash attack tests
cmake --build build --target all_tests # All tests| Category | Directory | Description |
|---|---|---|
| Unit | tests/unit/ |
CRUD, iterators, copy/move, edge cases, full API coverage |
| Memory | tests/memory/ |
ASan/MSan/UBSan, leak detection, lifecycle audit |
| Stress | tests/stress/ |
High load factor, bad hash, randomized stress |
| Attack | tests/attack/ |
Hash collision attacks (constant/small-range/linear) |
| Fuzz | tests/fuzz/ |
LibFuzzer + ASan fuzzing (requires clang) |
See tests/README.md for detailed instructions.
| Document | Description |
|---|---|
| Test Suite | Test organization, build instructions, coverage matrix |
| Test Analysis & Coverage Report | Per-file coverage data, test classification, CI integration |
| Performance Overview | Benchmark results, high load factor performance |
| API Reference | Constructors, methods, iterators |
| Design Principles | Collision resolution, memory layout, implementation comparison |
| Usage Notes | Thread safety, reference stability, iteration, large values |
| Performance Tips | Compile flags, pre-allocation, hash selection, anti-patterns |
| FAQ | Frequently asked questions |
| Migration Guide | Migrating from std::unordered_map |
| Performance Tracking | Version-by-version benchmark history, regression policy |
| Architecture Decisions (ADR) | Why we chose open addressing, header-only, emhash8 layout, etc. |
emhash has been validated by multiple well-known third-party benchmarks:
Historical performance charts are available in docs/images/:
int64_t*.png - Integer key benchmarksstring*.png - String key benchmarksint_string.png - Mixed key/value type benchmarksDownload all files in the bench/tsl_bench/ directory and open chartsAll.html in a browser to view interactive performance curves.
This project is open-sourced under the MIT License.
…Thanks to the following projects and authors for inspiration and comparison:
-DEMH_NO_BUILTIN_WYHASH to use your own wyhash.hNo open issues yet, or sync has not completed.