skip to content

Why does backward-shift deletion avoid tombstones only when the table uses linear probing?

level: middleimportance: nice to knowfreq 20%

answer

  1. Repair the path instead of marking it
  2. What must hold between home and slot?
  3. Scan forward to the next empty slot
  4. Move back only entries homed before the hole
  5. Candidates must form one contiguous run

basics

~20 s

Backward-shift deletion repairs the probe path instead of marking it: it pulls later entries back into the hole when the hole lies on their own path from home. Only linear probing puts every such entry in one contiguous run after the hole.

solid answer

~50 s

Deletion breaks one invariant — that every slot from a stored key's home slot to its position is non-empty. Tombstones preserve it by lying about the hole; backward-shift deletion repairs it instead. After emptying the slot, you scan forward to the next genuinely empty slot and, for each entry in that run, move it into the hole if the hole lies on the path from its home slot to its current position; the vacated slot becomes the new hole and the scan continues. The result is a table with no dead markers at all. It works because with linear probing, every key that could legitimately occupy the hole must currently sit in the contiguous run between the hole and the next empty slot. With quadratic probing or double hashing the displaced entries are scattered by key-dependent step sizes, so there is no bounded run to inspect — you would have to examine the whole table. That is why tombstones remain the general solution.

code

pseudocode · 14 lines
pseudocode
// delete key from a linearly probed table, no tombstones
i = slot_holding(key)
table[i] = EMPTY
j = i
while true:
    j = (j + 1) mod length(table)
    if table[j] == EMPTY:
        return
    k = hash(table[j].key) mod length(table)
    // does the hole i lie on this entry's path from k to j?
    if reached_first_going_forward(k, i, j):
        table[i] = table[j]
        table[j] = EMPTY
        i = j

go deeper

for a junior

Know that there is an alternative to marking deleted slots: pulling later entries back into the hole so the table keeps no dead markers at all.

for a middle

State the move condition precisely — an entry moves only when the hole lies on its forward path from its home slot — and explain why the scan stops at the first empty slot.

for a senior

Argue the tradeoff for a real workload: delete cost proportional to run length and relocated entries invalidating iterators, against the tombstone accumulation and rebuild it removes.

for a principal

Weigh maintainability, not just cost. A subtly wrong move condition is a silent data-loss bug, so a team owning this code needs the invariant written down and property-tested, which is part of the price of choosing it.

## The invariant everything hangs on An open-addressed table is searchable because of one property: **for every stored key, every slot on its probe path from its home slot up to its actual position is non-empty**. A lookup can therefore stop at the first empty slot it meets. Deletion breaks that property for any key whose path crossed the removed slot. There are exactly two honest responses: - **Lie about the hole** — write a tombstone, so the slot is still "non-empty" for path purposes. Cheap now, pays later in longer probes and a rebuild. - **Repair the paths** — move the affected entries so the invariant holds again with a genuinely empty slot. That is backward-shift deletion, known from the classic literature as the deletion algorithm for linear probing. ## The parking-lot picture Think of numbered parking spaces. Each car has a preferred space; if it is taken, the driver takes the next free one going forward. A car in space 14 might belong in 11, having been pushed along by earlier arrivals. When the car in 11 leaves, you don't cone off the space — you look forward: is there a car in 12, 13, 14 whose preferred space is 11 or earlier? If so, roll it back into 11 and repeat from the space it vacated. Stop at the first genuinely empty space. Afterwards, every remaining car can still be found by walking forward from its preferred space, and no cone is left behind. ## The move condition — the part people get wrong The run between the hole and the next empty slot cannot be shifted back wholesale. For an entry currently at slot `j` with home slot `k`, and a hole at `i`, the entry may move to `i` **only if `i` lies on the forward path from `k` to `j`** — that is, walking forward from `k` you reach `i` before you reach `j`. If instead the entry's home lies *after* the hole, moving it into `i` would place it **before** its own home slot. Any future lookup would start at `k`, walk forward, and never look back at `i` — the entry becomes unreachable. So those entries stay put, the scan steps past them, and the hole stays where it is until a movable entry is found. The scan terminates at the first EMPTY slot, because nothing beyond it can have a path crossing the hole. ## Why linear probing is required The algorithm depends on being able to enumerate every entry that *could* fill the hole by inspecting a bounded region. With linear probing that region is exactly the contiguous run of non-empty slots after the hole: probe sequences are `home, home+1, home+2, …`, so any key whose path crosses the hole and is still stored must be at or after the hole and before the next empty slot. With **quadratic probing** the step grows with the attempt number, and with **double hashing** the step is derived from the key itself. Two keys sitting in adjacent slots may have arrived by completely different routes, and a key whose path crosses the hole can be stored anywhere in the array. There is no bounded region to scan; identifying the candidates would mean walking the entire table and recomputing every stored key's probe sequence, which costs far more than the delete saves. Hence tombstones are the general-purpose answer and backward-shift is the linear-probing specialisation. ## What it costs - **Time per delete** is proportional to the length of the run after the hole, not constant. Under low load that run is short; as the table fills, deletes get more expensive — the mirror image of the tombstone strategy, which makes deletes cheap and everything else gradually worse. - **Entries move.** Any external state that names a slot index — an iterator position, a cached probe result, a pointer into the array — becomes stale. This is the reason many implementations refuse the technique outright: it makes deletion during iteration, and concurrent readers, much harder to reason about. - **Writes multiply.** One logical delete becomes several slot writes, which matters when slots are large or writes are expensive. In exchange you get a table that never accumulates dead space: the non-empty fraction genuinely tracks the live entries, the load-factor test needs no separate tombstone accounting, and lookups for absent keys never degrade from deletions at all. ## Choosing between them Tombstones favour delete-light workloads, large or moved-unfriendly entries, iteration-heavy use, and probe sequences other than linear. Backward-shift favours delete-heavy workloads on linearly probed tables with small entries and no external slot references — precisely where tombstone accumulation would otherwise force frequent rebuilds. The decision is not about elegance; it is about which cost you would rather pay and when: a slightly slower delete now, or a slow-motion degradation plus a bulk rebuild later.

  • Which invariant does the shift restore?
    That for every stored key, every slot from its home slot up to its position is non-empty. A delete breaks it for exactly those keys whose paths crossed the removed slot, and the shift restores it by relocating exactly those entries — after which a genuinely empty slot is safe, because no live key's path runs through it any more.
  • Which entries inside the scanned run must be left exactly where they are?
    Those whose home slot lies after the hole. The hole is not on their path, so pulling them back would place them before their own home slot; a lookup starting at that home walks forward and never revisits earlier slots, making the entry permanently unreachable. The scan steps over them and keeps looking for a movable one.
  • What does backward-shift cost that tombstoning does not?
    It moves live entries, so a delete costs several slot writes proportional to the run length rather than one, and any external reference to a slot index — an iterator position, a cached probe result — goes stale. Tombstoning never relocates data; it defers the cost into longer probe paths and an eventual bulk rebuild.

Numbered parking spaces where a driver whose space is taken rolls forward to the next free one. When someone leaves, you pull back the cars that had overflowed past that space instead of coning it off.

saying these in an interview costs you the question

  • Shifts the whole run back unconditionally
  • Claims it works for any probe sequence
  • Says deletion stays constant-time regardless of load
  • Ignores that entries move and invalidate slot references
  • Confuses it with rebuilding the whole table

context

resolving links…