I'm looking for the algorithm for deleting an element from a linear-probing hash table that does a delete-and-shift instead of just using tombstone elements.
The basic idea is quite simple - but I keep getting caught up in corner cases (notably, w.r.t. "wraparound", where an element hashes to a high slot but all the end slots are full so the index it is actually inserted at is low.)
Basic idea:
When you delete an element, keep track of the slot and start scanning forwards. If you hit an element that's null (read: not present), you're done. Otherwise, if you hit an element that hashes to a slot <= the slot kept track of, move that element to the kept-track-of slot, and keep track of the current slot instead.
Or in pseudocode:
func del(item i):
slot s = get_slot_of(i)
table[s] = null
fixup(s)
func fixup(slot s):
assert table[s] == null
slot t = s
while table[++t] != null:
if get_slot_of(table[t]) <= s:
table[s] = table[t]
table[t] = null
s = t
In simple cases, this works. But as soon as you include the modulo behavior, it falls flat on its face.
So how would I go about fixing this up such that it doesn't fall flat on its face in such cases? I looked around, but couldn't find this algorithm implemented anywhere - it seems like most places that use linear probing just use tombstone elements instead.