Implementing Hash Table Resizing: Separate Chaining and Open Addressing

A hash table’s primary appeal is its near-constant time complexity—$O(1)$ average-time lookup, insertion, and deletion. However, this theoretical bound degrades as the table fills up and collisions accumulate. To maintain consistent performance and avoid wasted memory, dynamic resizing (both growing and shrinking) is essential.

Resizing involves deciding when to resize, where in the codebase to hook the trigger, and how to move elements efficiently between arrays while accounting for the underlying collision resolution strategy—specifically separate chaining vs. open addressing.

---

1. The Core Metrics: Load Factor and Triggers

The health of a hash table is captured by its load factor (commonly denoted as $\alpha$):

$\alpha = \frac{\text{Number of Keys}}{\text{Total Slots in the Table}}$

As $\alpha$ approaches 1, the probability of collisions increases dramatically:

• In separate chaining, the average linked list length grows, turning $O(1)$ lookups into $O(L)$ linear scans.
• In open addressing, collision probe sequences become significantly longer, exponentially degrading lookup and insertion times.

Thresholds for Growing and Shrinking

To balance memory overhead and lookup performance, industry-standard implementations use the following heuristics:

1. Growing (Upsizing):
   • Trigger: During an insert operation, if $\alpha \ge 0.5$ (or up to $0.75$ depending on the variant), double the table size ($2 \times \text{capacity}$).
   • Goal: Spread entries across more buckets, reducing collision chains.
2. Shrinking (Downsizing):
   • Trigger: During a delete operation, if $\alpha \le 0.125$ (i.e., $\frac{1}{8}$), halve the table size ($\frac{\text{capacity}}{2}$).
   • Goal: Reclaim contiguous heap memory when many keys have been removed.
   • Why $\frac{1}{8}$ and not $\frac{1}{2}$?: Hysteresis prevents “thrashing” (rapidly oscillating between doubling and halving near a boundary when alternating inserts and deletes).

---

2. Resizing with Separate Chaining

In separate chaining, each slot in the table array points to the head of a linked list (or another secondary structure) holding collided key-value pairs.

Index
  0  --> [ Key A | * ] -> [ Key E | NULL ]
  1  --> NULL
  2  --> [ Key B | NULL ]
  3  --> [ Key C | * ] -> [ Key D | NULL ]

Every resize operation requires three high-level steps:

1. Allocate a new bucket array of the target size.
2. Rehash and migrate keys from the old bucket array to the new one.
3. Free the old bucket array.

There are two approaches to migrating linked list nodes:

Approach A: Re-insertion by Value (Simple but Expensive)

Iterate over every linked list in the old array and invoke the existing insert(new_table, key, value) function.

Old Table Node -> Read Key/Value -> Invoke insert() -> malloc() New Node -> Free Old Node

• Pros: Highly readable and clean; reuses standard insertion logic.
• Cons: Severe memory churn. Every key triggers a memory allocation (malloc) for a new linked list node, followed by a free of the old node. In memory-constrained or latency-sensitive environments, this allocation overhead causes latency spikes and memory fragmentation.

Approach B: In-Place Pointer Readjustment (Efficient)

Instead of allocating fresh linked list nodes, reuse the existing allocated nodes by rewiring their next pointers into the new bucket array.

       Old Table Slot                New Table (2x Size)
[ Node A ] -> [ Node B ]    ===>    Slot X: [ Node A ] -> NULL
                                    Slot Y: [ Node B ] -> NULL

void resize_chaining(HashTable *table, size_t new_capacity) {
    Node **new_buckets = calloc(new_capacity, sizeof(Node*));
    
    for (size_t i = 0; i < table->capacity; i++) {
        Node *curr = table->buckets[i];
        while (curr != NULL) {
            Node *next = curr->next; // Save next reference
            
            // Recompute index for new capacity
            size_t new_idx = hash(curr->key) % new_capacity;
            
            // Prepend node to the new bucket chain
            curr->next = new_buckets[new_idx];
            new_buckets[new_idx] = curr;
            
            curr = next;
        }
    }
    
    free(table->buckets);
    table->buckets = new_buckets;
    table->capacity = new_capacity;
}

