# Memory Allocation Behaviors of absl::flat_hash_map vs absl::node_hash_map: In-Place vs Node-Based Storage

> Explore the memory allocation behaviors of absl flat_hash_map vs absl node_hash_map. Discover in-place storage vs node-based allocation to optimize your C++ hash map performance.

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

---

**absl::flat_hash_map stores elements in-place within a contiguous buffer without per-element heap allocations, while absl::node_hash_map allocates each key-value pair individually on the heap as a separate node.**

Both `absl::flat_hash_map` and `absl::node_hash_map` implement the high-performance Swiss-table hashing algorithm in the abseil-cpp repository. While they share the same underlying probing and metadata strategies, their **memory allocation behaviors** differ fundamentally regarding how they store key-value pairs. These architectural distinctions directly impact cache locality, memory overhead, and pointer stability.

## Core Memory Allocation Strategies

The primary distinction between these containers lies in where they physically store the `std::pair<const K, V>` objects and how often they invoke the allocator.

### In-Place Storage in absl::flat_hash_map

`absl::flat_hash_map` stores elements **directly inside the hash table's contiguous array**. When you insert a key-value pair, the container constructs the object into a slot within the internal buffer. The allocator—defaulting to `std::allocator<std::pair<const K, V>>`—is only invoked when the table buffer itself requires growth or initial reservation.

This design eliminates per-element heap allocation overhead. As implemented in [`absl/container/flat_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_map.h), the `FlatHashMapPolicy` reports zero additional space usage for individual elements:

```cpp
static size_t space_used(const slot_type*) { return 0; }

```

This method, located at lines 71-73 in the header, confirms that once the table buffer is allocated, inserting elements does not trigger additional allocation calls.

### Per-Element Node Allocation in absl::node_hash_map

In contrast, `absl::node_hash_map` follows a node-based approach similar to `std::unordered_map`. Each insertion allocates a separate **node on the heap** to store the key-value pair. The container maintains an array of buckets that point to these individually allocated nodes.

The `NodeHashMapPolicy` in [`absl/container/node_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/node_hash_map.h) explicitly manages these allocations through dedicated hooks:

```cpp
static value_type* new_element(Allocator* alloc, Args&&... args) { … }
static void delete_element(Allocator* alloc, value_type* pair) { … }

```

These functions, found at lines 53-62, perform `allocate` plus `construct` operations for each node. Additionally, the policy reports the actual per-element memory consumption:

```cpp
static size_t element_space_used(const value_type*) { return sizeof(value_type); }

```

This method appears at lines 81-84 and accounts for the full size of each heap-allocated node.

## Pointer Stability and Memory Layout Implications

The allocation strategies create significant differences in **pointer stability** and cache performance characteristics.

### Reference Invalidation on Rehash

Because `absl::flat_hash_map` stores elements in-place within a contiguous array, any operation that triggers a rehash—such as insertion beyond the load factor, explicit `rehash()`, or sufficient inserts following `reserve()`—**moves elements physically** to new memory locations. Consequently, pointers and references to stored values become invalid during these operations.

Conversely, `absl::node_hash_map` allocates nodes individually on the heap. While the bucket array may be resized and rehashed, the **nodes themselves remain at fixed addresses**. Only the pointers within the bucket array change, leaving references to the actual key-value pairs stable across rehash operations.

### Memory Overhead and Cache Locality

`absl::flat_hash_map` minimizes memory overhead to just the control bits (metadata for empty/deleted flags) accompanying each slot. This compact representation provides excellent **cache locality** because elements reside in contiguous memory, maximizing CPU cache line utilization during iteration.

`absl::node_hash_map` incurs higher per-element overhead due to allocation headers, alignment padding, and the pointer indirection required to traverse from buckets to nodes. While this reduces cache efficiency compared to the flat variant, it enables storing non-movable types and maintains pointer stability required by certain API designs.

## Practical Code Examples

### absl::flat_hash_map: Single Buffer Allocation

When using `absl::flat_hash_map`, the `reserve()` call allocates one contiguous buffer, and subsequent inserts place data directly into slots without individual heap allocations:

