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
  module_function

  # A stable 64-bit integer for any item.
  def to_64_bits(item)
    Digest::SHA256.hexdigest(item.to_s)[0, 16].to_i(16)
  end
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
  bit_count = 32
  bitmap = Array.new(bit_count, false)

  lines = []

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

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

  lines << ""

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

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

  lines.join("\n")
end

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

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

bitmap[15] -> true  (alice was added)
bitmap[26] -> true  (bob was added)
bitmap[23] -> false  (zoe was never added, correctly absent)
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 positions to be on by coincidence from other items, and that’s much harder to achieve by accident.

Say half the bits in your bitmap are on (a fill fraction of 0.5). With one hash, an absent item has a 50% chance of a false positive. With three hashes it needs three independent coin flips to all come up heads: 0.5 × 0.5 × 0.5 = 0.125, or 12.5%. With seven hashes: 0.5**7 ≈ 0.008, under 1%.

The problem is that more hashes means more bits flipped on per item, and that fills a bitmap quickly. Too few hashes wastes the bitmap space, but too many and your false positive rate climbs back up. We’re going to need to tune that to find the correct settings.

Building it

Given we only have the one hashing function we’re going to need to figure something out to get several independent positions per item. Remember, though, that a difference of even one character in the input to a hash function will produce a very different hash, and that’s a property we can take advantage of. By putting a different number in front of items before hashing we get a far nicer scattering of unrelated positions:

class BloomFilter
  attr_reader :bit_count, :hash_count, :bitmap

  def initialize(bit_count:, hash_count:)
    @bit_count = bit_count
    @hash_count = hash_count
    # A row of switches, all off.
    @bitmap = Array.new(bit_count, false)
  end

  # The positions one item is responsible for.
  #
  # Prepending the seed (0, 1, 2, ...) changes the input, so each hash
  # scatters somewhere unrelated. "alice" becomes hash_count positions.
  def positions(item)
    Array.new(@hash_count) do |seed|
      Hashing.to_64_bits("#{seed}:#{item}") % @bit_count
    end
  end

  # Record an item: turn on every bit it is responsible for.
  def add(item)
    positions(item).each { |position| @bitmap[position] = true }
    self
  end

  # Check an item: present only if every one of its bits is on.
  # A single off bit proves it was never added.
  def include?(item)
    positions(item).all? { |position| @bitmap[position] }
  end

  # Combine two filters by OR-ing their bitmaps.
  def merge(other)
    merged = BloomFilter.new(bit_count: @bit_count, hash_count: @hash_count)
    merged.bitmap.each_index { |index| merged.bitmap[index] = @bitmap[index] || other.bitmap[index] }
    merged
  end
end

That’s a Bloom filter, Burton Bloom’s 1970 design. Notice that add only ever turns bits on, never off. That’s what makes the “definitely not present” guarantee work: if a bit is off, nothing has ever touched it.

Note: As with the HyperLogLog post we are explicitly avoiding bit manipulation for early examples. This is intentional, and that version will be covered later.

Watching it work

In practice, given a tiny filter with 32 bits and 3 hashes, here’s what happens feeding in six names. We’ll need a small helper to turn a bitmap into a string of 1s and 0s:

def render(bitmap)
  bitmap.map { |bit| bit ? "1" : "0" }.join
end

Then the experiment itself:

def watch_it_work
  filter = BloomFilter.new(bit_count: 32, hash_count: 3)
  lines = []
  lines << "start                          #{render(filter.bitmap)}"

  %w[alice bob carol dave eve frank].each do |name|
    filter.add(name)
    spots = filter.positions(name).sort
    lines << format("add %-6s spots %-12s  %s", name, spots.inspect, render(filter.bitmap))
  end

  lines.join("\n")
end

Each row shows the three positions that name claimed and the state of all 32 bits afterward:

start                          00000000000000000000000000000000
add alice  spots [0, 27, 31]   10000000000000000000000000010001
add bob    spots [9, 15, 27]   10000000010000010000000000010001
add carol  spots [19, 26, 30]  10000000010000010001000000110011
add dave   spots [8, 20, 30]   10000000110000010001100000110011
add eve    spots [10, 22, 25]  10000000111000010001101001110011
add frank  spots [10, 12, 28]  10000000111010010001101001111011

