I guess it's storing the pointer to the data? That sounds pretty bad. At any-rate it's one of two things, either you store the whole item or you store a hash.

I guess it's storing the pointer to the data? That sounds pretty bad. 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 http://infoweekly.blogspot.com/2010/02/cuckoo-hashing.html).