Coding Interview: How Do You Implement Robin Hood Hashing?

Prompt and scope

Implement a fixed-capacity open-addressing hash table with an array of m slots, where each slot holds at most one key-value pair. Support insert(key,value), contains(key), and remove(key). Resolve collisions with Robin Hood hashing; do not use chaining or tombstones. To focus on the core algorithm, a full table may return failure instead of resizing.

This is a general coding interview problem about data structures, invariants, edge cases, and complexity. Stanford CS106B's public assignment asks students to implement a Robin Hood table and explicitly includes probe-distance swapping, early lookup termination, and backward-shift deletion. A current software-engineering interview guide lists data-structure judgment, correctness, complexity, and edge-case handling as coding signals.

What the interviewer is testing

• Can you store each element's home bucket and PSL, or probe sequence length?
• Can you explain “the poorer key gets priority”: when the incoming PSL is larger, swap with the resident key that is closer to home?
• Can you use PSL monotonicity to stop a failed lookup early instead of scanning the whole array?
• Can you delete without tombstones while keeping every key in a probe cluster reachable?
• Can you state average and worst-case costs and choose a policy for high load?

A routine answer writes linear probing but misses that deletion holes truncate later searches. A strong answer turns both “empty slot” and “resident PSL below target PSL” into proved stop conditions.

Clarifications before answering

1. Is capacity fixed? With fixed capacity, insertion failure is an explicit result; with resizing, a load-factor threshold triggers a rebuild.
2. Are duplicate keys allowed? Assume a duplicate updates its value rather than adding a second slot; a multimap would need a different API and deletion contract.
3. Is the hash stable and are keys copyable? A hash must be stable during one operation. Caching the home bucket can avoid repeated work but consumes slot memory.
4. Must iterators or references remain stable? Swaps and backward shifts move elements, so stable addresses are not promised. Use indirection if callers need stable handles.
5. Is concurrency in scope? This is single-threaded. A concurrent version needs locking, striping, or a lock-free protocol; the ordinary implementation is not thread-safe.

30-second answer framework

“I store key, value, home bucket, and PSL in each occupied slot. Insertion linearly probes from home; when the incoming PSL exceeds the resident PSL, I swap them so the farther-traveled element gets priority, then continue placing the displaced item. A lookup can fail on an empty slot or when the resident PSL is below the target PSL, because later entries cannot jump back to a shorter distance. Deletion shifts later entries backward until an empty slot or a zero-PSL entry, decrementing PSL for each move so no search path is cut. Expected operations are near O(1), worst case is O(m), and space is O(m).”

Step-by-step deep answer

1. Slot model and invariants

Each occupied slot stores (key, value, home, psl). In a ring of m slots, psl = (index - home + m) % m. Maintain three invariants:

• home is the fixed hash origin for the key.
• Walking psl steps forward from home reaches the current index.
• Within one contiguous probe cluster, occupied PSL values never decrease; an empty slot ends the cluster.

The third invariant comes from giving priority to the larger PSL on insertion. It lets lookup compare the target PSL with the resident PSL instead of examining every later slot.

2. The linear-probing bottleneck

Plain linear probing walks forward from home until it finds an empty slot. At high load, an early key can occupy a slot close to home while a later key that has already probed far keeps walking; probe-length variance then inflates tail latency. Robin Hood hashing keeps the compact array layout but gives the farther-traveled key priority at collisions.

3. Robin Hood insertion

Pseudocode:

insert(key, value):
    item = (key, value, home=hash(key), psl=0)
    for step in 0 .. m-1:
        i = (item.home + item.psl) mod m
        if table[i] is empty:
            table[i] = item
            return success
        if table[i].key == key:
            table[i].value = value
            return updated
        if table[i].psl < item.psl:
            swap(table[i], item)
        item.psl += 1
    return full

After a swap, item is the displaced entry. Its PSL already describes the current probe position, so the next iteration increments it once. Keep empty slots distinct from a real entry whose PSL is zero; otherwise insertion and deletion boundaries become ambiguous.

4. Lookup and early termination

Lookup starts at the target home and tracks the target PSL:

contains(key):
    home = hash(key)
    for psl in 0 .. m-1:
        i = (home + psl) mod m
        if table[i] is empty:
            return false
        if table[i].psl < psl:
            return false
        if table[i].key == key:
            return true
    return false

An empty slot ends the cluster. A resident PSL below the target means later slots cannot contain the target, because the cluster's PSL does not decrease. Stanford's assignment treats this early stop as a core difference from ordinary linear probing.

5. Backward-shift deletion

