You could use Blocked Bloom Filters[1]. It's essentially many small Bloom Filters that each fit into a cache-line. The first hash function decides, which of the

You could use Blocked Bloom Filters[1]. It's essentially many small Bloom Filters that each fit into a cache-line. The first hash function decides, which of the smaller Bloom Filters an element will be saved in and can still cause a cache miss. All subsequent accesses to the small Bloom Filters are cached. The main drawback is that, because the elements won't be completely evenly distributed among the small Bloom Filters, you need some additional space to compensate and keep the false positive rate low. [1] https://www.cs.amherst.edu/~ccmcgeoch/cs34/papers/cacheefficientbloomfilters-jea.pdf https://www.cs.amherst.edu/~ccmcgeoch/cs34/papers/cacheeffic...