1

Is it possible to have non-lazy delete (without tombstones) in open-addressed hash tables with collision resolution other than linear probing (but still open addressing)?

With linear probing, there is an algorithm here. I wonder, is there an algorithm for non-lazy delete, when we have quadratic probing/double hashing?

geza
  • 28,403
  • 6
  • 61
  • 135
  • In the link you posted, it says "The O(1) remove method above is only possible in linearly probed hash tables with single-slot stepping." – Alex Reinking Oct 27 '18 at 00:13
  • @AlexReinking: that's strange phrasing for me. That method is for linear probing, so of course it is only possible for linear probing. And I've tried to come up with something, and while this problem is hard, it doesn't seem impossible. Maybe it is not possible with quadratic probing, but maybe it is possible with some other probing method. – geza Oct 27 '18 at 00:41

3 Answers3

2

There is no such algorithm for any non-linear probing algorithm which has any value. It works for linear probing because the probe sequence is reversible. If the probe sequence is reversible, then all elements follow the same probe sequence (although they will start in different places along the sequence, based on the initial hash). So the secondary hash does nothing to prevent probe convergence, leading to the clustering of used nodes which characterises linear probing.

In other words, any probing algorithm which allows deletion by moving non-deleted elements backwards along the probe sequence will have the same sensitivity to load factor as linear probing, without the advantage of locality of reference provided by linear probing.

rici
  • 234,347
  • 28
  • 237
  • 341
1

The problem with deletion by pure removal is that empty slots may cause later searches to terminate before finding an item that really is in the table. If you maintain a counter giving the maximum number of probes taken before any insertion and terminate each failed search only after this number of probes then you could delete by simply removing items from their slots - but of course failed searches would be more expensive.

mcdowella
  • 19,301
  • 2
  • 19
  • 25
0

The algorithm on the wiki page is confusing and incomplete: here is a better version with optimized test for checking if k is outside range [i, j), considers j may be wrapped around:

function remove(key): boolean
    i := find_slot(key)
    if not slot[i].used
        return false // key is not in the table
    j := i
    loop
        j := (j + 1) modulo num_slots
        if not slot[j].used or j = i // if table was 100% full
            breakloop
        k := hash(slot[j].key) modulo num_slots
        if (j < i) xor (k <= i) xor (k > j)
            slot[i] := slot[j]
            i := j
    endloop
    slot[i].used := false
    num_slots := num_slots - 1
    return true
tylo
  • 41
  • 3
  • The `(j < i) xor (k <= i) xor (k > j)` condition leaves a lot of explaining to do. I have given it a try here: https://github.com/tim-janik/zcam-js/blob/b660dc8b42f8ae3e5191912f9884fab5b728197f/src/hashtable.js#L130 – TimJ Mar 23 '22 at 01:57