Do not clear a slot immediately: a later key may have crossed it during collision resolution, and lookup would incorrectly stop at the hole. Tombstones are also disallowed and would lengthen probes over time.

remove(key):
    i = find_index_or_not_found(key)
    if i is not found:
        return false
    j = (i + 1) mod m
    while table[j] is not empty and table[j].psl > 0:
        table[i] = table[j]
        table[i].psl -= 1
        i = j
        j = (j + 1) mod m
    table[i] = empty
    return true

Stop at an empty slot or a zero-PSL entry. The former ends the cluster; the latter is at its home, so clearing the previous slot cannot cut its search path. Every move decrements PSL and restores the distance invariant.

6. Complexity and high-load policy

With uniform hashing and load factor α comfortably below one, expected probes for insert, lookup, and delete are constant-scale. A single operation can still scan all m slots, so worst-case time is O(m) and space is O(m). Robin Hood hashing mainly improves probe-length distribution and variance; it does not remove the open-addressing worst case. The cited analysis studies bounded variance in high-load models, but production code still needs a load threshold.

When α approaches that threshold, rebuild at a larger capacity instead of relying on expected O(1). If capacity must remain fixed, treat full as a normal business result and monitor failure rate, mean PSL, P99 probes, and deletion-shift length.

7. Counterexamples and tests

• Empty table insert and lookup: the home slot is filled directly, and a missing key stops at the first empty slot.
• Duplicate key: updating a value does not increase element count.
• Wraparound: choose a home near the end and verify (index - home + m) % m.
• Swap chain: construct colliding keys and verify one insertion can displace and place every item.
• Delete cluster head, middle, and tail: all remaining keys stay findable.
• Delete a home entry: stop when the successor has zero PSL, avoiding cross-cluster movement.
• Full table: the (m+1)th distinct key returns failure instead of looping forever.
• Adversarial hash: map many keys to one home, verify correctness, and expose O(m) probes in metrics.

High-quality sample answer

“I would use a fixed-capacity Robin Hood open-addressing table, storing the key, value, and PSL in every occupied slot. Insertion probes linearly from home. If the incoming entry has traveled farther than the resident entry, I swap them and continue placing the displaced entry. This keeps PSL nondecreasing within a probe cluster.

“Lookup uses that invariant: an empty slot fails, and a resident PSL below the target PSL also fails because later entries cannot return to a shorter distance. Deletion cannot leave a hole, so I shift entries backward while their PSL is positive and decrement each PSL; an empty slot or zero-PSL entry ends the shift. Expected time is near O(1), worst case is O(m), so load factor, P99 probes, and shift length decide whether to resize or reject insertion. Because shifts move elements, I do not promise stable iterators or addresses.”

Common mistakes

• Mistake → always keep the earlier resident on collision → later entries accumulate long probes → swap when the incoming PSL is larger.
• Mistake → stop lookup only on empty slots → lose the PSL optimization → also stop when resident PSL is below the target.
• Mistake → clear a deleted slot immediately → the hole truncates later probe paths → use backward shifting and decrement PSL.
• Mistake → stop shifting at any occupied entry → leave unreachable keys or move across clusters → shift only while the contiguous cluster's PSL is positive.
• Mistake → write expected O(1) as worst-case O(1) → bad hashes and high load invalidate it → state worst-case O(m) and enforce a load threshold.
• Mistake → promise stable references → swaps and deletion move entries → return handles, use indirection, or drop the address guarantee.

Follow-ups and responses

When should a dynamically growing table rebuild?

Trigger on both load factor and tail probe latency, such as a configured α or a P99 probe budget. Recompute every home and PSL during rebuild; copying slots directly is wrong because the array modulus changes. A write lock, dual-table migration, or background rebuild can serve different availability goals, but state the consistency and pause policy first.

Why avoid tombstones, and can backward shifting cost too much?

A tombstone makes deletion O(1) but permanently lengthens searches until a rebuild. Backward shifting concentrates work on deletes and keeps clusters compact. If deletes dominate and reads are rare, tombstones plus periodic rebuild can win; if read latency matters, prefer shifting and monitor move length.

How would you handle concurrent readers and writers?

This implementation is single-threaded. The simplest concurrent version uses a read-write lock; swaps and shifts must be one write critical section so readers never see a half-moved cluster. Higher throughput can use striped locks or immutable snapshots. A lock-free design needs version words, memory ordering, and reclamation; atomic slot pointers alone are insufficient.

Does Robin Hood make average lookup constant time?

Under common uniform-hash models, expected open-addressing cost depends on load factor. Robin Hood mainly reduces probe-length variance and tail spread. Average cost still rises at high load and worst case can scan the table, so variance improvements do not replace load control and benchmarks.