Separate Chaining and the Load-Factor Threshold

A hash table is a promise that a lookup will cost about the same whether the table holds ten keys or ten million. Nothing in the array of buckets enforces that promise; it is enforced by the collision policy. Separate chaining is the simplest policy that keeps the promise without any restriction on how full the table may become, and reading its cost model closely shows exactly which quantity the load factor governs.

The bucket array and the list hanging off each slot

The structure is two levels. An array of m slots holds either a null pointer or a pointer to the first node of a list. Each node stores a key, a value, and a pointer to the next node. A hash function maps a key to an integer, and the table reduces that integer modulo m to select a slot.

Insertion hashes the key, walks to the slot, and links a new node at the front of the chain. That is O(1) work regardless of how many keys are already present, because the new node goes in front and no existing node moves. Lookup hashes the key, then walks the chain comparing stored keys until it finds a match or reaches the end. Deletion hashes, walks, and unlinks, which is also O(1) once the node is found.

The walk is where the cost lives. If the hash function distributed keys perfectly evenly, a chain would hold n/m nodes and a lookup would compare against n/m keys. Real hash functions do not distribute perfectly, but they behave close enough to uniform that the expected chain length is the ratio itself.

That ratio is the load factor, written α = n/m. It is dimensionless, and it is the only quantity that appears in the cost analysis.

What the load factor buys and what it costs

Under the assumption that every key is equally likely to hash into each of the m slots, independently of the others, the expected number of nodes examined in an unsuccessful search is exactly α. For a successful search, the key sits at a uniformly random depth in its chain, so the expected number of nodes examined before it is about α/2, plus the one comparison that succeeds. Both are Θ(1 + α), which is the standard statement of the result.

The practical reading is that the chain length is short as long as α is small, and the cost grows linearly once α is large. A table with α = 1 examines one node per lookup on average. A table with α = 10 examines ten. There is no cliff and no failure, only a steady degradation.

Because chaining places no limit on how many keys a slot may hold, α may exceed 1. This is the property that distinguishes it from open addressing, where every key must occupy its own slot and the table becomes unusable as α approaches 1. A chained table at α = 2 is a slow hash table. An open-addressed table at α = 1 is full and cannot accept another key without rebuilding.

Memory cost is the counterweight. Each key needs a node, and a node needs at least one pointer for the chain. On a 64-bit machine that pointer is 8 bytes, and a separately allocated node also carries the allocator’s own bookkeeping, which rounds the allocation up to a size class and can add a header of the same order as the pointer. A table with a million small keys pays several megabytes for chain links alone, plus the pointer array itself, which is 8 bytes per slot.

There is a second, quieter cost: locality. A lookup touches the bucket array once and then a node somewhere else in the heap. Those are two separate cache misses on a machine where a cache line is 64 bytes and holds eight pointers. Open addressing, which stores keys directly in the slot array, often needs one.

Library defaults sit where the arithmetic says they should. Java’s HashMap documents a default initial capacity of 16 and a default load factor of 0.75, resizing when the number of entries exceeds capacity times load factor. CPython’s dictionary, which uses a different layout, resizes once the table is about two-thirds full. Both numbers are chosen so that the average chain stays near or below one and the resize cost stays amortized.

Reference stability across a rehash

Chaining has a property that matters more than its cost curve and is easy to overlook: the nodes do not move when the table resizes. A rehash allocates a larger bucket array, walks every chain, and relinks each node into its new slot. The node addresses are unchanged.

This is why the C++ standard’s container requirements state that rehash invalidates iterators but that references and pointers to elements remain valid: relinking nodes does not change their addresses. Code that stores a pointer to a value inside an unordered container keeps a valid pointer across insertions that trigger growth. Open-addressed tables cannot offer that, because growth means moving the entries themselves.

The guarantee is conditional. Erasing the element invalidates its pointer, and so does any operation that destroys the container. The stability applies to relocation during growth, not to the element’s lifetime.

Chains that do not stay short

The cost model assumes uniform hashing. Every failure mode of a chained table is a failure of that assumption or a consequence of the per-node allocation.

A hash function that ignores part of the key concentrates keys in a few slots. So does one that maps distinct keys to the same bucket by construction: if the bucket count is a power of two and the hash is computed as a plain modulo of a value whose low bits are poorly mixed, the high bits never influence the slot. A table can hold a thousand keys in one chain while nine hundred and ninety-nine slots sit empty, and every operation on those keys costs a thousand comparisons.

Adversarial input makes this deliberate. If an attacker can predict which keys collide, the table becomes a linked list and each insertion costs the current length, so filling it costs quadratic time. That attack and its defences are the subject of hash flooding.

Allocator behaviour matters at scale. A million small nodes scattered across the heap produce poor locality and can fragment the allocator, and the per-node overhead can exceed the key and value combined. Some implementations pool nodes or store the first few entries inline in the bucket slot to avoid an allocation on the common path.

Finally, resizing is not free even though it is amortized. Doubling the bucket array and relinking n nodes is Θ(n) work in one operation, and the latency of that operation scales with the table size, which is a latency spike rather than a throughput problem. Applications with hard latency bounds either pre-size the table or spread the migration over subsequent operations, a technique covered in incremental rehashing.

A minimal insertion routine shows how little there is to the mechanism:

struct node { struct node *next; const char *key; void *val; };
struct table { struct node **slot; size_t mask, count; };

static void table_grow(struct table *t);

void table_put(struct table *t, const char *key, void *val)
{
    size_t i = hash(key) & t->mask;          /* mask requires power-of-two slot count */
    for (struct node *n = t->slot[i]; n; n = n->next)
        if (strcmp(n->key, key) == 0) { n->val = val; return; }

    struct node *n = malloc(sizeof *n);
    n->key = key; n->val = val;
    n->next = t->slot[i];                    /* insert at head: O(1) */
    t->slot[i] = n;

    if (++t->count * 4 > (t->mask + 1) * 3)  /* grow past 0.75 */
        table_grow(t);
}

Two details in that fragment carry most of the design. The mask replaces a modulo, which is only valid when the slot count is a power of two, and the growth test is expressed in integer arithmetic to avoid floating point on the insertion path. The grow function must relink every node, and it must do so before any subsequent operation observes the new array.

Chaining is the policy to reach for when deletion is frequent, when keys are large and copying them on every probe is unacceptable, or when the language requires stable references. Open addressing wins on memory density and locality, and it wins decisively when the table fits in cache. The next question is what happens when the keys live in the slot array itself, which is where linear probing begins.