# Abseil Swiss Table Containers: When to Use Flat, Node, and Parallel Hash Maps

> Learn when to use Abseil Swiss Table containers flat node or parallel hash maps for high performance. Optimize your C++ data structures with SIMD probing.

- Repository: [Abseil/abseil-cpp](https://github.com/abseil/abseil-cpp)
- Tags: deep-dive
- Published: 2026-07-16

---

**Abseil Swiss table containers are high-performance hash-based associative containers that use open addressing with SIMD-optimized probing to outperform `std::unordered_map` and `std::unordered_set`, with specific variants optimized for cache locality (flat), pointer stability (node), or concurrent access (parallel).**

The Abseil C++ library (`abseil/abseil-cpp`) provides a family of Swiss table containers that reimplement hash-based associative containers from first principles. Unlike the standard library's bucket-and-pointer approach, these containers store elements in contiguous memory blocks using a metadata array of control bytes to enable fast SIMD probing. This design delivers consistently lower latency and higher throughput for lookup-heavy workloads.

## How Swiss Table Containers Work

The Swiss table algorithm—implemented in [`absl/container/internal/hash_policy.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/internal/hash_policy.h)—combines **open addressing** with a cache-friendly layout that eliminates the pointer chasing found in traditional node-based hash tables.

### Control Bytes and SIMD Probing

Each bucket group contains a small, fixed number of slots (typically 16) preceded by a metadata byte for each slot. These **control bytes** store the hash fragment (H2) and occupancy state:

- An empty slot marks the end of the probe sequence
- A deleted slot triggers continued probing  
- Occupied slots contain the 7-bit hash fragment for quick comparison

The algorithm uses SIMD instructions to compare the target hash fragment against all control bytes in a bucket group simultaneously. According to the implementation in [`absl/container/internal/hash_policy.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/internal/hash_policy.h), this allows the container to check 16 slots with a single CPU instruction, dramatically reducing branch mispredictions compared to chaining-based approaches.

### Contiguous Memory Layout

Unlike `std::unordered_map`, which allocates nodes scattered across the heap, **flat** variants store keys and values directly in the bucket array. This improves CPU cache locality and reduces memory allocation overhead to a single allocation per rehash. The `flat_hash_map` and `flat_hash_set` headers ([`absl/container/flat_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_map.h) and [`absl/container/flat_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_set.h)) define these compact containers.

## Container Types Compared

Abseil provides three primary container categories, each with distinct memory and iterator stability guarantees.

### Flat Hash Containers (`flat_hash_map` and `flat_hash_set`)

**`absl::flat_hash_map`** and **`absl::flat_hash_set`** (defined in [`absl/container/flat_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_map.h) and [`absl/container/flat_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_set.h)) store elements directly in the bucket array. This layout maximizes memory density and cache locality.

- **Memory layout**: Key-value pairs stored contiguously in the bucket array
- **Iterator stability**: Iterators are invalidated on rehash; references to elements are not stable
- **Best for**: High-performance lookup/insertion where element pointers are not stored externally

### Node Hash Containers (`node_hash_map` and `node_hash_set`)

**`absl::node_hash_map`** and **`absl::node_hash_set`** (defined in [`absl/container/node_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/node_hash_map.h) and [`absl/container/node_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/node_hash_set.h)) allocate elements in separate nodes while retaining the Swiss table probing strategy for the bucket array.

- **Memory layout**: Elements stored in individually allocated nodes; the bucket array stores pointers
- **Iterator stability**: References and iterators remain valid across rehashes (similar to `std::unordered_map`)
- **Best for**: Scenarios requiring stable pointers to elements, such as when other data structures hold references to container elements

### Parallel Flat Hash Containers (`parallel_flat_hash_map` and `parallel_flat_hash_set`)

**`absl::parallel_flat_hash_map`** and **`absl::parallel_flat_hash_set`** (defined in [`absl/container/parallel_flat_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/parallel_flat_hash_map.h)) partition the hash table into lock-free shards to enable concurrent access without external synchronization.

- **Concurrency**: Supports concurrent insertions and lookups from multiple threads using per-shard mutexes or spinlocks
- **Memory layout**: Multiple sub-tables stored contiguously, each independently resizable
- **Best for**: Multi-threaded workloads with high contention, such as building large lookup tables in parallel

## When to Use Which Swiss Table Container

Choose the specific container based on your requirements for iterator stability, memory locality, and thread safety:

**`absl::flat_hash_map`** — Use when you need maximum lookup and insertion speed and can tolerate iterator invalidation on rehash. This is the default choice for most single-threaded applications where you do not store pointers to container elements.

**`absl::node_hash_map`** — Use when you require **stable references** to elements across rehashes. If your code stores pointers to elements in other data structures or relies on iterators not being invalidated during insertion, use the node-based variants.

**`absl::parallel_flat_hash_map`** — Use for **concurrent workloads** where multiple threads need to insert or lookup simultaneously. The internal sharding eliminates the need for external locking and provides better scalability than wrapping a flat hash map in a mutex.

**Transparent Hashing** — All Swiss table containers support heterogeneous lookups (e.g., finding a `std::string` key using a `std::string_view`), avoiding temporary object construction. This works automatically when your hash function supports the alternative type.

## Code Examples

### Basic Flat Hash Map with Heterogeneous Lookup

The `flat_hash_map` provides zero-copy lookups when using compatible string types:

```cpp
#include "absl/container/flat_hash_map.h"
#include <string>
#include <iostream>

int main() {
  absl::flat_hash_map<std::string, int> word_counts;
  word_counts["hello"] = 1;
  word_counts["world"] = 2;

  // Heterogeneous lookup with std::string_view (no temporary std::string)
  std::string_view key = "hello";
  if (auto it = word_counts.find(key); it != word_counts.end()) {
    std::cout << key << " appears " << it->second << " time(s).\n";
  }
}

```

### Node Hash Set with Stable Pointers

Use `node_hash_set` when you need pointers to elements to survive insertions:

```cpp
#include "absl/container/node_hash_set.h"
#include <iostream>

int main() {
  absl::node_hash_set<int> ids{1, 2, 3};

  // Store a pointer to an element inside the set
  const int* p = &*ids.find(2);
  std::cout << "Found value: " << *p << '\n';

  // Inserting more elements does not invalidate `p`
  ids.insert(4);
  ids.insert(5);
  std::cout << "Pointer still valid: " << *p << '\n';
}

```

### Parallel Flat Hash Map for Concurrent Insertion

The `parallel_flat_hash_map` allows lock-free concurrent operations across threads:

```cpp
#include "absl/container/parallel_flat_hash_map.h"
#include <thread>
#include <vector>

int main() {
  absl::parallel_flat_hash_map<int, int> map;
  const int N = 1'000'000;
  const int num_threads = 8;

  auto worker = [&](int start) {
    for (int i = start; i < N; i += num_threads) {
      map.emplace(i, i * i);
    }
  };

  std::vector<std::thread> threads;
  for (int t = 0; t < num_threads; ++t) {
    threads.emplace_back(worker, t);
  }
  for (auto& th : threads) th.join();

  // Verify a few entries
  std::cout << map[42] << '\n';   // prints 1764
}

```

## Implementation Details

The Swiss table implementation relies on several key header files in the `abseil/abseil-cpp` repository:

- **[`absl/container/flat_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_map.h)** and **[`absl/container/flat_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_set.h)**: Define the flat container interfaces with compact storage
- **[`absl/container/node_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/node_hash_map.h)** and **[`absl/container/node_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/node_hash_set.h)**: Provide the node-based variants with stable iterators
- **[`absl/container/parallel_flat_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/parallel_flat_hash_map.h)**: Implements the sharded concurrent containers
- **[`absl/container/internal/hash_policy.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/internal/hash_policy.h)**: Contains the core probing logic, control byte manipulation, and SIMD optimization strategies

The algorithm extracts a 7-bit hash fragment (H2) from the high bits of the hash value to store in the control byte, while using the low bits to determine the bucket index. This separation allows the SIMD probe to filter candidates before comparing full keys, reducing cache misses during unsuccessful lookups.

## Summary

- **Abseil Swiss table containers** replace `std::unordered_*` with cache-friendly open addressing and SIMD-optimized probing for superior performance.
- Use **`absl::flat_hash_map`** when you need maximum speed and memory density, and do not require stable iterators or element pointers.
- Use **`absl::node_hash_map`** when you must store pointers to elements or require iterators that survive rehashing.
- Use **`absl::parallel_flat_hash_map`** for multi-threaded applications requiring concurrent insertion and lookup without external locking.
- All variants support **transparent hashing** for efficient heterogeneous lookups (e.g., `std::string_view` into `std::string` keys).
- The implementation in [`absl/container/internal/hash_policy.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/internal/hash_policy.h) uses control bytes and SIMD instructions to achieve O(1) operations with very low constant factors.

## Frequently Asked Questions

### What is the difference between `flat_hash_map` and `node_hash_map`?

**`flat_hash_map`** stores elements directly in the bucket array, providing better cache locality and lower memory overhead, but invalidates iterators and references when the table rehashes. **`node_hash_map`** stores elements in separately allocated nodes, maintaining stable pointers and iterators across rehashes at the cost of an additional pointer indirection and higher memory usage. Choose `flat_hash_map` for raw performance and `node_hash_map` when you need to store external references to container elements.

### When should I use `parallel_flat_hash_map` instead of protecting a `flat_hash_map` with a mutex?

Use **`parallel_flat_hash_map`** when your application requires high-frequency concurrent access from multiple threads. The parallel variant uses internal sharding to reduce contention, whereas a mutex-protected `flat_hash_map` serializes all operations and becomes a bottleneck. The parallel container is specifically optimized for scenarios like aggregating data in parallel or building large lookup tables concurrently.

### Do Abseil Swiss table containers support custom hash functions?

Yes, all Swiss table containers accept a custom hasher and equality comparator as template parameters. Additionally, they support **transparent hashing**—if your hash functor defines `is_transparent` and provides overloads for heterogeneous types (such as `std::string_view` for a `std::string` key), the container avoids constructing temporary objects during lookup operations. This capability is defined in the container interfaces in [`absl/container/flat_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_map.h) and related headers.

### Are Abseil Swiss table containers drop-in replacements for `std::unordered_map`?

They are largely compatible but have important differences in **iterator invalidation** rules and **reference stability**. `flat_hash_map` invalidates iterators on rehash, while `std::unordered_map` does not (until C++20 for some operations). Additionally, Swiss table containers provide `find()` and `contains()` methods that work with heterogeneous keys, which `std::unordered_map` only gained in C++20. Review the iterator stability requirements of your existing code before migrating from standard library containers.