Implementing Hash Maps with Hash Tables: Internals, Memory Management, and Collision Strategies

A hash map (or dictionary) extends the fundamental indexing concept of a hash set to bind application-level values to unique keys. While conceptually straightforward, implementing a generic, production-grade hash map in low-level systems languages requires handling critical edge cases: generic key/value typing, avoiding hash recomputation, handling custom equality semantics, managing object lifecycles to prevent memory leaks, and optimizing write/read paths.

This guide breaks down the architectural blueprints for implementing robust hash maps backed by both separate chaining and open addressing hash tables.

---

1. Core Anatomy of a Generic Hash Map

In a hash set, the system only tracks whether a key exists. In a hash map, every entry associates an arbitrary key with an arbitrary payload value. Crucially, all operations remain key-centric: indexing, probing, bucket distribution, and lookups evaluate only the key. The value is merely an associated payload.

The Entry Pair Representation

To support generic data types in a language like C, keys and values are stored via generic void pointers (void*). To eliminate the CPU overhead of repeatedly hashing keys during collisions, resizing, and comparisons, the 32-bit hash value is cached directly alongside the entry.

typedef struct Entry {
    uint32_t hash_key;  // Cached 32-bit hash value (avoids re-hashing)
    void *key;          // Generic pointer to application key
    void *value;        // Generic pointer to application value
} Entry;

Required Callback Functions

Because the hash map implementation is agnostic of application-specific data structures, the consumer must supply specific hooks during map initialization:

1. Key Comparator (int (*key_cmp)(const void *k1, const void *k2)):
   Different keys can produce the same hash code (a hash collision) or map to the same bucket index. When a probe reaches a candidate location, checking pointer equality (k1 == k2) is insufficient. A custom comparator must evaluate value equality (e.g., strcmp for strings).

   Note: A value comparator is never required because the hash map never queries or re-indexes by value.

2. Key and Value Destructors (void (*free_key)(void*), void (*free_val)(void*)):
   In languages without automated garbage collection, overwriting an entry or dropping a bucket without freeing dynamically allocated payload memory causes silent memory leaks. Supplying optional destructor callbacks allows the map to safely clean up heap-allocated keys and values during hard deletes or eviction.

---

2. Implementing Hash Maps via Separate Chaining

In separate chaining, the primary backing array contains buckets, where each bucket holds a singly linked list of colliding nodes.

graph LR
    subgraph Bucket Array
        B0[Index 0]
        B1[Index 1]
        B2[Index 2]
    end

    subgraph Collision Chain
        B1 --> Node1[hash: 0x4F | key: 'a' | val: 'apple']
        Node1 --> Node2[hash: 0x9B | key: 'b' | val: 'ball']
        Node2 --> Null[NULL]
    end

Map and Node Structures

typedef struct Node {
    uint32_t hash_key;
    void *key;
    void *value;
    struct Node *next;
} Node;

typedef struct HashMapChained {
    Node **buckets;             // Array of pointers to linked list heads
    size_t capacity;            // Number of buckets
    size_t active_keys;         // Number of active entries
    int (*key_cmp)(const void*, const void*);
    void (*free_key)(void*);
    void (*free_val)(void*);
} HashMapChained;

Unified Lookup Semantic

Instead of exposing separate contains(key) and get(key) functions—which would double traversal costs when checking existence before retrieval—implement a single unified lookup(key):

• If the key is present: returns the associated void* value.
• If the key is missing: returns NULL.

(Note: If NULL is a valid stored value, a boolean status pointer or optional wrapper can be passed instead).

Handling Key Updates: Three Insertion Strategies

When put(key, value) is called with a key that already exists, a hash set simply drops the insert. A hash map, however, must handle the updated value. There are three architectural choices for managing this:

graph TD
    A[Put Key, Value] --> B{Strategy Choice}
    B -->|Strategy 1| C[In-Place Value Update]
    B -->|Strategy 2| D[Delete Node & Re-insert at Head]
    B -->|Strategy 3| E[Blind Insert at Head with Duplicates]
    
    C --> F[Low overhead, preserves list order]
    D --> G[Optimizes for read-after-write temporal locality]
    E --> H[O 1 write path, high read/delete overhead]

Strategy 1: In-Place Update (Standard)

• Mechanism: Traverse the bucket chain. If a node matches key_cmp, run the value destructor on the old value pointer and overwrite node->value = new_value.
• Pros: Clean, predictable memory footprint; keeps chain length constant.
• Cons: Requires a full traversal to the existing node before updating.

Strategy 2: Delete and Re-insert at Head (Temporal Locality)

• Mechanism: Traverse the chain, unlink the existing node, invoke its destructors, and prepend a brand-new node holding new_value to the head of the list.
• Pros: Capitalizes on temporal locality (“read-your-own-writes”). Recently inserted or updated keys stay near the head of the linked list, dramatically speeding up subsequent lookups without needing a separate LRU cache.
• Cons: Small pointer rearrangement overhead on update.

Strategy 3: Blind Insert (Write-Optimized Multi-Version Append)