Watch dave land on position 30, which carol already turned on. Nothing happens, the bit was already 1, and that’s why Bloom filters have false positives.

Now query it for the two names that went in, then for the two that never did:

filter = BloomFilter.new(bit_count: 32, hash_count: 3)
%w[alice bob carol dave eve frank].each { |name| filter.add(name) }

lines = []
lines << "members (each was added):"
%w[alice frank].each do |name|
  result = filter.include?(name)
  positions = filter.positions(name).sort
  lines << format("  include?(%-7s) -> %-5s  bits at %s all on", name, result, positions.inspect)
end

lines << ""
lines << "non-members (never added):"
%w[zoe mallory].each do |name|
  positions = filter.positions(name).sort
  bits_state = positions.map { |pos| filter.bitmap[pos] ? "on" : "off" }
  result = filter.include?(name)
  if result
    lines << format("  include?(%-7s) -> %-5s  bits at %s are %s (all on -> FALSE POSITIVE)", name, result, positions.inspect, bits_state.inspect)
  else
    lines << format("  include?(%-7s) -> %-5s  bits at %s are %s (one off -> absent, for certain)", name, result, positions.inspect, bits_state.inspect)
  end
end

lines.join("\n")

Which produces:

members (each was added):
  include?(alice  ) -> true   bits at [0, 27, 31] all on
  include?(frank  ) -> true   bits at [10, 12, 28] all on

non-members (never added):
  include?(zoe    ) -> true   bits at [9, 20, 30] are ["on", "on", "on"] (all on -> FALSE POSITIVE)
  include?(mallory) -> false  bits at [5, 24, 28] are ["off", "off", "on"] (one off -> absent, for certain)

zoe never went in, but her three positions (9, 20, and 30) are all on from other items: 9 came from bob, 20 from dave, 30 from carol and dave. The filter reports her as present because it has no way to tell whose bits are whose.

mallory has two of her three bits off. Nothing can turn a bit off once it’s on, so if it reads off nobody has ever set it, meaning the item is definitely not in there.

How big, and how many hashes

Up above we mentioned that we’re going to need to fine tune how many bits we need to allocate and how many hashes we need to run to make this efficient. We can derive that like so:

def false_positive_rate(bit_count, item_count, hash_count)
  # Step 1: How many times do we try to turn on a bit?
  #
  # Each item we add flips `hash_count` bits. After adding `item_count`
  # items, we've made this many total attempts to flip bits:
  #
  #   total_flips = hash_count * item_count
  #
  # Step 2: What's the chance a specific bit is still `off`?
  #
  # Each flip picks one of `bit_count` positions. The chance that a
  # single flip MISSES a specific bit is:
  #
  #   miss_one = 1 - (1.0 / bit_count)
  #
  # After `total_flips` independent misses, the chance that specific
  # bit has never been touched is:
  #
  #   still_off = miss_one ** total_flips
  #
  # For large `bit_count` values that simplifies to an exponential decay.
  # Exponential decay means the value shrinks by the same proportion at
  # each step, like how a half-life works: each round of flips has the
  # same chance of missing our bit, and those chances multiply together.
  #
  # Ruby spells this as `Math.exp(x)` which computes e (~2.718) raised
  # to `x`. The approximation gets more accurate as `bit_count` grows.
  # More on exponential decay: https://en.wikipedia.org/wiki/Exponential_decay
  #
  #   still_off ≈ Math.exp(-hash_count * item_count / bit_count)
  #
  # Step 3: What fraction of bits are `on`?
  #
  #   fraction_on = 1 - still_off
  #
  # Step 4: What's the false positive rate?
  #
  # An item we never added gets `hash_count` random positions checked.
  # For a false positive, ALL of them need to be `on`. Each one is `on`
  # with probability `fraction_on`, so:
  #
  #   false_positive_rate ≈ fraction_on ** hash_count

  still_off = Math.exp(-hash_count.to_f * item_count / bit_count)
  (1 - still_off)**hash_count
end

Every added item takes hash_count attempts at turning bits on, and the odds that any given bit is still off shrink as those attempts pile up. For a false positive to happen, an absent item needs every one of its hash_count bits to already be on by coincidence, and that probability drops fast as hash_count grows. The code comments explain why Math.exp works as a stand-in for the exact power (it gets more accurate as bit_count grows).

