Ok, big shout out to monort [0] for the link to the video [1].<p>This is just a quick overview from a single viewing of the video, but it's called "funnel hashing". The idea is to split into exponentially smaller sub arrays, so the first chunk is n/m, the second is n/(m^2), etc. until you get down to a single element. Call them A0, A1, etc., so |A0| = n/m, |A1| = n/(m^2) etc., k levels in total.<p>Try inserting into A0 c times. If it fails, try inserting into A1 c times. If it fails, go down the "funnel" until you find a free slot.<p>Call \delta the fraction of slots that are empty (I'm unclear if this is a parameter that gets set at hash table creation or one that's dynamically updated). Setting c = log(1/d) and k = log(1/d) to get worst case complexity O(log^2(1/d)).<p>This circumvents Yao's result by not being greedy. Yao's result holds true for greedy insertion and search policies and the above is non-greedy, as it's cascading down the funnels.<p>There are probably many little hairy details to work out but that's the idea, as far as I've been able to understand it. People should let me know if I'm way off base.<p>This very much reminds me of the "Distinct Elements in Streams" idea by Chakraborty, Vinodchandran and Meel[2].<p>[0] <a href="https://news.ycombinator.com/item?id=43007860">https://news.ycombinator.com/item?id=43007860</a><p>[1] <a href="https://www.youtube.com/watch?v=ArQNyOU1hyE" rel="nofollow">https://www.youtube.com/watch?v=ArQNyOU1hyE</a><p>[2] <a href="https://arxiv.org/pdf/2301.10191" rel="nofollow">https://arxiv.org/pdf/2301.10191</a>