When the data is read-only, sparse linear filters get up to an O(ln 2)-factor smaller storage space at the cost of slower construction and inability to add item

When the data is read-only, sparse linear filters get up to an O(ln 2)-factor smaller storage space at the cost of slower construction and inability to add items on the fly. These include xor-sat filters, xor/xor+ filters, smashed/bumped ribbon filters, frayed ribbon filters, binary fuse filters, probably a few other options. The basic idea is that instead of table[hash1(x)] & table[hash2(x)] & ..., you calculate table[hash1(x)] ^ table[hash2(x)] ^ ... basically substituting XOR instead of AND. To construct the table, you need to solve a big system of linear equations. The various filter types change the parameters (mostly load factor of the filter) and indexing function (turning the hash into something where the bits you look up have correlated positions) in order to make structured equations that are easier to solve.