flat_hash_map and flat_hash_set Performance Characteristics vs std::unordered_map

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, 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 (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 (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 (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 (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 (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 (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

#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, 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 (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 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, 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) 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, 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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}