In a linear-probing hash table, how does a lookup find a key that collided when it was inserted?
answer
- The entry is somewhere in the array
- Insert and lookup must agree
- Walk the same sequence, one step at a time
- What proves a key is absent?
- Only a never-used slot ends the walk
basics
~20 sLinear probing puts a colliding key in the next free slot, so lookup replays that walk: start at the home slot and step forward comparing keys, stopping only at an empty slot, never at the first non-matching key.
solid answer
~40 sOpen addressing keeps every entry inside the table itself, so a collision is resolved by moving along a **probe sequence** until a free slot is found. With linear probing the sequence is `home, home+1, home+2, ...` modulo the table size, wrapping at the end. A lookup must walk exactly the same sequence: hash the key to its home slot, then compare slot by slot. The critical detail is the stop condition — a non-matching key means "keep going", because that slot may simply be an earlier collider sitting in your path; only a slot that has never been filled proves the key is absent. That is why an over-full open-addressed table is slow rather than wrong: the walk gets long, but it still terminates correctly.
code
pseudocode · 11 lines// each slot holds a stored entry or the marker EMPTY
FIND(table, key):
m = length(table)
i = hash(key) mod m
for step in 0..m-1:
if table[i] == EMPTY:
return NOT_FOUND // a never-used slot proves absence
if table[i].key == key:
return i
i = (i + 1) mod m // someone else's key: keep walking
return NOT_FOUND // table completely fullgo deeper
Be ready to walk an insert and a lookup on a small table at the whiteboard and say aloud why a non-matching key means keep going while an empty slot means stop.
Explain that insert and lookup are one contract: they must replay the identical probe sequence, the walk wraps, and it is bounded by the table size so a full table cannot loop forever.
Show the production judgment: state the cost as expected O(1) at a given load factor and O(n) worst case, and connect the contiguous-array layout to why this design is chosen on memory-tight or cache-sensitive paths.
Own the framing that the probe sequence is the table's only index: any change to hashing, table size, or slot lifecycle has to preserve it, which is what makes an open-addressed table cheap to read and expensive to modify carelessly.
### The setting Imagine a fixed-size sensor registry on an embedded device: a flat array of `m` slots, each holding either a `(sensorId, reading)` pair or the marker `EMPTY`. There is no room for per-slot side structures, so every entry must live *in* the array. That is open addressing. A hash function maps a `sensorId` to a **home slot** — `hash(sensorId) mod m`. Because `m` is far smaller than the space of possible ids, two different ids will eventually land on the same home slot. That is not a bug and not a sign of a bad hash function; by the pigeonhole principle it is unavoidable. Open addressing's answer is: if the home slot is taken, keep looking at other slots in a deterministic order called the **probe sequence**. ### Linear probing Linear probing is the simplest probe sequence: try `home`, then `home+1`, then `home+2`, and so on, wrapping around modulo `m`. Insert stops at the first slot that is `EMPTY` and writes there. The part candidates miss is that *insert and lookup are two halves of one contract*. Insert only makes sense because lookup can reproduce the walk. So lookup starts at `home` and steps forward with the same rule, comparing the stored key at each slot: - stored key equals the search key -> found, return it; - slot is `EMPTY` -> the key is not in the table, stop; - stored key is some *other* key -> **keep walking**. That third rule is the whole idea. A slot in your path holding somebody else's key does not mean your key is absent; it means an earlier collider got there first and your key, if present, was pushed further along. Stopping at the first mismatch is the classic wrong answer, and it silently loses entries. Equally, the walk must wrap: if the home slot is near the end of the array, the sequence continues at index 0. And it must be bounded — after `m` steps you have examined every slot, so a lookup on a completely full table terminates instead of spinning forever. ### Why the array is never allowed to fill Open addressing gives each key its own slot, so the number of stored entries can never exceed `m`. The **load factor** `alpha = n/m` therefore lives in `[0, 1]`. As `alpha` climbs, free slots become rare, probe walks get longer, and the cost of both insert and lookup rises sharply — which is why open-addressed tables are grown while there is still plenty of free space rather than being run near capacity. Contrast this with a bucket-list design, where several keys share a bucket and the load factor may legitimately exceed 1. ### What it buys The reward for this discipline is memory layout. The whole table is one contiguous block: no per-entry side allocation, no pointer chasing, and a probe walk touches consecutive addresses, so after the first slot the rest of a short run is usually already in the same cache line or the next one. On a memory-constrained device this is often decisive — a table that fits in fast memory and probes three slots beats one that follows two pointers into cold memory. ### Complexity, stated honestly Under a good hash function, a lookup or insert in an open-addressed table is **O(1) expected**, with the expectation depending on the load factor — the classic estimate for an unsuccessful linear-probe search is about `(1 + 1/(1-alpha)^2)/2` slot inspections. It is **O(n) worst case**: if every key hashes to the same home slot, or an adversary chooses keys to do so, the table degenerates into one long run and each probe walks it. "Hash lookup is O(1), full stop" is wrong in both directions — it ignores the load factor and it ignores adversarial or weak hashing. ### The mental model to carry into the interview A slot in an open-addressed table is not a private box for one home slot's keys; it is shared space that any earlier collider may occupy. The probe sequence is the only thing that ties a key to its location, so *anything that breaks the walk breaks the table*. Say that out loud and you have said the interesting half of open addressing.
- What happens to that lookup if the table is completely full and the key is absent?The walk visits every slot and then must stop. That is why the loop is bounded by the table size rather than only by "until an empty slot": with no empty slot anywhere, an unbounded version would circle forever. The cost of that lookup is O(m) — one more reason an open-addressed table is grown long before it fills.
- Can two keys with different home slots ever end up adjacent in the same run of occupied slots?Yes, and that is exactly what makes linear probing interesting. A key whose home slot falls inside an existing run walks to the end of it and extends it, so runs seeded by unrelated home slots merge into one longer run. From then on every key hashing anywhere into that run pays for the whole thing.
- Does the probe walk have to move forward by one? What else could it do?No — forward-by-one is just the simplest rule. Any deterministic sequence works as long as insert and lookup use the same one and it eventually covers enough of the table: stepping by a square-growing offset, or by a per-key stride derived from a second hash, are the two standard alternatives. Each changes how collisions pile up.
Like a row of numbered lockers where a latecomer takes the next free locker down the row: to find someone you start at their assigned number and keep walking until you hit a locker nobody ever used.
saying these in an interview costs you the question
- Says lookup stops at the first slot whose key differs
- Thinks the colliding key goes into a list hanging off the slot
- Forgets the probe walk wraps around the end of the array
- Claims open-addressed lookup is O(1) regardless of fill level
- Believes each home slot owns its slot exclusively