Collision Resolution: Chaining

When two or more keys produce the same hash value and therefore map to the same index in the underlying array, a collision occurs. Every hash table implementation must have a strategy for handling collisions, and one of the oldest, most intuitive, and most widely used strategies is called chaining. Instead of searching for a different empty slot elsewhere in the array, chaining allows multiple key-value pairs to coexist peacefully at the same index by attaching them together in a secondary data structure — most commonly a linked list — that hangs off that bucket. Understanding chaining deeply means understanding not just how to implement it, but why it behaves the way it does under different workloads, and where its strengths and weaknesses lie compared with alternative approaches.

What Is Chaining?

The fundamental idea behind chaining is elegantly simple: every slot in the hash table's backing array does not hold a single key-value pair — it holds the head of an independent collection. When no keys have hashed to that index, the slot is empty (or holds a null reference). As soon as one key maps there, a node containing that key-value pair is placed in the slot. When a second key maps to the same index, rather than displacing the first or hunting for another slot, a new node is created and linked to the existing one. The slot now points to a list of two entries. A third collision at the same index simply extends the list to three nodes, and so on.

This approach means each bucket is entirely self-contained. A collision at index 5 has absolutely no effect on index 6 or any other index. The entries at index 5 form their own private list, and entries everywhere else in the table are completely unaffected. This isolation is one of chaining's most appealing characteristics.

While singly linked lists are the canonical choice for the bucket container — they are dynamic, require no pre-allocated memory, and support prepend in O(1) — they are not the only option. Some implementations use:

• Doubly linked lists, which make deletion slightly easier because you already have a pointer to the previous node.
• Dynamic arrays (like Python lists or Java ArrayLists), which offer better cache locality within a bucket at the cost of occasional resizing.
• Self-balancing binary search trees (such as red-black trees), which guarantee O(log k) worst-case lookup within a bucket of size k. Java's HashMap actually converts a bucket's linked list into a red-black tree when that bucket's chain length exceeds 8 entries, providing a safety net against degenerate inputs.

For the purposes of this discussion, a singly linked list is the primary mental model, as it illustrates all the essential concepts most clearly.

Consider a hash table with 7 buckets and keys "apple", "grape", and "mango", where suppose hash("apple") % 7 = 3, hash("grape") % 7 = 3, and hash("mango") % 7 = 1. After all insertions, the table looks conceptually like this:

Index 3 holds a two-node chain because both "apple" and "grape" hashed there. Every other index is either empty or holds a single-element chain. The key insight is that no slot is ever "full" — a bucket's chain can grow as long as memory permits.

Inserting with Chaining

Inserting a new key-value pair into a chaining hash table follows a straightforward sequence of steps:

• Compute the hash of the key and reduce it to a valid index: index = hash(key) % capacity.
• Check for an existing key first. Walk the chain at that index looking for a node whose key equals the new key. If found, update its value in place and stop. This prevents duplicate keys, which would corrupt the logical map abstraction.
• If no matching key exists, create a new node containing the key-value pair and insert it into the list. The most common insertion point is the head of the list, because prepending to a singly linked list is O(1) — you simply point the new node's next to the current head and update the bucket pointer to the new node.

Here is a pseudocode representation of this process:

function insert(table, key, value):
    index = hash(key) % table.capacity
    current = table.buckets[index]

    // Check for existing key
    while current is not null:
        if current.key == key:
            current.value = value   // update in place
            return
        current = current.next

    // Key not found — prepend a new node
    newNode = Node(key, value)
    newNode.next = table.buckets[index]
    table.buckets[index] = newNode
    table.size = table.size + 1

On average, when chains are short (which is the goal of a well-designed hash table), the while loop terminates quickly, making insertion effectively O(1) on average. The single expensive case is when many keys collide at the same bucket, but a good hash function and appropriate load factor management prevent this in practice.

It is worth noting that some implementations choose to append to the tail of the list instead of prepending. This is slightly more expensive for a singly linked list (requiring a traversal to find the tail), but it preserves insertion order within a bucket, which can occasionally matter. The duplicate-check traversal required anyway means the tail position is already known by the time insertion occurs, so appending adds no extra cost in that context.

Searching and Retrieving Values

Lookup in a chaining hash table is conceptually identical to the first phase of insertion:

• Compute index = hash(key) % capacity.
• Walk the linked list at table.buckets[index], comparing each node's key against the target key.
• If a match is found, return the associated value.
• If the end of the list is reached without a match, return null or undefined to signal that the key is absent.

function search(table, key):
    index = hash(key) % table.capacity
    current = table.buckets[index]

    while current is not null:
        if current.key == key:
            return current.value
        current = current.next

    return null   // key not found

The average-case time complexity of lookup is O(1), but this statement deserves a careful qualification. It holds when two conditions are met: (1) the hash function distributes keys approximately uniformly across buckets, and (2) the load factor — the ratio of stored entries to the number of buckets — is kept reasonably low. When both conditions hold, the expected chain length at any given bucket is proportional to the load factor, which is treated as a small constant, giving O(1) expected time.

The worst-case time complexity of lookup is O(n), where n is the total number of entries in the table. This worst case materializes when every single key hashes to the same index, turning the entire hash table into one long linked list and reducing it to a structure no better than a linear search. This is not merely a theoretical concern — an adversary who knows the hash function can craft inputs that deliberately trigger this scenario, a vulnerability known as a hash collision attack. Modern hash table implementations defend against this with randomized hash seeds (hash randomization), switching to tree-based buckets at high chain lengths, or both.

