A new hash table for Lwan

tia.mat.br

14 points·g0xA52A2A··4 comments

Hash tables are one of those miraculous data structures that, once grokked, take you up a step-function in understanding modern computer science. I'm not talking about the 2018 leetcode meme of "Just solve everything in a hash table". It's more about Array chapter in CS1 where you're told "...and therefore, can retrieval ever go below O(N), or O(logN) if sorted?" and you sit there scratching your head, assuming thats reality and then BAM, the professor reveals hash tables and O(C) retrieval and drops the mic.

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.

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.

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.

Reply on news.ycombinator.com