Coincidentally, I was just testing an actual perfect hash function generator https://github.com/rizkg/BBHash https://github.com/rizkg/BBHash. It requires 2-3 bi

Coincidentally, I was just testing an actual perfect hash function generator https://github.com/rizkg/BBHash https://github.com/rizkg/BBHash. It requires 2-3 bits per entry irrespective of key or table size. They show that they can build the table for 10^12 entries. One problem is that identifying keys that aren't in the table can be as expensive as storing all the keys. I was thinking that it would be interesting to build two tables with different hash functions for the same set of keys and then record the mapping between them. This would double the table size and add n log n bits to record the relationship, but it would let you make probabilistic (but pretty confident) estimates of what keys weren't in the table, all with a fixed number of bits per key. To clarify, if you map a key into the table with both functions, by construction it will map to a position in each table that are linked together. If a key maps to unlinked positions in each table then we know with probability ~(1-1/n) that the key isn't in the input to the table. When keys are big and n is big you could be very confident in this estimate and save a huge amount of space over typical structures to do this.