In separate chaining, what happens when two keys hash to the same bucket, and what does a lookup then cost?

## The problem chaining solves A hash table maps a key to a slot by reducing the key's hash value into the range of a bucket array. Because there are far more possible keys than buckets, two distinct keys will eventually reduce to the same index. That is not bad luck; the pigeonhole principle guarantees it. Every hash table therefore needs a collision-resolution strategy, and separate chaining is the most direct one: **make each bucket hold a collection of entries rather than a single entry.** ## What a bucket actually holds In the classic form, each bucket holds a pointer to the head of a singly linked list. Each list node stores the key, its value, and a pointer to the next node — many implementations also cache the entry's hash value in the node, which pays off later. The bucket array itself is just an array of pointers, most of which may be null. Consider a log-ingestion service that maps a session identifier to the list of events seen for that session. Two different session identifiers can easily land in bucket 7. Chaining's answer is that bucket 7 now holds a two-node chain, and both sessions are retrievable. ## The three operations **Lookup.** Compute the hash, reduce it to a bucket index, then walk that bucket's chain. For each node, compare the stored key with the search key for *equality*. If a cached hash is stored in the node, compare hashes first as a cheap filter and fall back to full key comparison only when they match — a hash mismatch proves the keys differ, but a hash match proves nothing. Cost: one constant-time index plus one comparison per node walked. **Insert.** Compute the bucket, then link the new node in. Linking at the head is O(1) and needs no traversal. But if the table has map semantics — one value per key, where re-inserting an existing key must replace rather than duplicate — the insert must first scan the chain to find an existing entry. Skipping that scan is a classic bug: the table silently accumulates two nodes with the same key, and lookups return whichever the walk reaches first, so the older entry is shadowed but never freed. **Delete.** Walk the chain, unlink the node, done. Nothing about the rest of the table is disturbed, and no marker has to be left behind — a genuine simplicity advantage of chaining over strategies that store entries directly in the bucket array. ## Why the collision is not an overwrite The single most common junior error is to say the second key overwrites the first, or that a collision forces an immediate resize. Neither is true. Overwriting happens only when the *keys are equal*, which is decided by the equality comparison, not by the hash. And a resize is triggered by the table's overall load factor crossing a threshold, not by any individual collision — a table can and does operate with collisions present at all times. ## What the cost really is Describe the cost as "constant time plus the chain walk" and you will always be right. The bucket index is O(1). The walk is proportional to the number of entries in that one bucket. When keys spread evenly and the table resizes to keep the ratio of entries to buckets bounded, chains stay short and lookups are O(1) *expected*. When keys spread badly, one chain can hold a large share of the entries and lookups on it degrade toward O(n) — the table still returns correct answers, it just gets slow. This is why careful people say hash lookups are O(1) expected and O(n) worst case, never "O(1), full stop". ## Interview framing If you are asked "what happens on a collision", answer in three beats: both entries are kept in the same bucket's chain; lookup indexes the bucket then scans the chain comparing full keys; the cost is therefore one plus the chain length, which is short only when the hash distributes well. That answer shows you know the mechanism *and* where its guarantee comes from, which is exactly the difference the interviewer is listening for.