4 ms·

Funnel hashing is greedy.

• abetusk 2y ago
  This seems overly pedantic. Here I think "greedy" means uniform probing. The authors very clearly state "non greedy": https://www.youtube.com/watch?v=ArQNyOU1hyE&t=1087s https://www.youtube.com/watch?v=ArQNyOU1hyE&t=1087s
  • edflsafoiewq 2y ago
    What the author says there is "What we just showed was that we can achieve a worst-case expected probe complexity of log squared one over delta with a greedy algorithm. And we don't have too much time to go over the non-greedy algorithm but...". The funnel hashing described in the video is greedy. The video doesn't cover the non-greedy elastic hashing. "Greedy" means that the search and insertion do the same probe sequence, and insertion just uses the first free slot in that sequence.
    • abetusk 2y ago
      Ah, thanks for the clarification!