Filter sizer
How big does a membership filter get for your key count and false-positive rate? Sizes below follow each reference library's own allocation code, not the asymptotic textbook number. Or turn it around: give it a memory budget and see the best false-positive rate each filter gets. Warnings come from measurements.
| Filter | Use | Bits/key | Size | Real FPR |
|---|
What's counted
- Bloom: best integer number of hashes, smallest bit array that meets the rate.
- Blocked Bloom: every key lands in one 512-bit block (one cache line). Faster lookups, a few more bits. Exact Poisson formula over block loads.
- Cuckoo: 4 slots per bucket, bucket count rounded up to a power of two and doubled above 96% load, as in efficient/cuckoofilter. Semi-sorting packs 4 fingerprints into 1 bit less each.
- Xor: 1.23 n + 32 cells, as in xor_singleheader.
- Binary fuse: the same library's segment length and size factor. Big sets get close to 1.125 cells per key (3-wise); small sets pay more.
- Ribbon: RocksDB's Standard128Ribbon. Slots from its table (about 1 build in 20 fails and retries with a new seed); slack grows slowly with n, about 3.5% at 100k keys and 5% at 1M. Each 128-slot block stores a whole number of result bits, so the average can be fractional and land right on the target rate.
- Lower bound: n · log₂(1/ε) bits. No filter goes below it. With a memory budget of m bits, no filter beats ε = 2−m/n.
- Memory budget: Bloom filters use the whole budget with the best number of hashes. Cuckoo, xor and fuse tables have a fixed number of slots for n keys, so the budget only buys wider fingerprints, and the rest goes unused. Ribbon spends it one 128-bit segment at a time, so almost nothing is left over. Sizes: KB and MB are 1024-based; "8 bits/key" works too.
Only the filter arrays are counted, without headers or seeds. Xor, fuse and ribbon filters are built once from the full key set; nothing can be added later. Background, with the measurements behind the warnings: Bloom index math, cuckoo load, fuse sizing.