slavapestov/factor — Issue #381: Re-use deleted tombstones in hashtables
Author: slavapestov
Created: 2011-11-10 05:37:51+00:00
State: open

Delete-heavy hashtables rehash too much.

The problem is that right now, we don't reuse deleted tombstones -- new-key@ skips over them. The reason is the following. Suppose you have a two-entry hashtable and two keys, A and B, with the same hashcode. You insert A first:

[A]***

Then you insert B. You collide, so you insert it at the second location:

[A][B]

Now you delete A

***[B]

Now you insert B again. But it hashes to the first bucket. However if you store it there,

[B][B]

Oops!

This is why the current implementation would rehash in the above case.

The right fix is to change new-key@ to remember two locations; the location of the last deleted tombstone, and the current index. Upon encountering a deleted tombstone, it doesn't stop, but it remembers its location and keeps probing.

Then, at some point, the loop will either find an equal key, or hit an empty tombstone. If you found the equal key, replace its value as before.

If you found an empty tombstone, then at this stage there are two possibilities:
- if you saw a deleted tombstone, insert the original key at the deleted tombstone location
- If you never saw a deleted tombstone, it inserts at the current, empty, location.

This still means that new-key@ has to orbit around all possible locations that might contain this key, but the cruicial difference is that by reusing deleted slots you don't have to rehash, and you pack data more tightly.