# flat_hash_map and flat_hash_set Performance Characteristics vs std::unordered_map

> Discover performance differences between absl::flat_hash_map and std::unordered_map. Learn about cache locality, iteration speed, and traversal costs.

- Repository: [Abseil/abseil-cpp](https://github.com/abseil/abseil-cpp)
- Tags: performance
- Published: 2026-07-14

---

**absl::flat_hash_map and absl::flat_hash_set use a contiguous Swiss-table layout that eliminates memory indirection, providing superior cache locality and faster iteration than std::unordered_map, though with O(capacity) traversal cost and invalidation of pointers on rehash.**

Abseil’s `flat_hash_map` and `flat_hash_set` are high-performance hash containers implemented in the abseil/abseil-cpp repository. According to the source code in [`absl/container/flat_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_map.h), these containers store value types directly inside their implementation array to avoid memory indirection, resulting in both memory and computation advantages over the standard library’s node-based unordered containers.

## Memory Layout and Cache Efficiency

### Node-Based vs Flat Storage

Standard `std::unordered_map` and `std::unordered_set` allocate individual nodes for each element, storing pointers to these nodes in buckets. This creates extra indirection and higher per-element overhead. In contrast, `absl::flat_hash_map` stores elements contiguously in a single array.

As noted in [`absl/container/flat_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_map.h) (lines 108-113): “A `flat_hash_map` stores its value types directly inside its implementation array … map values will not retain pointer stability.” This flat storage eliminates the node allocation overhead inherent in the standard containers.

### Cache Locality

The contiguous layout of the Swiss-table implementation provides high cache locality. Iteration walks a dense memory region, giving better CPU-cache utilization compared to `std::unordered_map`, where each node may be scattered throughout memory. This architectural difference is the primary driver of the real-world performance gains observed in dense workloads.

## Time Complexity and Iteration Performance

### Amortized O(1) Operations

Like their standard library counterparts, `flat_hash_map` and `flat_hash_set` provide **amortized O(1)** complexity for search, insertion, and deletion. However, the constant factors differ significantly due to the flat storage model.

As stated in [`absl/container/flat_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_map.h) (lines 19-25): “search, insertion, and deletion of map elements can be done as an O(1) operation. … the collection of Abseil ‘Swiss tables’ contain other optimizations that result in both memory and computation advantages.” Insertions are particularly cheap because they only require copying the value into the array, while rehashing moves whole blocks of memory rather than individual node allocations.

### O(capacity) Iteration Cost

Unlike `std::unordered_map`, which iterates in O(*size*) time stepping through active nodes, flat hash containers iterate over the entire backing array.

According to [`absl/container/flat_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_set.h) (lines 112-116): “Iteration takes O(capacity) time, not O(size).” This means iteration speed depends on the table’s capacity rather than its current size. When the container is dense (high load factor), this approach is extremely fast due to cache-friendly sequential access. However, for very sparse tables, iteration may be slower than `std::unordered_map` because the algorithm must scan empty and deleted slots.

## Operational Trade-offs

### Erasure and Sparsity Impact

Erasing elements in a flat hash container creates deleted slots that remain in the array. These tombstones affect performance because iteration must still scan them, and `erase()` can degrade the speed of `begin()` and iterator increment operations.

The source code in [`absl/container/flat_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_set.h) (lines 112-115) warns: “Erasure & sparsity can negatively affect performance: * erase() slows down begin() and ++iterator.” After many deletions, you should call `rehash(0)` or `clear()` to compact the table and restore iteration performance.

### Pointer Stability

Because elements are stored in a contiguous array that may be reallocated during growth, pointers and references to elements are not stable across insertions.

As documented in [`absl/container/flat_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_map.h) (lines 108-113), the container “stores its value types directly inside its implementation array … map values will not retain pointer stability.” If your application requires stable pointers, consider using `absl::node_hash_map` or `absl::node_hash_set` instead, which provide node-based storage with stable addresses.

### Capacity Management

`std::unordered_map` can release memory through `shrink_to_fit`, and erasure does not affect the bucket count. In `flat_hash_map`, capacity only shrinks on an explicit `rehash()` or `clear()` operation. The container does not automatically compact after erasure, which contributes to the sparsity issues mentioned above.

## Heterogeneous Lookup

`flat_hash_map` and `flat_hash_set` support heterogeneous lookup when the hash and equality types expose `is_transparent`. This allows looking up elements without constructing the key type, reducing unnecessary allocations.

As documented in [`absl/container/flat_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_set.h) (lines 65-68): “Supports heterogeneous lookup … provided that the set is provided a compatible heterogeneous hashing function and equality operator.” The standard library only added similar support in C++20, and even then requires specific template parameters.

## Practical Usage Examples

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

// flat_hash_map – fast insert/lookup, compact layout
absl::flat_hash_map<std::string, int> fast_map;
fast_map.reserve(1000);                // pre-allocate slots
fast_map["apple"] = 5;
fast_map.emplace("banana", 7);
auto it = fast_map.find("apple");      // O(1) lookup
if (it != fast_map.end()) {
    std::cout << it->second << '\n';
}

// flat_hash_set – iteration over a dense set is cache-friendly
absl::flat_hash_set<int> dense_set;
for (int i = 0; i < 10'000; ++i) dense_set.insert(i);

// Rehash after many deletions to regain iteration speed
dense_set.erase(0);
dense_set.erase(1);
dense_set.rehash(0);   // forces capacity to shrink to fit current size

```

The underlying implementation resides in [`absl/container/internal/raw_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/internal/raw_hash_set.h), which defines the Swiss-table algorithm used by both `flat_hash_map` and `flat_hash_set`.

## Summary

- **Memory Layout**: `flat_hash_map` stores elements contiguously in one array, while `std::unordered_map` uses scattered nodes with pointer indirection.
- **Cache Performance**: The flat layout provides superior cache locality, making dense workloads significantly faster.
- **Iteration Cost**: Iteration is O(capacity) rather than O(size), making it fast for dense tables but potentially slower for sparse ones.
- **Erasure Impact**: Deleted elements leave tombstones that slow iteration; use `rehash()` after bulk deletions.
- **Pointer Stability**: Elements move during rehashing; use `absl::node_hash_map` if you need stable addresses.
- **Recommendation**: According to [`absl/container/flat_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_map.h) (lines 27-29), “In most cases, your default choice for a hash map should be a map of type `flat_hash_map`."

## Frequently Asked Questions

### Is flat_hash_map faster than std::unordered_map?

Yes, for most dense workloads. The contiguous memory layout in [`absl/container/internal/raw_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/internal/raw_hash_set.h) eliminates node allocation overhead and improves cache locality, resulting in faster insertion and lookup. However, if the container becomes sparse due to many erasures, iteration may be slower than `std::unordered_map` because it scans O(capacity) slots.

### Why does iteration take O(capacity) time instead of O(size)?

`flat_hash_map` and `flat_hash_set` iterate by scanning the entire backing array to avoid branching and maintain cache-friendly sequential access. As noted in [`absl/container/flat_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_set.h), this design choice makes iteration extremely fast when the table is dense, though it requires examining empty and deleted slots. When the load factor is high, this approach outperforms the pointer-chasing required by node-based containers.

### When should I use node_hash_map instead of flat_hash_map?

Use `absl::node_hash_map` (defined in [`absl/container/node_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/node_hash_map.h)) when you require pointer stability. Because `flat_hash_map` stores elements in a contiguous array that gets reallocated during growth, pointers and references to elements become invalid after insertion. The node-based variant allocates individual nodes like `std::unordered_map`, preserving stable addresses at the cost of reduced cache locality and higher memory overhead.

### How do I handle performance degradation after many erasures?

After erasing many elements, call `rehash(0)` to compact the table and remove tombstones. As documented in [`absl/container/flat_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_set.h), erasure creates deleted slots that remain in the array, causing `begin()` and `++iterator` to slow down because they must scan past these markers. The `rehash(0)` operation forces the container to shrink its capacity to fit the current size, eliminating empty and deleted slots and restoring optimal iteration speed.