Beyond Enumerable: Testing Membership with Bloom Filters | baweaver

baweaver

baweaver

Software Engineering

Simplicity is hard work. But there's a huge payoff. The person who has a genuinely simpler system is going to be able to affect the greatest change with the least work.<br>— Rich Hickey

ruby<br>July 20, 2026<br>22 min read

Beyond Enumerable: Testing Membership with Bloom Filters

Let’s say you need to keep track of which URLs you’ve visited, how might you approach that in Ruby? The most naive answer might be an Array, but that costs O(n) to search. After that you get a hold of Set which gives you an O(1) lookup, much better, but what do you suppose happens if you need to track billions of URLs? You end up paying in RAM, approximately 80 GB of it, and that’s a pretty steep cost to pay.

What if we didn’t have to pay it? What if we could get close enough at a fraction of that cost?

That’s where we start to see Bloom filters coming in. Take those same billion URLs we were tracking at 80 GB and a Bloom filter can cut it down to 1.2 GB, but there is a catch: It can tell you with certainty that something is not present, but it might be wrong about whether something is present, and with only a 1% false positive rate when done right.

That means you’re trading 1% correctness for substantially cheaper RAM costs, and in today’s market that’s becoming a very enticing trade to make.

Quick hashing refresher

How does it work? Similar to the last post we’re using hashing, a function that takes any input and produces a fixed-size number without a discernible pattern. The same input always gives the same output, but even a single character’s difference produces a wildly different hash. The function we’re using:

module Hashing<br>module_function

# A stable 64-bit integer for any item.<br>def to_64_bits(item)<br>Digest::SHA256.hexdigest(item.to_s)[0, 16].to_i(16)<br>end<br>end

One bit per item

Imagine with me a wall of light switches, all of them starting as off. To record an item in our filter we would hash it, and then flip one switch on according to its hash result. If we want to know if something is present we check to see if a switch related to its hash is on.

You may recognize this pattern as a bitmap from the previous HyperLogLog post, but in this case we’re asking a different question. We’re using it to try and figure out if something was there by looking for an on switch where it should be:

def one_bit_example<br>bit_count = 32<br>bitmap = Array.new(bit_count, false)

lines = []

# Record "alice"<br>alice_pos = Hashing.to_64_bits("alice") % bit_count<br>bitmap[alice_pos] = true<br>lines "hash(alice) % #{bit_count} = #{alice_pos} -> bitmap[#{alice_pos}] = true"

# Record "bob"<br>bob_pos = Hashing.to_64_bits("bob") % bit_count<br>bitmap[bob_pos] = true<br>lines "hash(bob) % #{bit_count} = #{bob_pos} -> bitmap[#{bob_pos}] = true"

lines ""

# Check membership<br>lines "bitmap[#{alice_pos}] -> #{bitmap[alice_pos]} (alice was added)"<br>lines "bitmap[#{bob_pos}] -> #{bitmap[bob_pos]} (bob was added)"

# Check something not added<br>zoe_pos = Hashing.to_64_bits("zoe") % bit_count<br>lines "bitmap[#{zoe_pos}] -> #{bitmap[zoe_pos]} (zoe was never added, #{bitmap[zoe_pos] ? "FALSE POSITIVE" : "correctly absent"})"

mallory_pos = Hashing.to_64_bits("mallory") % bit_count<br>lines "bitmap[#{mallory_pos}] -> #{bitmap[mallory_pos]} (mallory was never added, #{bitmap[mallory_pos] ? "FALSE POSITIVE" : "correctly absent"})"

lines.join("\n")<br>end

Run it with a 32-bit bitmap and a few names:

hash(alice) % 32 = 15 -> bitmap[15] = true<br>hash(bob) % 32 = 26 -> bitmap[26] = true

bitmap[15] -> true (alice was added)<br>bitmap[26] -> true (bob was added)<br>bitmap[23] -> false (zoe was never added, correctly absent)<br>bitmap[25] -> false (mallory was never added, correctly absent)

That said, you might notice a problem here: two items could very well hash to the same bit position. If zoe had happened to land on position 15 or 26 instead of 23, she’d read as present even though she never went in. That’s a false positive: the filter says yes about something you never put in. In this case zoe’s bit is off, meaning she’s definitely not present.

The reason that a Bloom filter works is that the filter can be wrong occasionally, but only in one direction, meaning the other direction can be used as a source of truth. A yes means “probably, but you should check” and a no means “it’s not there.” That “no” can let you skip expensive operations, and the rare wrong yes only costs you a lookup you’d have done anyways.

Pushing the error down

Much like HyperLogLog a single-hash-per-item bitmap will end up with a lot of collisions, rendering it useless at scale, so we stop using one bit and start using several.

Instead of hashing an item to one position, hash it to several positions using different hash functions. When you add an item, turn all of those positions on. When you check if an item is present, require that every single one of its positions is on. A false positive now needs all of those...