Bloom Filter

from __future__ import annotations
​
import hashlib
import math
​
​
class BloomFilter:
    """Probabilistic set-membership structure backed by a bit array and k
    independent hash functions (simulated via double hashing from two base
    hashes). Space-efficient, no false negatives, tunable false positive
    rate. `might_contain()` answers "definitely not present" (False) or
    "maybe present" (True) -- never "definitely present."
    """
​
    def __init__(self, n: int, p: float) -> None:
        """Size a filter for `n` expected elements at target false positive
        rate `p` (e.g. 0.01 for 1%)."""
        self.m: int = self._optimal_m(n, p)
        self.k: int = self._optimal_k(self.m, n)
        self.bits = bytearray((self.m + 7) // 8)  # 1 bit per slot, packed into bytes
​
    @staticmethod
    def _optimal_m(n: int, p: float) -> int:
        """Number of bits needed: m = -(n * ln(p)) / (ln(2)^2)"""
        m = -1 * n * math.log(p) / (math.log(2) ** 2)
        return math.ceil(m)
​
    @staticmethod
    def _optimal_k(m: int, n: int) -> int:
        """Ideal number of hash functions: k = (m/n) * ln(2)"""
        k = (m / n) * math.log(2)
        return max(1, round(k))
​
    @staticmethod
    def _hashes(data: bytes) -> tuple[int, int]:
        """Two independent base hashes of `data`. All k hash functions are
        derived from these via double hashing (Kirsch-Mitzenmacher), avoiding
        the need for k separate hash implementations. Two different digest
        algorithms stand in as the independent bases here to keep this
        dependency-free -- in a production system, prefer
        `mmh3.hash64(data, seed=0)` / `mmh3.hash64(data, seed=1)`
        (MurmurHash3), which is faster and just as well-distributed."""
        h1 = int.from_bytes(hashlib.md5(data, usedforsecurity=False).digest()[:8], "big")
        h2 = int.from_bytes(hashlib.sha1(data, usedforsecurity=False).digest()[:8], "big")
        return h1, h2
​
    def _combine(self, h1: int, h2: int, i: int) -> int:
        """Double hashing: hash_i(x) = h1(x) + i*h2(x)"""
        return h1 + i * h2
​
    def _set_bit(self, pos: int) -> None:
        byte_index, bit_index = divmod(pos, 8)
        self.bits[byte_index] |= 1 << bit_index
​
    def _get_bit(self, pos: int) -> bool:
        byte_index, bit_index = divmod(pos, 8)
        return bool(self.bits[byte_index] & (1 << bit_index))
​
    def add(self, data: bytes) -> None:
        """Insert an element into the filter."""
        h1, h2 = self._hashes(data)
        for i in range(self.k):
            pos = self._combine(h1, h2, i) % self.m
            self._set_bit(pos)
​
    def might_contain(self, data: bytes) -> bool:
        """Return whether `data` may be in the set. False means definitely
        not present. True means present with probability (1 - false positive
        rate) -- it might be a false positive."""
        h1, h2 = self._hashes(data)
        for i in range(self.k):
            pos = self._combine(h1, h2, i) % self.m
            if not self._get_bit(pos):
                return False
        return True
​
    def estimated_false_positive_rate(self, n: int) -> float:
        """Theoretical false positive rate given m, k, and how many elements
        n have actually been inserted so far (tracked externally by the
        caller -- the filter itself doesn't count insertions, since duplicate
        add() calls don't increase the "true" n)."""
        exp = -self.k * n / self.m
        return (1 - math.exp(exp)) ** self.k

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;
​
/**
 * Probabilistic set-membership structure backed by a bit array and k
 * independent hash functions (simulated via double hashing from two base
 * hashes). Space-efficient, no false negatives, tunable false positive
 * rate. mightContain() answers "definitely not present" (false) or "maybe
 * present" (true) -- never "definitely present."
 */
public class BloomFilter {
    private final BitSet bits;
    private final int m; // number of bits
    private final int k; // number of hash functions
​
    /** Size a filter for n expected elements at target false positive rate p (e.g. 0.01 for 1%). */
    public BloomFilter(int n, double p) {
        this.m = optimalM(n, p);
        this.k = optimalK(m, n);
        this.bits = new BitSet(m);
    }
​
    /** Bits needed: m = -(n * ln(p)) / (ln(2)^2) */
    private static int optimalM(int n, double p) {
        double m = -1.0 * n * Math.log(p) / (Math.log(2) * Math.log(2));
        return (int) Math.ceil(m);
    }
​
    /** Ideal number of hash functions: k = (m/n) * ln(2) */
    private static int optimalK(int m, int n) {
        double k = ((double) m / n) * Math.log(2);
        return Math.max(1, (int) Math.round(k));
    }
​
    /**
     * Two independent base hashes of data. All k hash functions are derived
     * from these via double hashing (Kirsch-Mitzenmacher), avoiding the need
     * for k separate hash implementations. MD5 and SHA-1 stand in as the
     * independent bases here to keep this dependency-free -- in a production
     * system, prefer a faster non-cryptographic hash (e.g. Guava's
     * Hashing.murmur3_128() with two seeds).
     */
    private static long[] hashes(byte[] data) {
        try {
            MessageDigest md5 = MessageDigest.getInstance("MD5");
            MessageDigest sha1 = MessageDigest.getInstance("SHA-1");
            long h1 = firstEightBytesAsLong(md5.digest(data));
            long h2 = firstEightBytesAsLong(sha1.digest(data));
            return new long[]{h1, h2};
        } catch (NoSuchAlgorithmException e) {
            throw new IllegalStateException(e); // MD5/SHA-1 are guaranteed on every JVM
        }
    }
​
    private static long firstEightBytesAsLong(byte[] digest) {
        long value = 0;
        for (int i = 0; i < 8; i++) {
            value = (value << 8) | (digest[i] & 0xFF);
        }
        return value;
    }
​
    /** Double hashing: hash_i(x) = h1(x) + i*h2(x), unsigned mod m. */
    private long combine(long h1, long h2, int i) {
        return Long.remainderUnsigned(h1 + (long) i * h2, m);
    }
​
    /** Insert an element into the filter. */
    public void add(byte[] data) {
        long[] h = hashes(data);
        for (int i = 0; i < k; i++) {
            bits.set((int) combine(h[0], h[1], i));
        }
    }
​
    /**
     * Returns whether data may be in the set. False means definitely not
     * present. True means present with probability (1 - false positive
     * rate) -- it might be a false positive.
     */
    public boolean mightContain(byte[] data) {
        long[] h = hashes(data);
        for (int i = 0; i < k; i++) {
            if (!bits.get((int) combine(h[0], h[1], i))) {
                return false;
            }
        }
        return true;
    }
​
    /**
     * Theoretical false positive rate given m, k, and how many elements n
     * have actually been inserted so far (tracked externally by the caller,
     * since the filter itself doesn't count insertions -- duplicate add()
     * calls don't increase the "true" n).
     */
    public double estimatedFalsePositiveRate(int n) {
        double exp = -1.0 * k * n / m;
        return Math.pow(1 - Math.exp(exp), k);
    }
}

from bloom import BloomFilter
​
​
def test_no_false_negatives():
    f = BloomFilter(1000, 0.01)
​
    inserted = [b"apple", b"banana", b"cherry", b"date", b"elderberry"]
    for item in inserted:
        f.add(item)
​
    for item in inserted:
        assert f.might_contain(item), (
            f"false negative for {item!r} -- Bloom filters must never do this"
        )
​
​
def test_definitely_absent():
    f = BloomFilter(1000, 0.01)
    f.add(b"present")
​
    # Not a guarantee for every unrelated string (false positives are
    # possible), but a filter sized for 1000 elements at 1% FP rate with
    # only 1 element inserted should reject almost everything.
    false_positives = 0
    trials = 1000
    for i in range(trials):
        key = bytes([i & 0xFF, (i >> 8) & 0xFF])
        if f.might_contain(key):
            false_positives += 1
    # Sanity bound -- should be well under the target rate given only 1
    # real insertion, not a tight statistical assertion.
    assert false_positives <= trials / 10, (
        f"false positive rate too high: {false_positives}/{trials}"
    )
​
​
def test_false_positive_rate_near_target():
    n = 10_000
    target_p = 0.01
    f = BloomFilter(n, target_p)
​
    for i in range(n):
        f.add(bytes([i & 0xFF, (i >> 8) & 0xFF, (i >> 16) & 0xFF]))
​
    # Test with keys guaranteed not to have been inserted.
    false_positives = 0
    trials = 10_000
    for i in range(trials):
        key = bytes([i & 0xFF, (i >> 8) & 0xFF, (i >> 16) & 0xFF, 0xFF])  # distinct namespace
        if f.might_contain(key):
            false_positives += 1
​
    observed_rate = false_positives / trials
    print(f"observed FP rate: {observed_rate:.4f}, target: {target_p:.4f}")
    # Allow generous margin -- this is a probabilistic structure.
    assert observed_rate <= target_p * 3, (
        f"observed FP rate {observed_rate:.4f} far exceeds target {target_p:.4f}"
    )

import java.nio.charset.StandardCharsets;
import java.util.BitSet;
​
/** Tests for the Bloom filter. */
public class BloomFilterTest {
    public static void main(String[] args) {
        testNoFalseNegatives();
        testDefinitelyAbsent();
        testFalsePositiveRateNearTarget();
        testStepperWalkthroughBitPositions();
        System.out.println("ALL TESTS PASSED");
    }
​
    static void testNoFalseNegatives() {
        BloomFilter f = new BloomFilter(1000, 0.01);
​
        String[] inserted = {"apple", "banana", "cherry", "date", "elderberry"};
        for (String s : inserted) {
            f.add(s.getBytes(StandardCharsets.UTF_8));
        }
​
        for (String s : inserted) {
            assertTrue(
                f.mightContain(s.getBytes(StandardCharsets.UTF_8)),
                "false negative for \"" + s + "\" -- Bloom filters must never do this"
            );
        }
        System.out.println("PASS testNoFalseNegatives");
    }
​
    static void testDefinitelyAbsent() {
        BloomFilter f = new BloomFilter(1000, 0.01);
        f.add("present".getBytes(StandardCharsets.UTF_8));
​
        // Not a guarantee for every unrelated string (false positives are
        // possible), but a filter sized for 1000 elements at 1% FP rate with
        // only 1 element inserted should reject almost everything.
        int falsePositives = 0;
        int trials = 1000;
        for (int i = 0; i < trials; i++) {
            byte[] key = {(byte) i, (byte) (i >> 8)};
            if (f.mightContain(key)) {
                falsePositives++;
            }
        }
        // Sanity bound -- should be well under the target rate given only 1
        // real insertion, not a tight statistical assertion.
        assertTrue(
            falsePositives <= trials / 10,
            "false positive rate too high: " + falsePositives + "/" + trials
        );
        System.out.println("PASS testDefinitelyAbsent");
    }
​
    static void testFalsePositiveRateNearTarget() {
        int n = 10_000;
        double targetP = 0.01;
        BloomFilter f = new BloomFilter(n, targetP);
​
        for (int i = 0; i < n; i++) {
            byte[] key = {(byte) i, (byte) (i >> 8), (byte) (i >> 16)};
            f.add(key);
        }
​
        // Test with keys guaranteed not to have been inserted.
        int falsePositives = 0;
        int trials = 10_000;
        for (int i = 0; i < trials; i++) {
            byte[] key = {(byte) i, (byte) (i >> 8), (byte) (i >> 16), (byte) 0xFF}; // distinct namespace
            if (f.mightContain(key)) {
                falsePositives++;
            }
        }
​
        double observedRate = (double) falsePositives / trials;
        System.out.printf("observed FP rate: %.4f, target: %.4f%n", observedRate, targetP);
        // Allow generous margin -- this is a probabilistic structure.
        assertTrue(
            observedRate <= targetP * 3,
            "observed FP rate " + observedRate + " far exceeds target " + targetP
        );
        System.out.println("PASS testFalsePositiveRateNearTarget");
    }
​
    /**
     * Reproduces the exact m=16, k=3 walkthrough from the guide's stepper:
     * insert "cat" (bits 2,5,9), "dog" (bits 1,5,14), "fox" (bits 9,12,15),
     * then confirm "bird" (never inserted) reads back as a false positive
     * because its own 3 positions (1,9,12) were each set by a different
     * earlier item. This exercises the same set/get-bit mechanics as
     * BloomFilter.add()/mightContain() with the walkthrough's fixed
     * positions standing in for real hash output, since the guide picks
     * those positions for illustration rather than pulling them from any
     * one language's live hash function.
     */
    static void testStepperWalkthroughBitPositions() {
        BitSet bits = new BitSet(16);
​
        for (int pos : new int[]{2, 5, 9}) { // insert "cat"
            bits.set(pos);
        }
        assertTrue(bitsEqual(bits, 2, 5, 9), "unexpected bit state after inserting cat");
​
        for (int pos : new int[]{1, 5, 14}) { // insert "dog" -- bit 5 overlaps with cat
            bits.set(pos);
        }
        assertTrue(bitsEqual(bits, 1, 2, 5, 9, 14), "unexpected bit state after inserting dog");
​
        for (int pos : new int[]{9, 12, 15}) { // insert "fox" -- bit 9 overlaps with cat
            bits.set(pos);
        }
        assertTrue(bitsEqual(bits, 1, 2, 5, 9, 12, 14, 15), "unexpected bit state after inserting fox");
​
        // "bird" was never inserted, but its 3 hash positions each happen to
        // already be set by a different earlier item -- a false positive.
        boolean falsePositive = true;
        for (int pos : new int[]{1, 9, 12}) {
            falsePositive &= bits.get(pos);
        }
        assertTrue(
            falsePositive,
            "expected \"bird\" to read as a false positive, matching the guide's walkthrough"
        );
        System.out.println("PASS testStepperWalkthroughBitPositions");
    }
​
    static boolean bitsEqual(BitSet bits, int... expectedSetPositions) {
        BitSet expected = new BitSet(16);
        for (int pos : expectedSetPositions) {
            expected.set(pos);
        }
        return bits.equals(expected);
    }
​
    static void assertTrue(boolean cond, String msg) {
        if (!cond) {
            throw new AssertionError(msg);
        }
    }
}