One Hash Bloom Filters

Yep, thanks. I'll email the author about their bad rel=canonical tag.

I learned the Kirsch and Mitzenmacher trick from Google’s Guava. Interestingly, they also use Murmur-128, but then they just use the first 64 bits of that and split it into the two 32-bit hashes as described in the paper.

I wrote a couple of alternative implementations based on that idea, but using SipHash instead of Murmur IIRC. One as a memory-mapped fast lookup for known-compromised passwords, and another for JWT logout described in these blog posts from 2016 (written to support massive projected usage at the BBC, no idea if they still use it):

https://neilmadden.blog/2016/02/25/stateless-session-logout-in-openam-13/

https://neilmadden.blog/2016/06/06/bloom-filter-session-logout-some-numbers/

The linked paper describes a "Standard Bloom Filter" as using k hash functions and a modulo.

If I was to build a simple Bloom filter:

• Size my bit array to a power of two so I can use a truncation / mask instead of a comparatively expensive modulo. (Obviously less flexible, but if you have a use case where the next lower power of two bit array size has too high a false positive rate and the next larger uses too much memory... your cache sizing is way more precise than anything I've worked on.)
• Shift and mask the output of one hash function to generate my "k" hashes. E.g. the lowest 16 bits are h1, next higher 16 are h2, etc. Can get three 21 bit numbers from a 64 but hash, and if that's not enough, many hash functions can output 128 bits or more for no extra cost. For a good hash function, any positions should be as independent as different hash functions would be.

Perhaps those are mentioned later in the paper or in the references, but weren't in the related work or the beginning of the design section before the math got too dense for me to skim on my phone.

While there might be other e.g. locality benefits to this scheme, making a "one hash Bloom filter" seems trivial. Is there something I'm missing where the simple scheme wouldn't actually work?

I really like this kind of stuff :) The combination of clever maths, cache locality, and concurrency optimisations is fascinating. I'd be curious to see how much of the improvement comes from the one-hash approach itself versus cache-line blocking and reduced contention. A comparison against conventional double-hashed and blocked Bloom filters, at the same memory budget and false-positive rate, would be interesting. Especially with varying filter sizes (inside and beyond L3 cache) and concurrent write loads.