By keeping the bitmap size and item count constant and manipulating the value of hash_count we notice that the false positive rate drops at first, and then starts climbing. Too few hashes and you’re not using the bitmap effectively, too many and you’re filling it too fast. There’s a sweet spot in the middle where the error is lowest, and that’s where we want to land.

The optimal number of hashes works out to (bit_count / item_count) * log(2), where log(2) is the natural logarithm of 2, about 0.693 (Ruby: Math.log(2)). At 10 bits per item that gives us 10 × 0.693 ≈ 7, so 7 hashes is the best choice.

Let’s give that a try by running an experiment at 10 bits per item, varying the hash count, and testing against fifty thousand absent items. First we need a helper that computes the optimal hash count from the formula above:

def optimal_hashes(bits_per_item)
  (bits_per_item * Math.log(2)).round
end

Then the sweep:

item_count = 50_000
bits_per_item = 10
bit_count = bits_per_item * item_count
predicted = optimal_hashes(bits_per_item)

lines = []
lines << "bits/item = #{bits_per_item}, items = #{item_count}"
lines << "predicted best hash count = #{bits_per_item} * ln(2) = #{"%.2f" % (bits_per_item * Math.log(2))} -> #{predicted}"
lines << ""
lines << " hashes  measured FP"

(1..12).each do |hash_count|
  filter = BloomFilter.new(bit_count: bit_count, hash_count: hash_count)
  item_count.times { |index| filter.add("item-#{index}") }

  false_positives = 0
  test_count = 50_000
  test_count.times { |index| false_positives += 1 if filter.include?("absent-#{index}") }
  rate = false_positives.to_f / test_count * 100

  marker = hash_count == predicted ? "  <- predicted optimum" : ""
  lines << format("   %2d     %6.3f%%%s", hash_count, rate, marker)
end

lines.join("\n")

Results:

bits/item = 10, items = 50000
predicted best hash count = 10 * ln(2) = 6.93 -> 7

 hashes  measured FP
    1      9.714%
    2      3.398%
    3      1.780%
    4      1.220%
    5      0.998%
    6      0.888%
    7      0.838%  <- predicted optimum
    8      0.836%
    9      0.922%
   10      1.058%
   11      1.256%
   12      1.392%

The measured minimum lands at 7 to 8 hashes, which is close to the predicted 6.93. One hash gives you a useless ~9.7% error rate, and past the optimum the rate climbs as the extra bit-sets fill the bitmap.

The next question is sizing: given how many items you expect and the error rate you can live with, how many bits do you need? The formula is -item_count * log(target) / (log(2) ** 2). Breaking that down:

log(target) is the natural logarithm of your desired false positive rate. For a 1% target that’s Math.log(0.01) ≈ -4.6. The minus sign in front cancels the negative, giving a positive bit count.
log(2) ** 2 is Math.log(2) ** 2 ≈ 0.48, a constant from the math behind the optimal hash count.

What’s handy is that the bits-per-item cost is fixed for a given target regardless of how many items you store:

item_count = 50_000
targets = [0.10, 0.01, 0.001]
lines = []

targets.each do |target|
  bits_per_item = -Math.log(target) / (Math.log(2)**2)
  hash_count = optimal_hashes(bits_per_item)
  bit_count = (bits_per_item * item_count).ceil

  filter = BloomFilter.new(bit_count: bit_count, hash_count: hash_count)
  item_count.times { |index| filter.add("item-#{index}") }

  false_positives = 0
  test_count = 50_000
  test_count.times { |index| false_positives += 1 if filter.include?("absent-#{index}") }
  measured = false_positives.to_f / test_count * 100

  lines << format("target %5.1f%%  -> %5.2f bits/item, %d hashes, measured %6.3f%%",
    target * 100, bits_per_item, hash_count, measured)
end

lines.join("\n")

Output:

target  10.0%  ->  4.79 bits/item, 3 hashes, measured 10.092%
target   1.0%  ->  9.59 bits/item, 7 hashes, measured  0.998%
target   0.1%  -> 14.38 bits/item, 10 hashes, measured  0.098%

The cost is constant per item: 1% costs about 9.6 bits each whether you store a thousand items or ten billion. Tightening from 1% to 0.1% costs you roughly five more bits per item.

