A signed minimal perfect hash function may be a better bet. You can get down to around 2.68 bits per key plus w sign bits where the false positive rate is 2^-w.

A signed minimal perfect hash function may be a better bet. You can get down to around 2.68 bits per key plus w sign bits where the false positive rate is 2^-w. For false positive rate of 2^-9 (0.00195) that's 447 MB, which is slightly less than an optimal bloom filter for the same number of items, and lookups will be considerably faster. Construction time and the fact that you can't add to it without rebuilding the whole thing are the downsides. But given the application I don't think they matter much. http://sux4j.di.unimi.it/docs/it/unimi/dsi/sux4j/mph/MinimalPerfectHashFunction.html http://sux4j.di.unimi.it/docs/it/unimi/dsi/sux4j/mph/Minimal...