BloomFilter.java

import java.util.BitSet;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
import java.util.function.ToIntFunction;

/**
 * A <b>Bloom filter</b> — a probabilistic set that is extremely space-efficient
 * but allows a small chance of false positives. False negatives are impossible:
 * if the filter says "no", the element was definitely never added.
 * <p>
 * This makes Bloom filters ideal for situations where you need to quickly reject
 * definite non-members (spell checkers, network routers, database query planners)
 * and can tolerate the occasional false alarm that gets verified by a slower
 * exact lookup.
 *
 * <h3>How it works</h3>
 * The filter maintains a bit array of {@code m} bits, all initially zero, and
 * {@code k} independent hash functions. To <b>add</b> an element, compute all
 * {@code k} hashes and set those bit positions to 1. To <b>query</b>, compute
 * the same {@code k} hashes and check whether all those bits are 1. If any bit
 * is 0, the element was definitely never added. If all are 1, the element is
 * <em>probably</em> present — but those bits might have been set by other elements.
 *
 * <h3>Theoretical false positive rate</h3>
 * After inserting {@code n} elements, the probability of a false positive is
 * approximately {@code (1 - e^(-kn/m))^k}. The optimal number of hash functions
 * for a given {@code m/n} ratio is {@code k = (m/n) * ln(2) ≈ 0.693 * m/n}.
 *
 * <h3>Implementation notes</h3>
 * <ul>
 *   <li>Uses {@link BitSet} instead of {@code boolean[]} — 8× more space-efficient,
 *       since each boolean in an array occupies a full byte.</li>
 *   <li>Hash functions use the form {@code h_i(x) = (a_i * x + b_i) >>> 1 % m},
 *       with unsigned shift to avoid the {@code Math.abs(Integer.MIN_VALUE)} bug
 *       that plagues many Bloom filter implementations.</li>
 *   <li>Accepts a {@link ToIntFunction} instead of {@code Function<E, Integer>}
 *       to avoid autoboxing overhead on every hash computation.</li>
 * </ul>
 *
 * @param <E> the element type
 * @author Ilkka Kokkarinen
 */
public class BloomFilter<E> {

    private final BitSet bits;
    private final int bitCount;             // m — number of bits
    private final int[] hashMultipliers;    // a_i coefficients
    private final int[] hashOffsets;        // b_i coefficients
    private final ToIntFunction<E> toInt;   // element → int conversion
    private int elementCount;               // n — elements added so far

    // -----------------------------------------------------------------------
    // Construction
    // -----------------------------------------------------------------------

    /**
     * Create a Bloom filter with {@code k} hash functions and {@code m} bits.
     *
     * @param hashFunctionCount the number of hash functions (k)
     * @param bitCount          the number of bits in the filter (m)
     * @param toInt             converts an element to an int for hashing;
     *                          if null, {@code Object.hashCode()} is used
     */
    public BloomFilter(int hashFunctionCount, int bitCount, ToIntFunction<E> toInt) {
        this.bitCount = bitCount;
        this.bits = new BitSet(bitCount);
        this.toInt = toInt;
        this.elementCount = 0;

        // Initialize the hash function family h_i(x) = a_i * x + b_i.
        // We use a seeded Random for reproducible behavior in tests.
        var rng = new Random(12345);
        hashMultipliers = new int[hashFunctionCount];
        hashOffsets = new int[hashFunctionCount];
        for (int i = 0; i < hashFunctionCount; i++) {
            // Odd multipliers guarantee they are coprime with any power-of-two
            // table size, giving better bit dispersion.
            hashMultipliers[i] = rng.nextInt() | 1;
            hashOffsets[i] = rng.nextInt();
        }
    }

    /** Convenience constructor that uses {@code hashCode()} for hashing. */
    public BloomFilter(int hashFunctionCount, int bitCount) {
        this(hashFunctionCount, bitCount, null);
    }