Memory, in numbers

Great, but why do we care about any of this? We care because here’s the difference on a million stored URLs with a Set versus a Bloom filter at 1%:

item_count = 1_000_000
avg_url_bytes = 80
bits_per_item = 9.59
bloom_bytes = (bits_per_item * item_count / 8.0).ceil

set_mb = (avg_url_bytes * item_count) / 1_000_000.0
bloom_mb = bloom_bytes / 1_000_000.0
ratio = (set_mb / bloom_mb).round

lines = []
lines << "average URL string size: #{avg_url_bytes} bytes"
lines << format("Set of %s URLs:   ~%.1f MB (strings alone, before Set overhead)", "1,000,000", set_mb)
lines << format("Bloom filter (1%%):       ~%.2f MB (%.2f bits/item)", bloom_mb, bits_per_item)
lines << "ratio: Set is ~#{ratio}x larger"
lines.join("\n")

Which gives us:

average URL string size: 80 bytes
Set of 1,000,000 URLs:   ~80.0 MB (strings alone, before Set overhead)
Bloom filter (1%):       ~1.20 MB (9.59 bits/item)
ratio: Set is ~67x larger

That’s a 98.5% improvement on memory for a 1% chance you get a false positive. When you only need to know if something is present or not, that trade is worth taking. The filter doesn’t store the URLs themselves, it stores evidence that something was there. You can’t ask it to list what it’s seen, and you can’t get a URL back out of it. You can only ask “have you seen this one.”

We can test this by inserting a hundred thousand items and asking about all hundred thousand again:

item_count = 100_000
bits_per_item = 9.59
bit_count = (bits_per_item * item_count).ceil
hash_count = 7

filter = BloomFilter.new(bit_count: bit_count, hash_count: hash_count)
item_count.times { |index| filter.add("url-#{index}") }

# Check all members are present
false_negatives = 0
item_count.times { |index| false_negatives += 1 unless filter.include?("url-#{index}") }

# Check false positive rate on non-members
test_count = 100_000
false_positives = 0
test_count.times { |index| false_positives += 1 if filter.include?("absent-#{index}") }
measured = false_positives.to_f / test_count * 100

lines = []
lines << "false negatives: #{false_negatives}"
lines << format("measured FP: %.2f%%   predicted: 1.0%%", measured)
lines.join("\n")

Running it:

false negatives: 0
measured FP: 1.06%   predicted: 1.0%

Zero false negatives, because bits only ever get turned on and never off. The ~1% false positive rate only applies to items that were never added.

Merging filters

Say two machines have each been running their own filter over the URLs they’ve seen, and you want one filter that answers for both. As long as they’re the same size with the same hash count, you combine them by OR-ing the bitmaps position by position: for each position, if either filter has it on, the merged filter has it on. In Ruby that’s || across both arrays (or | if you’re working with packed integers). We added a merge method to BloomFilter above that does exactly this:

bit_count = 10_000
hash_count = 7

east = BloomFilter.new(bit_count: bit_count, hash_count: hash_count)
west = BloomFilter.new(bit_count: bit_count, hash_count: hash_count)

100.times { |index| east.add("east-user-#{index}") }
100.times { |index| west.add("west-user-#{index}") }

both = east.merge(west)

lines = []
lines << "both.include?('east-user-42')  -> #{both.include?("east-user-42")}"
lines << "both.include?('west-user-99')  -> #{both.include?("west-user-99")}"
lines << "both.include?('nobody-here')   -> #{both.include?("nobody-here")}"

east_all = (0...100).all? { |index| both.include?("east-user-#{index}") }
west_all = (0...100).all? { |index| both.include?("west-user-#{index}") }
lines << "all east members present in union? #{east_all}"
lines << "all west members present in union? #{west_all}"
lines.join("\n")

Output:

both.include?('east-user-42')  -> true
both.include?('west-user-99')  -> true
both.include?('nobody-here')   -> false
all east members present in union? true
all west members present in union? true

You still get zero false negatives after merging, and at scale this becomes very useful. You don’t need to ship the data between machines, you ship an observation of it.

You can’t delete

You can add to a Bloom filter, but you can’t remove from one. Turning an item’s bits back off looks reasonable until you remember that multiple items can share the same bit positions.

