3 ms·
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 f
by teo_zero 5mo ago
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 5mo agoIf 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 5mo agoA 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.