emhash

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.

---

Table of Contents

• Core Features
• Quick Start
• Version Selection Guide
• Testing
• Documentation
• Third-Party Benchmarks
• License

---

Core Features

Extreme Performance

• High load factor support: Set load factor up to 0.999 via EMH_HIGH_LOAD macro (available in hash_table5/7/8) or max_load_factor() (emhash6/7)
• No tombstones: Performance does not degrade even with frequent insert/erase operations
• Smart collision resolution: Three-way hybrid strategy combining linear probing, quadratic probing, and bidirectional search
• Cache-friendly design: Single array inline storage minimizes memory footprint and maximizes cache hit rate

Memory Optimization

• Compact layout: Significant memory savings when sizeof(key) % 8 != sizeof(value) % 8
  • Example: hash_map<uint64_t, uint32_t> saves 1/3 memory compared to hash_map<uint64_t, uint64_t>
• Dynamic shrinking: shrink_to_fit() releases unused memory

Extended Features

Platform Support

• Operating Systems: Windows, Linux, macOS
• Processors: x86_64, ARM64 (Apple M1/M2, AMD, Intel)
• Compilers: GCC, Clang, MSVC (C++17/20)

---

Quick Start

1. Include Header

emhash is header-only — just copy one .hpp file to your project:

# Option A: Copy directly (simplest, no build system needed)
cp include/emhash/hash_table7.hpp /your/project/emhash/

# Option B: Clone and include
git clone https://github.com/ktprime/emhash.git
# Then add -I/path/to/emhash/include to your compiler flags

# Option C: CMake FetchContent (no install needed)
# Add to your CMakeLists.txt:
#   include(FetchContent)
#   FetchContent_Declare(emhash GIT_REPOSITORY https://github.com/ktprime/emhash.git GIT_TAG v1.1.0)
#   FetchContent_MakeAvailable(emhash)
#   target_link_libraries(your_target PRIVATE emhash::emhash)

# Option D: CMake find_package (after install)
# cmake -B build -DCMAKE_PREFIX_PATH=/path/to/emhash-install
# In CMakeLists.txt: find_package(emhash REQUIRED CONFIG)
#   target_link_libraries(your_target PRIVATE emhash::emhash)

#include "emhash/hash_table7.hpp"  // Or emhash/hash_table[5-8].hpp

2. Basic Usage

#include "emhash/hash_table7.hpp"
#include <iostream>

int main() {
    // Create and reserve space
    emhash7::HashMap<int, std::string> map;
    map.reserve(100);

    // Insert elements (multiple ways)
    map[1] = "one";
    map.emplace(2, "two");
    map.insert_unique(3, "three");  // Best performance, key must be unique

    // Find element
    auto it = map.find(2);
    if (it != map.end()) {
        std::cout << "Found: " << it->second << "\n";
    }

    // try_get: returns pointer, more concise
    if (auto* pval = map.try_get(3)) {
        std::cout << "Value: " << *pval << "\n";
    }

    // Iterate
    for (const auto& [key, value] : map) {
        std::cout << key << " => " << value << "\n";
    }

    return 0;
}

3. Advanced Usage

// Custom key type
struct Point {
    int x, y;
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

struct PointHash {
    size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

emhash7::HashMap<Point, std::string, PointHash> point_map;

// C++20 using Lambda
#if __cplusplus >= 202002L
auto hash = [](const Point& p) { return std::hash<int>()(p.x + p.y); };
auto eq = [](const Point& a, const Point& b) { return a.x == b.x && a.y == b.y; };
emhash7::HashMap<Point, int, decltype(hash), decltype(eq)> map(0, hash, eq);
#endif

More examples: docs/examples/

---

Version Selection Guide

30-Second Quick Guide

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:

What is your primary workload?
  ├─ Mixed (insert + find + erase) → emhash7 (no tombstones, stable at high LF)
  ├─ Find/erase-heavy →
  │     ├─ Integer keys → emhash6 (bitmask-accelerated empty-slot search)
  │     └─ String/large KV types → emhash8 (dense pairs, cache-friendly)
  ├─ Iteration-heavy → emhash8 (dense pairs array, sequential scan)
  └─ Small tables (< 1K elements) → emhash5 (small-size optimization)

Consider emilib2 (Swiss Table) if:
  - You need maximum find throughput at scale (1M+ elements) on GCC
  - Your workload is read-heavy with minimal erase (tombstone accumulation degrades mixed workloads)
  - Note: insert performance is significantly slower on Clang vs GCC

Detailed Comparison

Feature Matrix

See Performance Overview for detailed benchmark numbers.

---

Testing

The test suite is in tests/ and requires no third-party dependencies — only emhash/emilib headers.

Quick Start

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

Test Categories

See tests/README.md for detailed instructions.

---

Documentation

---

Third-Party Benchmarks

emhash has been validated by multiple well-known third-party benchmarks:

• Martin Ankerl's Hashmap Benchmark - Comprehensive performance testing
• Jackson Allan's C/C++ Hash Tables Benchmark - Multi-dimensional comparison

Benchmark Code

• Comprehensive Benchmark
• High Load Test

Performance Charts

Historical performance charts are available in docs/images/:

• int64_t*.png - Integer key benchmarks
• string*.png - String key benchmarks
• int_string.png - Mixed key/value type benchmarks

Interactive Performance Charts

Download all files in the bench/tsl_bench/ directory and open chartsAll.html in a browser to view interactive performance curves.

---

License

This project is open-sourced under the MIT License.

Copyright (c) 2019-2026 Huang Yuanbing & bailuzhou AT 163.com

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

---

Acknowledgments

Thanks to the following projects and authors for inspiration and comparison:

• martinus/robin-hood-hashing
• greg7mdp/parallel-hashmap
• Tessil/hopscotch-map
• ska::flat_hash_map
• wyhash — integrated directly into config.hpp (no external dependency required); pass -DEMH_NO_BUILTIN_WYHASH to use your own wyhash.h