[teo_zero]

Mmm... so when looking for a non-existent key you have to go through the whole table. Hardly O(1)!

A better strategy would be to first search the given range for the first empty slot, and exclude everything after that point. Then proceed looking for tophash in the thus-limited interval. The return value has 3 possible values: 1) key found, 2) reached end of interval without finding but it might be in the other half, 3) found an empty slot so the key is not present, not even in the second half.

[acidx]

If I understood this comment correctly, this approach wouldn't work with a single possible tombstone value.

If the table has, for instance, a tophashes array that looks something like VVVVVVdVVVV, where "V" is any value, and "d" is a deleted item, you can't stop looking after the "d" value -- as your item might be there.

[teo_zero]

A tombstone must be distinct from an empty element. In your example, you wouldn't stop at "d" because you haven't found an empty yet.