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

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, the FlatHashMapPolicy reports zero additional space usage for individual elements:

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 explicitly manages these allocations through dedicated hooks:

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:

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:

#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:

#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: Defines FlatHashMapPolicy with space_used() returning 0, indicating no per-element allocation tracking.
• 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: 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, 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.

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