A Bloom filter is a probabilistic data structure that answers "is X in this set?" with two possible answers: definitely not, or probably yes. In software it's clever; in hardware it's transformative, because it replaces a multi-cycle hash table lookup with a fixed-latency lookup that always completes in one clock — perfect for line-rate packet processing.

The structure is a bit array of m bits and k independent hash functions. To insert element X, you compute h₁(X), h₂(X), … hₖ(X), each producing an index into the array, and set those bits to 1. To query, you compute the same k hashes and AND the bits at those indices. If any bit is 0, X was never inserted — guaranteed. If all bits are 1, X is probably in the set, but other insertions may have collectively set those bits (a false positive).

Hardware loves this for three reasons. First, the k hash lookups are independent, so you instantiate k parallel SRAM read ports (or k banks of single-port SRAM) and read all k bits simultaneously in one cycle. Second, hash functions for Bloom filters can be cheap — a few XOR trees over the input bits, often built from CRC polynomials you already have. Third, no collision resolution logic is needed: there are no chains, no rehashing, no probe sequences. Just read, AND, done.

Real-world example: Cisco's high-end switches use Bloom filters in front of their MAC address tables. A packet arrives, the destination MAC hits the Bloom filter, and if the answer is "definitely not in our forwarding table," the switch immediately floods or drops without ever touching the expensive ternary CAM. The Bloom filter sits in a small on-chip SRAM and runs at full line rate (often >1 billion lookups/second). Only the ~1% of packets that pass the filter trigger the slower, power-hungry CAM lookup. Intel's DPDK and many DDoS-mitigation ASICs use the same trick to filter blocklisted IPs.

The sizing rule of thumb: for n inserted elements and target false positive rate p, you need m = -n·ln(p)/(ln 2)² bits and k = (m/n)·ln 2 hash functions. For n=10,000 entries and p=1%, that's ~96,000 bits (12 KB of SRAM) and k≈7 hashes. Halve p to 0.5%, and m only grows by ~15% — false positives drop exponentially per bit added.

The catch: you can't delete. Clearing bits would corrupt other entries that share them. Hardware fixes this with counting Bloom filters (replace each bit with a 4-bit saturating counter) at 4× the memory cost, or by maintaining two filters and swapping them periodically.