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.)
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.