    /**
     * Create a Bloom filter sized for an expected number of elements and
     * a desired false positive probability. Computes optimal {@code m} and
     * {@code k} automatically.
     *
     * @param expectedElements the expected number of elements to insert
     * @param falsePositiveRate the desired false positive probability (e.g. 0.01)
     * @param toInt             element-to-int conversion (null for hashCode)
     */
    public BloomFilter(int expectedElements, double falsePositiveRate, ToIntFunction<E> toInt) {
        this(optimalK(expectedElements, optimalM(expectedElements, falsePositiveRate)),
                optimalM(expectedElements, falsePositiveRate),
                toInt);
    }

    // -----------------------------------------------------------------------
    // Optimal sizing formulas
    // -----------------------------------------------------------------------

    /** Optimal bit count: m = -n * ln(p) / (ln(2))² */
    private static int optimalM(int expectedElements, double falsePositiveRate) {
        double m = -expectedElements * Math.log(falsePositiveRate) / (Math.log(2) * Math.log(2));
        return Math.max(64, (int) Math.ceil(m));
    }

    /** Optimal hash function count: k = (m/n) * ln(2) */
    private static int optimalK(int expectedElements, int bitCount) {
        double k = ((double) bitCount / expectedElements) * Math.log(2);
        return Math.max(1, (int) Math.round(k));
    }

    // -----------------------------------------------------------------------
    // Core operations
    // -----------------------------------------------------------------------

    /**
     * Compute a non-negative hash bucket index for hash function {@code i}.
     * Uses unsigned right shift ({@code >>>}) instead of {@code Math.abs()}
     * to avoid the bug where {@code Math.abs(Integer.MIN_VALUE)} returns
     * a negative number (Integer.MIN_VALUE itself).
     */
    private int hashBucket(int hash, int i) {
        return ((hashMultipliers[i] * hash + hashOffsets[i]) >>> 1) % bitCount;
    }

    /** Convert an element to its integer hash seed. */
    private int elementHash(E element) {
        return (toInt != null) ? toInt.applyAsInt(element) : element.hashCode();
    }

    /**
     * Add an element to the filter. After this call, {@code probablyContains}
     * is guaranteed to return {@code true} for this element.
     *
     * @param element the element to add
     */
    public void add(E element) {
        int hash = elementHash(element);
        for (int i = 0; i < hashMultipliers.length; i++) {
            bits.set(hashBucket(hash, i));
        }
        elementCount++;
    }

    /**
     * Query whether an element is probably in the filter.
     * <ul>
     *   <li>{@code false} → the element was <b>definitely never added</b></li>
     *   <li>{@code true}  → the element was <b>probably added</b>
     *       (with a small false positive probability)</li>
     * </ul>
     *
     * @param element the element to look up
     * @return whether the element is probably present
     */
    public boolean probablyContains(E element) {
        int hash = elementHash(element);
        for (int i = 0; i < hashMultipliers.length; i++) {
            if (!bits.get(hashBucket(hash, i))) {
                return false; // Definitely not present — guaranteed correct.
            }
        }
        return true; // Probably present — small chance of false positive.
    }

    // -----------------------------------------------------------------------
    // Diagnostics
    // -----------------------------------------------------------------------

    /** Return the number of elements that have been added. */
    public int size() { return elementCount; }

    /** Return the fraction of bits that are currently set to 1. */
    public double fillRatio() {
        return (double) bits.cardinality() / bitCount;
    }

    /**
     * Return the theoretical false positive probability given the current
     * number of inserted elements: {@code (1 - e^(-kn/m))^k}.
     */
    public double theoreticalFalsePositiveRate() {
        int k = hashMultipliers.length;
        double exponent = -(double) k * elementCount / bitCount;
        return Math.pow(1 - Math.exp(exponent), k);
    }

