It should be noted it's impossible to have a 'reverse bloom filter' with the same properties as a regular bloom filter. That is, a constant predefined size give

It should be noted it's impossible to have a 'reverse bloom filter' with the same properties as a regular bloom filter. That is, a constant predefined size gives you a particular false negative rate. The thing you linked to is really just a cache. It has to store an entire entry (not just set some bits based on the hash) and doesn't have a predictable false negative rate based on its size. For more info: https://cstheory.stackexchange.com/questions/6596/a-probabilistic-set-with-no-false-positives https://cstheory.stackexchange.com/questions/6596/a-probabil...