Hacker News new | past | comments | ask | show | jobs | submit login

Funnel hashing is greedy.





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


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.


Ah, thanks for the clarification!



Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: