It bears mentioning that not only cuckoo filters but also simply vanilla linear probed hash tables of B-bit truncated hashes (sometimes called fingerprints) can

It bears mentioning that not only cuckoo filters but also simply vanilla linear probed hash tables of B-bit truncated hashes (sometimes called fingerprints) can be a better substitute for Bloom filters. This seems a highly under propagated fact. "high p" (order 10%) numerical examples are often used to sell an idea less valuable at small p. An (asymptotic, for p <=~ 10%) back of the envelope formula is that such a hash table/set of fingerprints takes up a factor of about (1+log_{1/p}(N)) more space than a Bloom filter. It is not hard to derive this. Unlike the incredibly precise Coq formula proof theme, this is all approximate, but more engineering-relevant. If you were targeting p=0.001 to have a small mistake rate, 1 + log_1000(N) is pretty small (say <~ 1+3=4 for for N <~ 1e9 elements). While it does use 25% space, this Bloom filter would require many more (-log_2(p) =~ 10) probes while the LP hash table would only hit the DIMMs once. Many, but not all, might view a 10x latency reduction as worth 4x the space in the game of space-speed trade-offs.