In separate chaining, why is expected lookup cost 1 + load factor rather than flatly O(1)?
answer
- Load factor is a ratio, but of what
- Entries divided by buckets, per bucket
- One step you always pay, one that varies
- The constant comes from the resize policy
- Expectation assumes the hash spreads
basics
~20 sLoad factor is entries divided by buckets — under uniform hashing, exactly the expected chain length. A lookup pays a constant-time bucket index plus a walk of that many nodes, so cost is 1 + load factor, constant only because resizing bounds it.
solid answer
~40 sWrite the load factor as `alpha = n / m`, entries over buckets. If the hash spreads keys independently and uniformly, each bucket holds `alpha` entries in expectation, so an unsuccessful lookup scans about `alpha` nodes and a successful one about `1 + alpha/2`. Adding the constant-time bucket index gives the familiar `O(1 + alpha)`. That collapses to O(1) only because the table resizes to keep `alpha` under a fixed threshold — the constant is a policy decision, not a law. Two consequences worth saying out loud: chaining still works with `alpha` above 1, since chains simply get longer rather than the table filling up; and the bound is an *expectation* over a uniform hash, so it says nothing about a specific badly-distributed key set.
code
pseudocode · 10 linesb = hash(key) mod length(table)
node = table[b]
steps = 0
while node != null:
steps = steps + 1
if node.key == key:
return node.value
node = node.next
// expected steps ~ n / m for a miss
return NOT_FOUNDgo deeper
Know that load factor means entries divided by buckets, and that under chaining it is the average number of entries sitting in one bucket. That single fact carries most of the answer.
Derive the cost out loud: constant bucket index plus an expected walk of alpha nodes, roughly 1 + alpha/2 on a hit and alpha on a miss, constant only because resizing pins alpha.
Show judgment about picking the threshold: a lower alpha shortens walks and costs memory, a higher one saves memory and lengthens the pointer-chasing path, and the right number depends on the read/write mix you are serving.
Be ready to defend the expected-time guarantee as a risk position, not a fact — state what your service does when the uniformity assumption fails and what latency budget the chosen threshold is actually buying.
## The quantity being measured The **load factor** of a hash table is `alpha = n / m`, where `n` is the number of stored entries and `m` is the number of buckets. Under separate chaining it has a very concrete meaning: it is the **average number of entries per bucket**, because every entry lives in exactly one bucket's chain. ## Where 1 + alpha comes from The standard analysis assumes *simple uniform hashing*: each key is equally likely to land in any bucket, independently of the others. Under that assumption, the expected length of any given chain is `alpha`. A lookup does two things. First it computes the hash and reduces it to a bucket index — a constant-time step regardless of table size. Then it walks that bucket's chain, doing one key comparison per node. So: | Operation | Expected node comparisons | |---|---| | Unsuccessful lookup | `alpha` (the whole chain is scanned) | | Successful lookup | about `1 + alpha/2` (stops on average halfway) | | Insert at head (no duplicate check) | 0 | | Insert with replace semantics | same as a lookup | Add the constant index step and you get `O(1 + alpha)` — the `1` is the bucket index you always pay even when the chain is empty, and `alpha` is the walk. ## Why that is not the same as O(1) `O(1 + alpha)` becomes O(1) **only when `alpha` is bounded by a constant**, which is the whole reason tables resize. A growth policy that doubles the bucket count once `alpha` crosses a threshold keeps the expected chain length pinned near that threshold forever, so amortized over many inserts each lookup is expected constant time. Remove the resize policy and the same table degrades linearly: insert ten million entries into a thousand buckets and every lookup walks ten thousand nodes on average. Nothing about chaining itself promises constant time; the resize policy does. It is also worth being precise about *what kind* of guarantee this is. It is an **expectation** under an assumption about the hash, not a worst-case bound and not an amortized bound. Amortized reasoning would smooth an expensive resize over the cheap inserts around it; expectation here is about how the keys scatter. A key set that defeats the uniformity assumption defeats the bound outright, and no amount of resizing repairs it. ## The load factor above 1 point A chained table is perfectly functional with `alpha = 3`: buckets simply hold three entries on average, and lookups cost about four steps instead of two. There is no notion of the table being "full", because entries never compete for a slot — they compete only for the reader's patience. This is the structural difference from strategies that store entries directly in the bucket array, where the number of entries can never exceed the number of slots and performance degrades sharply well before that ceiling. Chaining's degradation is gentle and linear in `alpha`; that is its defining operational property. ## The skeptic's objection, and the honest answer Suppose you defend a chained table to a colleague reviewing a log-ingestion service that maps session identifiers to their event lists, and they object that "linked lists are slow". They are pointing at something real: each hop from one node to the next is a pointer dereference into memory that the previous node did not bring with it, so a chain walk costs one dependent memory access per node in the worst case. A three-node chain is not three cheap steps; it is potentially three round trips that cannot be overlapped because each one's address comes from the previous. The honest answer is a quantified one rather than a dismissal: at `alpha = 0.75` the *expected* walk is well under one node, so the common case is a bucket index and at most one hop. The pointer-chasing cost is real but it is multiplied by a small expected count, and it buys gentle degradation and simple deletion. If profiling shows the walk dominating, the fix is to lower `alpha`, improve the hash, or change the bucket's internal layout — not to abandon the argument. ## What to say in an interview Give the formula, name the assumption, then name the policy. "Expected chain length is the load factor under uniform hashing, so a lookup is `1 + alpha`; it reads as O(1) only because the table resizes to keep `alpha` bounded, and only in expectation over a hash that actually spreads." Candidates who say "chaining is O(1)" and stop have skipped both the assumption and the policy, which is precisely the follow-up the interviewer has queued up.
- Can a chained hash table operate with a load factor above 1?Yes. Entries never compete for a slot, so exceeding one entry per bucket simply means chains average more than one node. A table at `alpha = 3` costs roughly four steps per lookup instead of two and keeps working. The threshold implementations pick is a latency choice, not a capacity limit — chaining degrades gently and linearly in `alpha` rather than hitting a wall.
- Is the 1 + alpha bound an average-case or an amortized result?Average-case, in the probabilistic sense: it is an expectation taken over the assumption that the hash scatters keys uniformly and independently. Amortized bounds are a different tool — they spread the cost of occasional expensive operations, such as a resize, across a worst-case sequence. Chaining uses both: expectation for chain length, amortization for the doubling.
- Why does an unsuccessful lookup cost more than a successful one at the same load factor?A miss must prove the key is absent, which means walking the chain to its end — about `alpha` comparisons. A hit can stop as soon as it matches, which happens on average partway through, giving roughly `1 + alpha/2`. That asymmetry matters for workloads dominated by negative lookups, such as membership filters, where the miss path is the hot path.
saying these in an interview costs you the question
- Says chaining is O(1) without naming the resize policy
- Thinks load factor must stay below 1 for chaining
- Confuses the expectation with a worst-case bound
- Calls the 1 + alpha result amortized rather than expected
- Claims chain length depends on total table size