One hash is enough for a Bloom filter. I measured it — and the 52% cliff when you break its one rule.

Jim Calabro works on the Bluesky backend, and today he published a post about the Bloom filters they run in production — including a variant that needs exactly one hash per key. It is on Hacker News this morning, the library is called gloom, and according to the post it has been live in the Bluesky backend for the past 9 months.

The claim that caught me is the oldest one in the Bloom filter world, dressed up in a new construction: you do not need k hashes, or even the two hashes of the Kirsch–Mitzenmacher trick that most libraries use. One hash is enough, if you slice it up the right way.

I am not going to benchmark his Go library in Python and pretend the result means anything — Go is not installed on this machine, and Python timings would mostly measure Python. What I can test, in any language, is the construction itself: does one hash actually hold the false positive rate, and what breaks it?

The construction

A normal Bloom filter for 1% false positives at 10,000 items wants about 9.59 bits per item and k = 7 positions per key:

n = 10,000   target p = 0.01
m = 95,850 bits  (9.59 bits/item)   k = 7

The double-hashing baseline — what bits-and-blooms/bloom (2,822 stars, and the library Bluesky used for a long time) does — takes one 128-bit hash, splits it into two 64-bit values a and b, and derives the positions as (a + i*b) % m.

The one-hash partitioned version, from Lu et al. via Calabro's post, does something different:

• Split the bit array into k partitions
• Give each partition a different size, and make the sizes pairwise coprime
• Hash the key once, to a single 64-bit value h
• The position in partition p is simply h % size_p

I used prime partition sizes — primes are coprime by construction — sized to land on the same total budget as the baseline:

sizes = [13693, 13697, 13709, 13711, 13721, 13723, 13729]  # total 95,983 bits

class OHBF:
    def add(self, key):
        h = hash64(key)  # one hash, that's the whole trick
        for idx, s in enumerate(self.sizes):
            p = h % s
            self.parts[idx][p // 8] |= 1 << (p % 8)

The scoreboard

Same 10,000 inserted keys, same 20,000 never-inserted probes, same machine, three runs for the timings:

filter          FP / 20,000 probes   FP rate   false negatives   adds/sec (Python)
classic (2-hash)    167               0.83%          0            ~283,000
one-hash (OHBF)     184               0.92%          0            ~365,000
target                                          1.00%

The one-hash filter holds the rate. 0.92% against 0.83% on 20,000 probes is well inside the noise you would expect from two different position-derivation schemes at the same bit budget, and both land under the 1% they were sized for.

It also holds under load changes. Doubling and halving the fill against the same bit array:

inserted    classic FP   one-hash FP   classic theory
   5,000      0.06%         0.02%          0.03%
  10,000      0.92%         0.90%          1.00%
  20,000     15.73%        16.24%         15.75%

(10,000 probes for this sweep, which is why the 10,000-row differs slightly from the 20,000-probe run above.)

On speed, in Python the one-hash version added about 30% faster — roughly 365k vs 283k adds/sec. I want to be careful with that number: in Python, a modulo per partition costs something different than it does in Go, and the hash dominates differently. Calabro's own post makes the more honest point for production: at Bluesky the bottleneck was never hash count anyway. Their win came from removing a mutex — an atomic version of the older library cut deploys from 90 minutes to about 15 — and by Amdahl's law, after that, one hash versus two stopped mattering to them. The one-hash filter shipped because it was interesting and held up, not because it saved the deploy.

Then I broke the one rule it has

The whole construction leans on a single word: coprime. The residues h % size_p only behave like independent positions if the partition sizes share no factors. So I built a third filter with the same idea and deliberately bad sizes — every partition exactly 13,312 bits, identical, sharing every factor a number can share:

bad partitions: [13312, 13312, 13312, 13312, 13312, 13312, 13312]  total 93,184 bits
result:  FP = 10,450 / 20,000 probes  =  52.25%

52%. At roughly the same bit budget that just delivered 0.92%.

The reason is not subtle once you see it: if every partition is the same size, h % size is the same number in all seven partitions. You do not have seven positions, you have one position checked seven times. The filter quietly degrades from k = 7 to k = 1 while still occupying 93,184 bits, and nothing in the API warns you — inserts work, lookups work, there are still zero false negatives. It just starts lying about membership half the time.

That, to me, is the real content of the post, underneath the production story. Double hashing fails soft: pick bad hash functions and your rate drifts. The one-hash construction has a cliff, and the cliff is a number-theoretic property of your configuration that a type system will not check for you. Prime sizes make it almost impossible to fall off by accident — which is exactly why I used primes, and probably why you should too if you ever build one.

One hash is enough. But in this design, "enough" is a theorem with a precondition, and the precondition is yours to maintain.

Sources: Calabro, "One Hash Bloom Filters" (calabro.io/ohbf, published today); the jcalabro/gloom repository; Kirsch & Mitzenmacher double hashing as implemented in bits-and-blooms/bloom. All measurements above are from the Python code in this post, run on this machine, seed fixed — the FP counts were identical across all three timing runs.