• Pros: Zero node allocations. Only the array of bucket pointers is allocated, resulting in lower latency and minimal memory overhead.
• Cons: Pointer manipulation code is slightly more complex and prone to pointer bugs if not carefully handled.

---

3. Resizing with Open Addressing

Open addressing stores all entries directly within the array without auxiliary linked lists. When collisions occur, probing strategies (linear, quadratic, or double hashing) find the next available slot.

The Problem: Soft Deletes (Tombstones)

Open addressing cannot physically erase a key upon deletion. Doing so would break the probe sequence for keys inserted subsequent to that collision:

Initial:       [ K1 ] [ K5 ] [ K2 ] [ K4 ]   (All collided at index 0)
Delete K5:     [ K1 ] [  ? ] [ K2 ] [ K4 ]

If slot 1 is cleared to EMPTY, a lookup for K4 starts at index 0, hits index 1, finds it empty, and prematurely halts, falsely reporting that K4 does not exist.

Therefore, open addressing requires soft deletes (tombstones). A tombstone indicates: “This slot is empty for inserts, but continue probing for lookups.”

Why Tombstones Complicate Resizing

Tombstones occupy slots and degrade probe efficiency just like active keys. If you only track active keys, the calculated load factor will be artificially low, while the physical table is saturated with tombstones, causing long probe sequences and performance degradation.

The Solution: Dual-Counter Tracking

To calculate the true operational load factor, maintain two separate counters in the table metadata:

1. active_keys: Number of currently valid, accessible keys.
2. used_slots: Total number of slots containing either an active key or a tombstone (soft-deleted key).

typedef struct {
    Entry *slots;
    size_t capacity;
    size_t active_keys; // Decremented on delete
    size_t used_slots;  // NOT decremented on delete
} OpenAddressingTable;

Operation           active_keys           used_slots
------------------------------------------------------------
Insert new key      active_keys++         used_slots++
Delete key          active_keys--         (No change)
Resize Table        active_keys (same)    used_slots = active_keys

Calculating $\alpha$ in Open Addressing

The effective load factor must be computed using used_slots:

$\alpha_{\text{probe}} = \frac{\text{used\_slots}}{\text{capacity}}$

• When $\alpha_{\text{probe}} \ge 0.5$, trigger a resize to double the capacity.
• When shrinking (evaluating after deletes), compute the ratio using active keys: $\alpha_{\text{active}} = \frac{\text{active\_keys}}{\text{capacity}}$. If $\alpha_{\text{active}} \le 0.125$, halve the capacity.

Purging Tombstones During Resizing

A critical optimization occurs during the migration phase of open addressing resize:

1. Allocate the new table array.
2. Iterate through the old table.
3. Migrate only active keys. Rehash each active key into the new array.
4. Discard soft-deleted slots completely. Do not migrate tombstones.
5. Reset used_slots = active_keys.

flowchart LR
    subgraph Old Table
        A["Active: K1"]
        B["Tombstone: DEL"]
        C["Active: K2"]
        D["Tombstone: DEL"]
    end

    subgraph New Table
        E["Active: K1"]
        F["Active: K2"]
        G["Empty"]
        H["Empty"]
    end

    A -->|Rehash| E
    B -.->|Dropped| X((Discard))
    C -->|Rehash| F
    D -.->|Dropped| X

Discarding tombstones consolidates probe sequences, clearing artificial collision trails and resetting lookup efficiency to optimal levels.

---

4. Comparison Summary

Feature	Separate Chaining	Open Addressing
Space Mechanism	Pointers to linked lists / trees	Single contiguous flat array
Deletion Model	Physical removal (free node)	Soft deletion (tombstone markers)
Tracking Counters	Single key counter (count_keys)	Dual counters (active_keys & used_slots)
Resize Optimization	Pointer rewiring (avoiding node re-allocations)	Purging tombstones during element migration
Growth Threshold	Typically $\alpha \approx 0.5 - 0.75$	Strictly $\alpha \le 0.5$ (probe clustering prevention)
Shrink Threshold	$\alpha \le 0.125$ (halves array)	$\alpha \le 0.125$ (halves array)