C++ Hash Container Libraries: Robin-Hood Hashing vs Parallel Hashmap vs Abseil Swiss Tables

Introduction

Hash tables are one of the most fundamental data structures in programming — they power everything from database indexes to web application caches. While the C++ standard library provides std::unordered_map, its performance characteristics leave much to be desired. The standard mandates separate chaining for collision resolution, which leads to poor cache locality and memory fragmentation. Fortunately, the C++ ecosystem has produced several high-performance hash table implementations that dramatically outperform the standard version.

In this article, we compare three leading open-source C++ hash container libraries: robin-hood-hashing, parallel-hashmap (PHMap), and Abseil Swiss Tables. Each takes a fundamentally different approach to solving the hash table performance problem, and each excels in different scenarios.

Why std::unordered_map Falls Short

Before diving into alternatives, it’s worth understanding why the standard library hash table underperforms. The C++11 standard effectively requires std::unordered_map to use bucket-based separate chaining — each bucket is a linked list of nodes. This design has several problems:

• Poor cache locality: Each node is separately heap-allocated, scattering data across memory
• Memory overhead: Every insertion requires at least one heap allocation (node + potential rehash)
• Pointer chasing: Lookups follow linked-list pointers, causing CPU pipeline stalls
• Reference stability requirement: The standard requires references to remain valid after insertion, preventing flat storage designs

Modern hash table designs abandon this approach in favor of open addressing — storing entries directly in the table array and probing for empty slots on collisions.

Comparison Table

Robin-Hood Hashing (robin-hood-hashing)

The robin-hood-hashing library implements the Robin Hood hashing algorithm in a clean, single-header C++ implementation. The core idea is elegantly simple: when inserting a key, if the new key is farther from its ideal position than the existing occupant, swap them — “robbing from the rich (close to home) to give to the poor (far from home).”

Installation

1
2

# Single header file — just copy it
wget https://raw.githubusercontent.com/martinus/robin-hood-hashing/master/src/include/robin_hood.h

Basic Usage

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include "robin_hood.h"
#include <string>
#include <iostream>

int main() {
    // Drop-in replacement for std::unordered_map
    robin_hood::unordered_map<std::string, int> map;
    
    map["apple"] = 100;
    map["banana"] = 200;
    map["cherry"] = 300;
    
    // Heterogeneous lookup with string_view (no allocation)
    std::string_view key = "banana";
    auto it = map.find(key);
    if (it != map.end()) {
        std::cout << it->second << std::endl; // 200
    }
    
    // Iteration preserves insertion-like order
    for (const auto& [k, v] : map) {
        std::cout << k << ": " << v << std::endl;
    }
    
    return 0;
}

The backward shift deletion algorithm ensures that when an entry is removed, subsequent entries are shifted backward to fill the gap, maintaining the probe sequence invariant. This keeps average probe lengths low and predictable.

Performance Characteristics

Robin Hood hashing achieves excellent performance through:

• Cache-friendly flat array: All entries stored contiguously
• Short probe sequences: Average probe length stays near 1 with 0.5-0.7 load factors
• Minimal memory overhead: Only 1 byte per entry for displacement metadata in optimized builds
• Fast deletions: Backward shift deletion is O(1) expected

When to Use

• When you need a simple, single-header replacement for std::unordered_map
• Projects targeting C++11 compatibility
• Memory-constrained environments where every byte counts
• When you want predictable, consistent performance without SIMD requirements

Parallel Hashmap (parallel-hashmap)

The parallel-hashmap library by Gregory Popovitch combines the best ideas from multiple hash table designs. It provides both phmap::flat_hash_map (based on Abseil Swiss Tables) and phmap::parallel_flat_hash_map for concurrent access.

Installation

1
2
3

# Header-only — just copy the parallel_hashmap directory
git clone https://github.com/greg7mdp/parallel-hashmap.git
# Include parallel_hashmap/phmap.h in your project

Basic Usage

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <parallel_hashmap/phmap.h>
#include <string>
#include <iostream>

int main() {
    // Standard flat hash map — Swiss Table based
    phmap::flat_hash_map<std::string, int> map;
    
    map["alpha"] = 1;
    map["beta"] = 2;
    map["gamma"] = 3;
    
    // Heterogeneous lookup
    auto it = map.find(std::string_view("beta"));
    if (it != map.end()) {
        std::cout << it->second << std::endl; // 2
    }
    
    // Parallel hash map — thread-safe insert/find
    phmap::parallel_flat_hash_map<std::string, int> parallel_map;
    
    // Safe from multiple threads simultaneously
    parallel_map.try_emplace("key", 42);
    
    // Lazy construction — only allocate sub-maps when accessed
    parallel_map.visit("key", [](const int& val) {
        std::cout << "Value: " << val << std::endl;
    });
    
    return 0;
}

Parallel Container Architecture

The parallel variants use a clever sharding approach. Instead of a single hash table with a mutex, the table is split into N sub-tables, each with its own mutex. This allows concurrent access to different buckets without contention:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// Internal architecture (simplified)
template<typename K, typename V, size_t N = 4>
class parallel_flat_hash_map {
    flat_hash_map<K, V> sub_maps_[N];
    mutable std::shared_mutex mutexes_[N];
    
    size_t sub_index(const K& k) const {
        return hash<K>{}(k) % N;
    }
    
    // Concurrent insert — locks only one sub-map
    bool try_emplace(const K& key, const V& value) {
        size_t idx = sub_index(key);
        std::unique_lock lock(mutexes_[idx]);
        return sub_maps_[idx].try_emplace(key, value).second;
    }
};

When to Use