For example, two names, alice and bob, will overlap on a position:

filter = BloomFilter.new(bit_count: 64, hash_count: 3)
filter.add("alice")
filter.add("bob")

alice_pos = filter.positions("alice").sort
bob_pos = filter.positions("bob").sort
shared = alice_pos & bob_pos

lines = []
lines << "alice sits at #{alice_pos}"
lines << "bob sits at #{bob_pos}"
lines << "they share position #{shared.first}"
lines << ""
lines << "Before deleting alice: include?(bob) -> #{filter.include?("bob")}"

# Simulate deletion by turning off alice's bits
filter.positions("alice").each { |position| filter.bitmap[position] = false }
lines << "After  deleting alice: include?(bob) -> #{filter.include?("bob")}  (bob was never removed)"
lines.join("\n")

Running it:

alice sits at [31, 32, 59]
bob sits at [9, 47, 59]
they share position 59

Before deleting alice: include?(bob) -> true
After  deleting alice: include?(bob) -> false  (bob was never removed)

Clearing alice turned off position 59, which bob was also using. Now the filter reports that bob isn’t there, even though bob was never touched. That’s a false negative, and false negatives are the one error this structure is supposed to make impossible.

If you need removal, you can store a small counter (say, 4 bits) at each position instead of a single bit. Adding increments the counter, removing decrements it. A position reads as on if its counter is above zero. That’s called a counting Bloom filter, and it works, but you’re paying 4 bits per position instead of 1 which quadruples the memory.

Where you’ve already used this

If you’ve run almost any modern database, Bloom filters have been working under you.

Many storage engines (RocksDB, LevelDB, Cassandra, HBase) use something called log-structured merge trees, or LSM trees. Instead of updating records in place on disk (which requires finding and rewriting them), the engine writes new data into a fresh sorted file. These files are called SSTables. Over time you end up with a lot of them, and when you want to look up a key you might have to check several files to find it.

That’s fine for keys that exist, you find them eventually. The expensive case is looking up a key that doesn’t exist, because you have to check every file before you can be sure it’s not there. Each check means reading from disk, and disk reads are slow.

Each SSTable carries a Bloom filter over the keys it contains. Before touching the disk, the engine asks the filter: “might this key be in this file?” If the filter says no, the file is skipped entirely. If it says yes, the engine reads the file.

RocksDB’s filter defaults to 10 bits per key, the same 10-bits-for-1% trade we derived above. Cassandra exposes it directly as a per-table setting called bloom_filter_fp_chance where you choose how much memory to spend in exchange for fewer disk reads.

Making it fast: packed bits and double hashing

The BloomFilter class above works correctly but has two performance problems.

By using arrays and booleans for our bitmap we’re paying a full 8-byte slot per array element to hold one bit of information, a 64x overhead on the raw data. Great for examples and readability, not so great for memory and efficiency if you wanted to use it in production.

On the hashing side, with 7 hashes we’re computing 7 separate SHA-256 digests per add and per include?. SHA-256 is expensive, and in a hot loop that cost adds up.

The fix for the hashing cost is a trick called double hashing, from Kirsch and Mitzenmacher (2006). Instead of computing 7 independent hashes, compute one 64-bit hash and split it into two 32-bit halves: high and low. Then generate as many positions as you want by stepping:

Position 0: (high) % bit_count
Position 1: (high + low) % bit_count
Position 2: (high + 2 * low) % bit_count
Position 3: (high + 3 * low) % bit_count
…and so on

Each position is different because you’re adding low each time, and the paper shows no measurable loss in false positive rate compared to fully independent hashes.

If you’re comfortable with bit manipulation, here’s the optimized version combining both fixes. If not, skip this block, the behavior is the same:

class PackedBloomFilter
  attr_reader :bit_count, :hash_count

  def initialize(bit_count:, hash_count:)
    @bit_count = bit_count
    @hash_count = hash_count
    @words = Array.new((bit_count + 63) / 64, 0)
  end

  def positions(item)
    hash = Hashing.to_64_bits(item)
    high = hash >> 32                 # top 32 bits
    low  = (hash & 0xFFFFFFFF) | 1    # bottom 32 bits, forced odd to spread well
    Array.new(@hash_count) { |nth| (high + nth * low) % @bit_count }
  end

  def add(item)
    positions(item).each do |position|
      @words[position >> 6] |= (1 << (position & 63))
    end
    self
  end

  def include?(item)
    positions(item).all? do |position|
      @words[position >> 6][position & 63] == 1
    end
  end
