News for hackers. Stuff that matters.

A comment on Bloom Filters: More than a space-efficient hashmap. Parent comment

Re:Bloom Filters: More than a space-efficient hashmap by thomasmg on Wednesday August 11, 2021 @08:09AM (#28141007)
Yes, exactly. Linear probing is often easier and faster. Using buckets also helps (each bucket contains multiple slots), for both cuckoo hashing and linear probing. E.g. the cuckoo filter uses a bucket size of 4. See also https://gankra.github.io/blah/hashbrown-tldr/ for a fast hash table implementation.
[ Parent | on HN ]
Re:Bloom Filters: More than a space-efficient hashmap by masklinn on Wednesday August 11, 2021 @09:03AM (#28141499)
Using hashbrown as evidence in a comment defending linear probing is odd when it specifically notes that it uses quadratic probing.
[ Parent | on HN ]
Re:Bloom Filters: More than a space-efficient hashmap by thomasmg on Wednesday August 11, 2021 @10:01AM (#28142072)
I'm sorry! I thought this implementation uses linear probing. Yes this is not an example of linear probing. But it is much closer to linear probing than to cuckoo hashing (I hope we can agree on this). I also found this blog entry interesting: https://probablydance.com/2017/02/26/i-wrote-the-fastest-has... (of course "fastest" is relative, when it comes to benchmarks)
[ Parent | on HN ]