Readit NewsI keep a slightly modified version of it as a top comment in my main C file in every pico project. Super handy for quick reference and you can annotate it with the actual uses in your project.
https://arxiv.org/pdf/2501.02305#:~:text=If%20both%20buckets...
(the text fragment doesn't seem to work in a PDF, it's the 12th page, first paragraph)
(By the way, the text fragment does works somewhat in Firefox. Not on the first load, but if load it, then focus the URL field and press enter)
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.
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.
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)).
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.
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.
This very much reminds me of the "Distinct Elements in Streams" idea by Chakraborty, Vinodchandran and Meel[2].
[0] https://news.ycombinator.com/item?id=43007860
What is it you don't understand: "method" (a representation) or "decimal" (a number that consists of a whole and a fractional part)?
"Decimal" implies a ten based system, even though it's perfectly fine to say "binary decimal".
Using your own replacement words, it would be clearer to write "A floating point number is a representation of a number with a fractional part".
It also seems like someone at Slack is tasked with driving up engagement, because I get these "Your team is missing you" messages from Slack (only to be find a dead slack community). That might be a sign that they're losing traction?