• When you need concurrent hash map access from multiple threads
• Projects requiring both single-threaded and multi-threaded hash maps from a single library
• When you want Abseil Swiss Table performance with header-only convenience
• Applications with large hash maps where per-sub-map locking provides better throughput than a single lock

Abseil Swiss Tables (absl::flat_hash_map)

Google’s Abseil library includes absl::flat_hash_map, an implementation of the Swiss Table design pioneered by Google. This is the same hash table used internally by Google across thousands of production services.

Installation

1
2
3
4
5
6
7

# Clone and build with CMake
git clone https://github.com/abseil/abseil-cpp.git
cd abseil-cpp
mkdir build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Release -DABSL_BUILD_TESTING=OFF
make -j$(nproc)
sudo make install

CMake Integration

1
2
3
4
5
6
7

cmake_minimum_required(VERSION 3.16)
project(MyProject)

find_package(absl REQUIRED)

add_executable(my_app main.cpp)
target_link_libraries(my_app absl::flat_hash_map absl::strings)

Basic Usage

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <absl/container/flat_hash_map.h>
#include <absl/strings/string_view.h>
#include <iostream>

int main() {
    // Swiss Table — highly optimized open-addressing design
    absl::flat_hash_map<std::string, int> table;
    
    // Bulk insert with reserve for predictable performance
    table.reserve(1000);
    for (int i = 0; i < 1000; ++i) {
        table[std::to_string(i)] = i;
    }
    
    // Transparent heterogeneous lookup (C++20)
    absl::string_view needle = "42";
    auto it = table.find(needle);
    if (it != table.end()) {
        std::cout << "Found: " << it->second << std::endl;
    }
    
    // SIMD-accelerated probing uses SSE2/AVX2 internally
    // to check 16 metadata bytes in a single instruction
    
    return 0;
}

Swiss Tables use a metadata array separate from the data array. Each metadata byte encodes the hash signature (7 bits) plus a control bit. During lookups, SIMD instructions compare the target hash signature against 16 metadata entries simultaneously, finding potential matches in a single instruction. This is what makes Swiss Tables so fast on modern CPUs.

When to Use

• Production environments where reliability and Google-scale testing matter
• Projects already using other Abseil libraries (strings, time, synchronization)
• When you want the absolute best SIMD-optimized lookup performance
• Large codebases where a compiled library (rather than header-only) is acceptable

Performance Comparison

In benchmark testing on a modern x86-64 system, here’s how the three libraries compare for common operations:

Swiss Tables (both phmap and Abseil) consistently outperform Robin Hood hashing by 15-25% on lookups due to SIMD-accelerated probe operations. However, Robin Hood hashing uses slightly less memory and compiles faster because it avoids the metadata array.

Choosing the Right Library

The choice depends on your specific constraints:

• Go with robin-hood-hashing if you need maximum simplicity (single header), C++11 compatibility, or the lowest memory overhead
• Choose parallel-hashmap if you need concurrent access, want Swiss Table performance with header-only convenience, or want the most feature-complete API
• Pick Abseil Swiss Tables if you’re in a Google-adjacent ecosystem, need battle-tested production reliability, or want the absolute best SIMD-accelerated performance

All three libraries outperform std::unordered_map by 3-5x in typical usage patterns. The migration cost is minimal since all provide near-identical APIs to the standard library.

FAQ

Can I use these as drop-in replacements for std::unordered_map?

Yes, all three libraries provide APIs that closely mirror the standard. The insert, find, erase, operator[], and iterator interfaces work identically. The main difference is that open-addressing designs invalidate references on rehash — but the standard guarantees for iterators remain respected (existing iterators stay valid unless rehash occurs).

Which library has the fastest compile times?

robin-hood-hashing is the clear winner here. As a single ~3,000-line header, it adds negligible compilation overhead. parallel-hashmap is header-only but more template-heavy. Abseil requires linking a compiled library, which adds build configuration complexity but can speed up incremental rebuilds.

Do these libraries support custom allocators?

All three support custom allocators via template parameters. Abseil uses absl::flat_hash_map<K, V, Hash, Eq, Allocator>, phmap uses phmap::flat_hash_map<K, V, Hash, Eq, Allocator>, and robin-hood uses robin_hood::unordered_map<K, V, Hash, Eq, Allocator>. For memory-constrained embedded systems, you can pair these with arena or pool allocators.

What about std::unordered_map in C++20/23?

C++20 and C++23 did not mandate changes to the hash table requirements. The ABI and reference-stability constraints from C++11 remain in place, so std::unordered_map will continue to use separate chaining for the foreseeable future. Several proposals to add std::flat_map (open-addressing) have been made but have not yet been standardized.

How do I migrate existing code to use these libraries?

Start by defining a type alias:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// Before migration, define:
#if USE_ROBIN_HOOD
#include "robin_hood.h"
template<typename K, typename V> using FastMap = robin_hood::unordered_map<K, V>;
#elif USE_PHMAP
#include <parallel_hashmap/phmap.h>
template<typename K, typename V> using FastMap = phmap::flat_hash_map<K, V>;
#elif USE_ABSL
#include <absl/container/flat_hash_map.h>
template<typename K, typename V> using FastMap = absl::flat_hash_map<K, V>;
#endif

// Replace all std::unordered_map<K,V> with FastMap<K,V>

For more on high-performance data structures, see our comparison of general-purpose data structure libraries and our guide to concurrent data structures. For lock-free patterns, check our lock-free data structure comparison.

💰 想测试你的市场判断力？我用 Polymarket 做预测市场交易——这是全球最大的预测市场平台，从大选结果到技术监管时间线，什么都可以押注。和赌博不同，这是真正的信息市场：你懂的信息越多，胜率越高。我靠预测技术相关事件的走向已经赚了不少。用我的邀请链接注册：Polymarket.com