    @Override
    public String toString() {
        return "BloomFilter[k=%d, m=%,d bits (%,d KB), n=%,d, fill=%.1f%%, theoretical FP=%.6f]"
                .formatted(hashMultipliers.length, bitCount, bitCount / 8 / 1024,
                        elementCount, fillRatio() * 100, theoreticalFalsePositiveRate());
    }

    // -----------------------------------------------------------------------
    // Random word generator for testing.
    // -----------------------------------------------------------------------

    private static String createUniqueWord(Random rng, Set<String> existing) {
        String word;
        do {
            int length = rng.nextInt(10) + 2;
            var sb = new StringBuilder(length);
            for (int j = 0; j < length; j++) {
                sb.append((char) ('a' + rng.nextInt(26)));
            }
            word = sb.toString();
        } while (existing.contains(word));
        return word;
    }

    // -----------------------------------------------------------------------
    // Main — demonstrate, verify, and measure the Bloom filter.
    // -----------------------------------------------------------------------

    public static void main(String[] args) {
        var rng = new Random(42);
        int insertCount = 50_000;
        int probeCount = 1_000_000;

        System.out.println("=== Bloom Filter Demonstration ===\n");

        // --- Manual configuration ---
        System.out.println("--- Manual configuration: k=20, m=128 KB ---\n");
        var manualFilter = new BloomFilter<String>(20, 128 * 1024 * 8);
        runExperiment(manualFilter, insertCount, probeCount, rng);

        // --- Auto-configured for 1% false positive rate ---
        System.out.println("\n--- Auto-configured for 1% false positive rate ---\n");
        var autoFilter1 = new BloomFilter<String>(insertCount, 0.01, null);
        runExperiment(autoFilter1, insertCount, probeCount, new Random(42));

        // --- Auto-configured for 0.1% false positive rate ---
        System.out.println("\n--- Auto-configured for 0.1% false positive rate ---\n");
        var autoFilter01 = new BloomFilter<String>(insertCount, 0.001, null);
        runExperiment(autoFilter01, insertCount, probeCount, new Random(42));

        // --- Space comparison ---
        System.out.println("\n--- Space comparison ---\n");
        System.out.printf("  Bloom filter (128 KB config): %,d bytes%n", 128 * 1024);
        // Rough estimate: HashSet stores String references (~40 bytes per entry
        // for the hash table overhead, plus the String objects themselves).
        System.out.printf("  HashSet (same %,d words):     ~%,d bytes (estimated)%n",
                insertCount, insertCount * 80);
        System.out.println("  The Bloom filter uses roughly " +
                (insertCount * 80) / (128 * 1024) + "× less memory.");
    }

    /**
     * Run a complete insert → verify → probe experiment on the given filter.
     */
    private static void runExperiment(BloomFilter<String> filter,
                                      int insertCount, int probeCount, Random rng) {
        var exactSet = new HashSet<String>(insertCount * 2);

        // Insert words into both the Bloom filter and a HashSet.
        for (int i = 0; i < insertCount; i++) {
            String word = createUniqueWord(rng, exactSet);
            filter.add(word);
            exactSet.add(word);
        }

        System.out.println("  " + filter);

        // Verify: no false negatives allowed.
        boolean allFound = exactSet.stream().allMatch(filter::probablyContains);
        System.out.println("  All inserted words found (no false negatives): " + allFound);
        if (!allFound) {
            System.out.println("  ERROR: Bloom filter implementation is broken!");
            return;
        }

        // Probe with words that were never inserted and count false positives.
        int falsePositives = 0;
        for (int i = 0; i < probeCount; i++) {
            String word = createUniqueWord(rng, exactSet);
            if (filter.probablyContains(word)) { falsePositives++; }
        }
        double observedRate = (double) falsePositives / probeCount;

        System.out.printf("  False positives: %,d / %,d probes%n", falsePositives, probeCount);
        System.out.printf("  Observed  FP rate: %.6f%n", observedRate);
        System.out.printf("  Theoretical FP rate: %.6f%n", filter.theoreticalFalsePositiveRate());
    }
}