Before diving into the structures themselves, we need to understand their core building block: hash functions.
A hash function takes an input of any size — a long URL, an IP address, a product SKU — and converts it into a fixed-size number, typically a 32-bit or 64-bit integer. The same input always produces the same output, but two different inputs will almost always produce different outputs.
For probabilistic data structures, we need hash functions with two specific properties:
- Speed: They must be extremely fast to compute, since they run on every single incoming item in a high-throughput stream. Cryptographic hash functions like SHA-256 are too slow for this purpose. Non-cryptographic functions like MurmurHash3 or xxHash are the standard choice.
- Uniform distribution: The output values should be spread evenly across the entire possible range of numbers. If a hash function tends to cluster outputs in a narrow range, the data structure's error guarantees break down.
Most probabilistic structures use multiple independent hash functions simultaneously. Each function produces a different "fingerprint" for the same item, pointing to different positions in the structure. Using multiple independent signals reduces the probability of accidental collisions causing incorrect results. In practice, you can simulate multiple independent hash functions from a single hash function using a technique called double hashing: given hash functions h1 and h2, you derive the i-th hash as h(i) = h1(item) + i * h2(item).