skip to content

Why must an open-addressed hash table run at a lower load factor than a chained one?

level: seniorimportance: must knowfreq 50%

answer

  1. Compare the two cost curves, not the constants
  2. One is a straight line in load factor
  3. The other has a pole at full
  4. What terminates a probe walk quickly?
  5. Free slots are the mechanism, not waste

basics

~20 s

Open addressing needs a free slot per key and its probe cost grows like 1/(1 - load factor), blowing up as the table nears full. Bucket-list designs degrade linearly and can exceed load factor 1, so they tolerate far higher fill.

solid answer

~50 s

The two schemes have different cost curves, not just different constants. In a bucket-list design the expected work is proportional to the average bucket occupancy — cost grows *linearly* with the load factor `alpha`, and `alpha` may exceed 1 because a bucket holds many keys. In open addressing every key needs its own free slot, so `alpha` is capped at 1, and the expected number of probes for an unsuccessful search grows like `1/(1-alpha)` in the idealized model and roughly `(1 + 1/(1-alpha)^2)/2` for linear probing. Those are hyperbolas: at 0.5 load a search costs a couple of probes, at 0.9 it costs tens, at 0.95 it is far worse still. The last few percent of capacity is where all the damage lives, so open-addressed tables are held at moderate fill — trading memory the design was supposed to save for a probe count that stays bounded.

go deeper

for a junior

Know that load factor is entries divided by slots, that an open-addressed table cannot exceed 1, and that a fuller table means longer searches.

for a middle

Explain the two cost shapes: roughly 1 + alpha for bucket lists versus a term in 1/(1 - alpha) for open addressing, and why the second one has a pole at full.

for a senior

Show operational judgment — tie rising fill to a detaching latency tail, argue why the mean hides it, and treat fill level as something to measure rather than assume.

for a principal

Own the memory-versus-tail-latency bargain: deliberately empty slots are what buys bounded probe walks, and defending that reserved headroom against pressure to pack the table is the call you are expected to make.

### The two cost curves Load factor is `alpha = n/m`: entries divided by slots. What that number means depends entirely on the collision strategy. **Bucket lists.** Each slot anchors a container of keys. The expected number of keys per bucket is exactly `alpha`, and an unsuccessful search inspects on the order of `1 + alpha` entries. This is a *straight line*. `alpha = 2` means an average of two entries examined — slower than `alpha = 0.5`, but nothing dramatic, and entirely legal because a bucket can hold as many keys as you like. **Open addressing.** Every key occupies its own slot, so `alpha <= 1` by construction. The relevant quantity is not "how many keys share my bucket" but "how far must I walk to find a free slot". Under the idealized uniform-hashing model, the expected number of probes for an unsuccessful search is about `1/(1-alpha)`, and for a successful one about `(1/alpha) * ln(1/(1-alpha))`. For linear probing the unsuccessful figure is closer to `(1 + 1/(1-alpha)^2)/2`. All of these are *hyperbolas with a pole at 1*. Put numbers on the idealized unsuccessful curve: `alpha = 0.5` -> 2 probes; `0.75` -> 4; `0.9` -> 10; `0.95` -> 20; `0.99` -> 100. For linear probing at `alpha = 0.9` the estimate is around 50. The curve is nearly flat over the first half of the table and then goes near-vertical. That shape is the entire answer. ### What this looks like in production Take an in-memory ticket-lookup table sized once at service start and filled through the day. For most of the morning it is under half full and lookups are essentially free — one or two slot inspections, all in cache. As the table crosses roughly two thirds full, p99 latency starts to lift; median barely moves, because the median lookup still lands in a short run while the tail lands in a long one. Past 0.8 the tail detaches from the median entirely. Engineers who watch only the average see nothing until the service is already in trouble — which is why fill level is a metric worth exporting, not a detail buried in the container. Two further points a senior answer makes: - **The distribution matters more than the mean.** Even at moderate load, clustering means probe lengths are not uniform: most walks are short, a few are long. The tail of the latency distribution is governed by the longest runs, not by the average probe count. Reasoning about a hash table with averages alone hides exactly the behaviour that pages you. - **The memory argument cuts both ways.** Open addressing is chosen partly to save memory — no side allocation per entry, one contiguous block, excellent locality. But holding it at, say, 0.7 fill means about 30% of the slots are deliberately empty. Compare *total* bytes honestly: a bucket-list design at higher fill still pays per-entry overhead for its links, so open addressing frequently wins overall even with the empty slots. What you must not do is claim the memory saving *and* fill the table to 95%. ### The wrong answer to aim at "Memory is expensive, so fill the array up." Every percent of extra fill past the knee costs disproportionately more probe work, and near the top a single insert can walk an enormous stretch. The lookup cost is not linear in occupancy; it is hyperbolic. Empty slots in an open-addressed table are not waste — they are the mechanism that terminates probe walks quickly. ### Mainstream runtimes disagree, which proves the point This is one of the places where production systems visibly made different calls on the same concept: the JVM's standard hash map uses bucket lists and ships a default load factor of 0.75, while CPython's dictionaries use open addressing and grow once they pass about two thirds full. Two different tolerable fill levels, two different collision strategies — the numbers differ because the underlying cost curves differ, not because one team was more conservative. ### The one-sentence version A bucket-list table gets gradually slower as it fills; an open-addressed table stays fast and then falls off a cliff, because its cost is governed by the scarcity of free slots rather than by the number of keys sharing one.

  • Why does the median lookup stay fast while p99 degrades first?
    Because probe lengths are not uniform. Clustering means most home slots sit in short runs while a minority sit in long ones, so the median lookup barely changes as the table fills while the tail — the keys landing in the long runs — grows with the worst run length. Monitoring the mean hides this entirely; watch the tail and the fill level together.
  • Does the answer change if lookups are almost always successful?
    It softens it. A successful search stops on a match, typically partway through a run, so its expected cost grows more gently — roughly logarithmically in 1/(1-alpha) in the idealized model — while an unsuccessful search must traverse to a free slot. A membership-check workload dominated by misses therefore feels high load much sooner than a hit-dominated one.
  • If empty slots are the mechanism, does open addressing really save memory?
    Often yes, once you compare total bytes. Holding 30% of slots empty is real overhead, but the alternative pays per-entry link overhead plus separate allocations and their headers, and loses contiguity. The comparison to make is bytes per stored entry at each design's operating fill level, not slot counts.

A parking lot that is 60% full is easy; at 97% full you circle for ages, because what you are hunting is not a space but the last few spaces.

saying these in an interview costs you the question

  • Says load factor means the same thing for both schemes
  • Claims filling the array to 95 percent saves memory for free
  • Thinks probe cost grows linearly with occupancy
  • Believes a load factor above 1 is impossible in any hash table
  • Judges table health from mean lookup time alone

context

resolving links…