Bloom filters and sketches

Key points

• A Bloom filter hashes a key to k positions and sets those bits. If any one of them is 0, the key is definitely absent.
• If they are all 1 the key is probably present - other keys may have set those bits. False positives yes, false negatives never.
• A million keys at a 1% false-positive rate costs about 1.2 MB. Storing the keys themselves would cost hundreds of megabytes.
• Use one as a guard in front of an expensive lookup. Cassandra and RocksDB check a filter per file before ever touching the disk.
• You cannot delete from a plain Bloom filter, because clearing a bit would break other keys. Rebuild it, or use a counting variant.
• HyperLogLog counts distinct users in about 12 KB with ~2% error, and a count-min sketch estimates per-key frequency the same way.

Example

import java.util.BitSet;
import java.util.HashSet;
import java.util.Set;

public class Main {

    // m bits, k hashes. No key is ever stored, so it can never list its members.
    static final class BloomFilter {
        private final BitSet bits;
        private final int m;
        private final int k;

        BloomFilter(int m, int k) { this.m = m; this.k = k; this.bits = new BitSet(m); }

        private int at(String key, int i) {
            int h = key.hashCode() * 0x9E3779B1 + i * 0x85EBCA6B;
            h ^= (h >>> 15);
            h *= 0xC2B2AE35;
            h ^= (h >>> 13);
            return Math.floorMod(h, m);
        }

        void add(String key) {
            for (int i = 0; i < k; i++) bits.set(at(key, i));
        }

        boolean mightContain(String key) {
            for (int i = 0; i < k; i++) {
                if (!bits.get(at(key, i))) return false;      // a 0 bit: certainly absent
            }
            return true;                                     // all 1s: probably present
        }
    }

    public static void main(String[] args) {
        int m = 100_000, k = 7, present = 10_000, absent = 100_000;
        BloomFilter filter = new BloomFilter(m, k);
        Set<String> real = new HashSet<>();

        for (int i = 0; i < present; i++) {
            filter.add("user:" + i);
            real.add("user:" + i);
        }

        int falseNegatives = 0;
        for (String key : real) if (!filter.mightContain(key)) falseNegatives++;

        int falsePositives = 0;
        for (int i = 0; i < absent; i++) if (filter.mightContain("ghost:" + i)) falsePositives++;

        System.out.println("memory used     : " + (m / 8 / 1024) + " KB for " + present + " keys");
        System.out.println("false negatives : " + falseNegatives + "   <- always zero, by construction");
        System.out.printf("false positives : %.2f%% of absent keys%n", falsePositives * 100.0 / absent);
        System.out.println("lookups skipped : " + (absent - falsePositives) + " of " + absent);
    }
}

Trade a small bounded error for a huge memory win - but only where a false positive costs one wasted lookup.