• Mechanism: Push every incoming (key, value) straight to the head of the chain without scanning the list to see if the key already exists.
• Pros: Pure $O(1)$ constant-time writes. Excellent for write-heavy workloads.
• Cons:
  • Space Inefficient: Older, superseded versions of keys linger in the list.
  • Lookup Nuance: lookup() must strictly return the first matching node encountered from the head to preserve correct latest-write semantics.
  • Expensive Deletes: A delete operation can no longer terminate at the first match. It must traverse the entire bucket chain to locate and free every historic duplicate of that key.

Strategy Comparison

Feature	Strategy 1: In-Place Update	Strategy 2: Move-to-Head	Strategy 3: Blind Append
Write Complexity	$O(K)$ bucket traversal	$O(K)$ bucket traversal	$O(1)$ immediate prepend
Read Complexity	$O(K)$ average	$O(1)$ for recently updated	$O(K)$ to scan past shadow keys
Delete Complexity	$O(K)$ (stops at first)	$O(K)$ (stops at first)	$O(K)$ (must traverse full chain)
Memory Footprint	Optimal (1 node/key)	Optimal (1 node/key)	Bloated (multiple nodes/key)

---

3. Implementing Hash Maps via Open Addressing

In open addressing, all elements live directly inside a contiguous array. Collisions are resolved through probing sequences (e.g., linear probing, quadratic probing, or double hashing) without pointer-linked structures.

graph LR
    subgraph Open Addressed Array
        S0["Slot 0: [Empty]"]
        S1["Slot 1: [Active | hash: 0x4A | key: 'k1' | val: 'v1']"]
        S2["Slot 2: [Tombstone / Deleted]"]
        S3["Slot 3: [Active | hash: 0x8F | key: 'k2' | val: 'v2']"]
    end

Slot and Map Structures

typedef struct Slot {
    bool is_empty;
    bool is_deleted;    // Tombstone marker for soft deletes
    uint32_t hash_key;  // Cached hash
    void *key;
    void *value;
} Slot;

typedef struct HashMapOpenAddressing {
    Slot *slots;
    size_t capacity;       // Total allocated slots
    size_t used_slots;     // Active keys + Deleted tombstones
    size_t active_keys;    // Only active keys
    int (*key_cmp)(const void*, const void*);
    void (*free_key)(void*);
    void (*free_val)(void*);
} HashMapOpenAddressing;

Load Factor Calculation Nuance

In open addressing, soft-deleted slots (tombstones) interrupt probe termination just like active keys. If load factor were computed solely as $\frac{\text{active\_keys}}{\text{capacity}}$, an array full of tombstones would appear empty while probe chains degrade to $O(N)$ scans.

$\text{Load Factor } (\alpha) = \frac{\text{used\_slots}}{\text{capacity}} = \frac{\text{active\_keys} + \text{tombstones}}{\text{capacity}}$

Resizing (or rebuilding) must be triggered based on used_slots to ensure lookup chains remain short.

Mandatory Key Comparison

During probing for insert, search, or delete:

1. Check if slot.hash_key == target_hash.
2. If hashes match, execute key_cmp(slot.key, target_key) == 0.

Never delete or overwrite an entry based purely on hash equality or pointer equality. Doing so risks deleting or modifying unrelated keys whose hash functions collided.

Soft Deletion vs. Hard Deletion Lifecycle

A key distinction in open addressing systems is when to trigger memory destructors:

1. Soft Delete (delete operation):

   • The slot is flagged with is_deleted = true.
   • Crucially, do not invoke user destructors if the pointers are retained, or invoke destructors and nullify pointers immediately while leaving the tombstone flag high.
   • Standard practice: Clean up the key/value heap allocations during the soft delete, but preserve the is_deleted = true sentinel so probing logic can skip past the tombstone.

2. Hard Delete (Table Resizing / Rebuilding):

   • When resizing the array (growing or shrinking), allocate a fresh array.
   • Iterate over the old table: ignore empty and tombstone slots entirely.
   • Rehash and copy over only active entries.
   • Free the old array backing memory. Any lingering tombstones are permanently discarded without copying.

---

4. Key Takeaways

1. Hash Maps are Key-Centric: Values are passive payloads. Comparators, distribution logic, and probing sequences operate exclusively on keys.
2. Cache Hash Values: Storing a 32-bit hash_key inside nodes or slots prevents repeatedly hashing keys across collisions, resizing cycles, and comparisons.
3. Decouple Memory Management: Exposing optional free_key and free_val function pointers guarantees that heap-allocated user objects are safely collected when keys are overwritten or purged.
4. Chaining Insertion Dynamics:
   • In-place updates yield stable, predictable chains.
   • Move-to-head updates provide natural caching for high-temporal-locality workloads.
   • Blind appends maximize write throughput at the cost of degraded lookups and expensive multi-node deletes.
5. Open Addressing Tombstone Discipline: Always calculate load factors using both active entries and tombstones, and purge tombstones during resizing cycles to avoid degraded probe performance.