```cpp
#include "absl/container/flat_hash_map.h"

int main() {
    absl::flat_hash_map<int, std::string> m;
    m.reserve(10);               // Single allocation for the table buffer
    m[1] = "one";                // No heap allocation; constructs in-place
    m[2] = "two";                // Writes into contiguous memory
    // All values live inside the internal array; pointers may invalidate on rehash
}

```

### absl::node_hash_map: Individual Node Allocation

With `absl::node_hash_map`, `reserve()` only allocates the bucket array. Each insertion triggers a separate heap allocation for the node:

```cpp
#include "absl/container/node_hash_map.h"

int main() {
    absl::node_hash_map<int, std::string> m;
    m.reserve(10);               // Allocates bucket array only
    m[1] = "one";                // Allocates node for pair <1, "one">
    m[2] = "two";                // Allocates separate node for <2, "two">
    // Pointers to values remain stable across future inserts
}

```

## Implementation Details in Source Files

The contrasting behaviors are defined in the policy classes within the Abseil container headers:

- **[`absl/container/flat_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_map.h)**: Defines `FlatHashMapPolicy` with `space_used()` returning 0, indicating no per-element allocation tracking.
- **[`absl/container/node_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/node_hash_map.h)**: Defines `NodeHashMapPolicy` with `element_space_used()` returning `sizeof(value_type)` and explicit `new_element()`/`delete_element()` hooks.
- **[`absl/container/internal/container_memory.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/internal/container_memory.h)**: Provides the allocator utilities used by the node policy to perform individual node construction and destruction.

Both containers utilize the shared Swiss-table implementation in [`absl/container/internal/raw_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/internal/raw_hash_map.h), but the policy classes determine whether the table contains actual objects (flat) or pointers to heap nodes (node).

## Summary

- **absl::flat_hash_map** stores elements in-place within a contiguous buffer, performing no per-element heap allocations and providing optimal cache locality at the cost of pointer stability during rehash.
- **absl::node_hash_map** allocates each key-value pair as a separate heap node, trading memory efficiency and cache performance for stable pointers across rehash operations.
- The `FlatHashMapPolicy::space_used()` method returns 0, while `NodeHashMapPolicy::element_space_used()` returns `sizeof(value_type)` to reflect their respective allocation strategies.
- Choose `flat_hash_map` for small-to-moderate sized values where cache performance matters, and `node_hash_map` when you require pointer stability or need to store non-movable types.

## Frequently Asked Questions

### Does absl::flat_hash_map allocate memory for each insertion?

No. `absl::flat_hash_map` only allocates memory when the internal table buffer needs to grow. Elements are stored directly within the contiguous slots of this buffer, so inserting a new key-value pair merely constructs the object in-place without invoking the allocator. Per-element allocation occurs solely during table resizing or explicit `reserve()` calls that exceed current capacity.

### Why does absl::node_hash_map provide pointer stability?

`absl::node_hash_map` allocates each element individually on the heap as a distinct node. While the bucket array may be reallocated and rehashed during growth, the **heap nodes themselves remain at fixed memory addresses**. This design maintains valid pointers and references to stored values even when the container's internal structure changes, making it compatible with code that relies on `std::unordered_map`-like semantics.

### Which container has better cache locality?

**absl::flat_hash_map** provides superior cache locality because it stores elements contiguously within a single buffer. This arrangement maximizes CPU cache line utilization during iteration and lookup operations. In contrast, `absl::node_hash_map` scatters elements across separate heap allocations, requiring pointer indirection that can degrade cache performance, particularly during large-scale traversals.

### Can I use custom allocators with these containers?

Yes. Both containers accept custom allocator types as template parameters, defaulting to `std::allocator<std::pair<const K, V>>`. However, the **allocation patterns differ significantly**: custom allocators used with `flat_hash_map` only receive allocation requests for the table buffer itself, while allocators paired with `node_hash_map` receive individual allocation and deallocation calls for every node insertion and erasure via the `new_element()` and `delete_element()` policy hooks.