FRESH

Hacker News

A new hash table for Lwan

14 points by g0xA52A2A

by teo_zero

0 subcomment

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.

by momojo

0 subcomment

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.