end

Breaking down the bit operations:

position >> 6 divides by 64 (since 2**6 = 64) to pick which integer in the array holds our bit
position & 63 gives the remainder (0-63) to pick which bit within that integer
|= (1 << (position & 63)) sets that specific bit to on without touching any other bits in the integer
integer[position & 63] in Ruby reads that single bit back as 0 or 1

Running the same hundred-thousand-item test through it:

PackedBloomFilter (double hashing), same settings:
  false negatives: 0
  measured FP: 1.00%   predicted: 1.0%

Same 0 false negatives, same roughly 1% false positive rate. One hash call instead of seven, bits packed into integers instead of individual objects, and a good deal faster:

def benchmark_filters
  require "benchmark/ips"

  item_count = 100_000
  bits_per_item = 9.59
  bit_count = (bits_per_item * item_count).ceil
  hash_count = 7

  readable = BloomFilter.new(bit_count: bit_count, hash_count: hash_count)
  packed = PackedBloomFilter.new(bit_count: bit_count, hash_count: hash_count)

  items = Array.new(item_count) { |index| "item-#{index}" }
  items.each { |item| readable.add(item); packed.add(item) }

  queries = Array.new(item_count) { |index| "query-#{index}" }

  Benchmark.ips do |bench|
    bench.report("BloomFilter#add") { readable.add(queries.sample) }
    bench.report("PackedBloomFilter#add") { packed.add(queries.sample) }
    bench.compare!
  end

  Benchmark.ips do |bench|
    bench.report("BloomFilter#include?") { readable.include?(queries.sample) }
    bench.report("PackedBloomFilter#include?") { packed.include?(queries.sample) }
    bench.compare!
  end
end

Which results in:

ruby 4.0.6 (2026-07-14 revision 03b6d3f889) +PRISM [arm64-darwin25]
Apple M4 Max

Warming up --------------------------------------
      BloomFilter#add    23.845k i/100ms
PackedBloomFilter#add    62.981k i/100ms
Calculating -------------------------------------
      BloomFilter#add    236.136k (± 1.1%) i/s    (4.23 μs/i) -      1.192M in   5.048990s
PackedBloomFilter#add    619.990k (± 1.9%) i/s    (1.61 μs/i) -      3.149M in   5.079192s

Comparison:
PackedBloomFilter#add:   619990.3 i/s
      BloomFilter#add:   236136.3 i/s - 2.63x  slower

Warming up --------------------------------------
      BloomFilter#include?    21.571k i/100ms
PackedBloomFilter#include?    69.599k i/100ms
Calculating -------------------------------------
      BloomFilter#include?    208.994k (± 1.8%) i/s    (4.78 μs/i) -      1.057M in   5.057458s
PackedBloomFilter#include?    676.427k (± 2.3%) i/s    (1.48 μs/i) -      3.410M in   5.041711s

Comparison:
PackedBloomFilter#include?:   676427.3 i/s
      BloomFilter#include?:   208994.1 i/s - 3.24x  slower

About 2.6x faster on inserts and 3.2x faster on lookups, primarily from avoiding 6 extra SHA-256 calls per operation and packing 64 bits per integer instead of one bit per array slot. Both sides pay the same queries.sample overhead so the relative difference is what matters.

Wrapping up

Bloom filters make it cheap to ask whether or not you’ve seen something. It’s always right when it says something isn’t there, but might be wrong when it says something is, at a false positive rate we can tune to an acceptable level. For large datasets this can be a great trade to make, but before we make those trades we should understand what we gain and what we lose, much as we would with any architectural decision.

Probabilistic algorithms are another tool we can use, they have a time and a place, and for a lot of problems I find myself in nowadays that time is now and that place is right here. Perhaps it’s different for you, but knowing these ideas exist is valuable too for when you do find such problems.

Where do we go from here? Well, we’ve covered how to count distinct items with HyperLogLog and membership with Bloom filters, but what if we wanted to figure out how many times we’ve seen a specific item? That’s Count-Min Sketch, and it’s next on my list to cover.