Deleting Entries with Chaining

Deletion is one of the areas where chaining shines compared with alternative strategies like open addressing. To delete a key:

• Compute the bucket index as usual.
• Walk the list, keeping track of both the current node and the previous node.
• When the target key is found:
  • If it is the head node (previous is null), update the bucket pointer directly to current.next.
  • If it is a deeper node, set previous.next = current.next, which stitches the list back together, skipping the deleted node.
• Decrement the table's size counter.
• If the key is not found, report failure or simply do nothing.

function delete(table, key):
    index = hash(key) % table.capacity
    current = table.buckets[index]
    previous = null

    while current is not null:
        if current.key == key:
            if previous is null:
                table.buckets[index] = current.next  // was head node
            else:
                previous.next = current.next          // bypass deleted node
            table.size = table.size - 1
            return true   // deletion succeeded
        previous = current
        current = current.next

    return false   // key not found

The performance profile of deletion mirrors that of lookup: O(1) average and O(n) worst case. Crucially, deletion in chaining is semantically clean — once a node is unlinked and its memory freed, it is truly gone. There are no ghost entries or special sentinel values left behind in the array. This cleanliness is a significant advantage over open addressing schemes, which must leave behind "tombstone" markers at deleted positions to avoid breaking the probe sequence for other keys that passed through that slot during their own insertion.

Load Factor and Its Effect on Chain Length

The load factor (commonly written as λ or α) is defined as:

load_factor = number_of_entries / number_of_buckets

It is the single most important quantity governing the performance of a chaining hash table. Under the assumption of uniform hashing (which a good hash function approximates), the expected length of the chain at any given bucket equals the load factor. This relationship directly determines the cost of all three operations:

Most practical implementations target a maximum load factor between 0.7 and 1.0 before triggering a resize. Resizing involves allocating a new, larger array (typically double the previous capacity), recomputing the hash-based index for every existing key-value pair in the old table, and reinserting each one into the new array. This process is called rehashing. It is an O(n) operation — every entry must be touched — but because it happens at most every time the table doubles in size, the amortized cost per insertion remains O(1).

After a resize, the load factor drops by approximately half (since capacity doubled while the number of entries stayed the same), chains become very short again, and fast O(1) average performance is restored. This dynamic resizing is what allows hash tables to maintain their performance guarantees as data grows, without requiring the programmer to predict in advance how many entries will be stored.

Trade-offs of Chaining vs. Other Strategies

Chaining is not the only collision resolution strategy. Open addressing is the primary alternative, where all entries are stored directly inside the backing array and a collision triggers a probe sequence to find the next available slot (using linear probing, quadratic probing, or double hashing). Understanding where chaining wins and loses relative to open addressing is essential for choosing the right implementation.

• Load factor ceiling: Chaining allows the load factor to exceed 1.0 without any logical failure — the chains simply grow longer. Open addressing fundamentally requires the load factor to remain strictly below 1.0, because every entry must occupy one of the array's slots, and a full array leaves nowhere to probe. In practice, open addressing becomes severely degraded well before the load factor reaches 1.0 (typically at around 0.7–0.8 for linear probing), making aggressive resizing mandatory.
• Memory layout and cache behavior: Open addressing stores all data inside a single contiguous array. This is extremely cache-friendly — probing nearby slots during a collision hits memory that the CPU has likely already fetched into cache. Chaining, by contrast, stores overflow nodes in heap-allocated memory scattered throughout RAM. Accessing the bucket itself is cache-friendly, but following the linked list's next pointers is a series of pointer dereferences into potentially distant memory locations, which the CPU's cache cannot predict or prefetch efficiently. For workloads with high lookup frequency and short chains, open addressing often wins on raw speed due to this cache advantage.
• Memory overhead: Each node in a linked list carries a next pointer in addition to the key and value. For small keys and values (like integers), this pointer overhead can double the memory footprint per entry compared with open addressing, which stores entries inline. However, chaining avoids the need to over-provision the backing array — with open addressing, a table at 50% load has half its array slots sitting empty as wasted reserved space.
• Deletion simplicity: As discussed, deletion in chaining is clean and leaves no side effects. In open addressing, deleting an entry by simply clearing its slot would break the probe chain for other entries that were displaced through that slot during their insertions. The standard fix — marking deleted slots with a special "tombstone" value — accumulates over time, degrading performance and requiring periodic compaction or rehashing to clear tombstones. Chaining completely avoids this problem.
• Predictability under adversarial inputs: Both strategies are vulnerable to adversarial key patterns, but the degradation manifests differently. With chaining, adversarial keys pile into one bucket creating a single long list; with open addressing, adversarial keys create long clustering patterns that slow probing across wide regions of the array. Both can be mitigated with hash randomization.
• Suitability for unpredictable workloads: Because chaining can absorb arbitrarily many entries per bucket (memory permitting) and because deletion is side-effect free, chaining is generally the preferred choice when the number of insertions is unknown in advance, when deletions are frequent, or when the table will be heavily loaded. Open addressing tends to be favored in performance-critical systems where the working set is known, the load factor can be tightly controlled, and cache efficiency is paramount (such as in embedded systems, database indexes, or CPU caches themselves).

To summarize the comparison concisely:

Chaining is the backbone of many production hash table implementations, including the default dictionaries in Python (which uses open addressing, but Java's HashMap, Ruby's Hash, and many C++ std::unordered_map implementations use chaining). Its simplicity, flexibility, and graceful handling of high load and frequent deletions make it an enduringly practical choice wherever the full generality of a hash map is needed.