Re:Bloom Filters: More than a space-efficient hashmap
by giveexamples on Wednesday August 11, 2021 @05:51AM
(#28140048)
It's worth knowing that you don't need to generate N hashes - you can use https://en.wikipedia.org/wiki/Double_hashing to generate all N hashes from just 2 hashes.
[ Parent
| on HN ]
Re:Bloom Filters: More than a space-efficient hashmap
by thomasmg on Wednesday August 11, 2021 @07:58AM
(#28140902)
Yes exactly. Actually you just need one 64-bit hash to generate all the hashes needed by the Bloom filter. And the somewhat slow modulo operation can be replaced with multiply+shift (fastRange). See e.g. https://github.com/FastFilter/fastfilter_cpp/blob/master/src...
for (int i = 0; i < k; i++) { data[fastRange(a, data.length)] |= getBit(a); a += b; }