This is actually not true and not possible. There is a good explanation here: http://cstheory.stackexchange.com/a/14455/43
There will be a low probability of false positives ~ 2^32*k. (Also it's not an inverse-bloom filter, it's a cache).
This is actually not true and not possible. There is a good explanation here: http://cstheory.stackexchange.com/a/14455/43
There will be a low probability of false positives ~ 2^32*k. (Also it's not an inverse-bloom filter, it's a cache).
EDIT: I suppose my point was just that there is a difference between "I think you chose a bad name for your class" and "This is actually not true and not possible". It seems both true and possible (and arguably inappropriately named).
That said, this is just a silly definition issue. You can provide a data structure with no false positives, and some false negatives, but you can't do it in constant space. I'm not aware of if you can absolutely bound the rate of false negatives.
At any-rate it's one of two things, either you store the whole item or you store a hash. If you're storing the whole item it's not a filter and you don't get constant space guarantees as you mentioned. If you store a hash - it's possible to have false positives.
You can always get a bound for false-negatives (or none at all) same as it with any hash-table. If you wanted to, you could Cuckoo hash before eviction and you should be able to get a pretty-good theoretical bound for false-negatives (http://infoweekly.blogspot.com/2010/02/cuckoo-hashing.html).
3 bits end up doing what would require a multiword bloom filter with 30 k hashes.