TLDR: a cache with LRU eviction, but only storing the keys, not the values.
"A Bloom filter is a data structure that may report it contains an item that it does not (a false positive), but is guaranteed to report correctly if it contains the item (“no false negatives”)."
I'm afraid that is not how it works. A Bloom filter can tell whether an item may be in the set (false positive) but can definitely tell an item is NOT in the set (no false negative).
"It's a cache." The use case is deduplication in an event-stream environment. This calls for exact matching without hash collisions.
Low memory version:
`return false;`
I would argue that the opposite of a bloom filter doesn't really exist, at least not in a satisfying way. A bloom filter's size is dependent only on the desired false positive rate, whereas its opposite must be dependent on the size of the data. (And don't be fooled by data that can be represented by a primary key, that's not as general as a bloom filter.) I tried, with limited success, to explain my point of view in this answer on StackExchange: https://cstheory.stackexchange.com/questions/6596/a-probabil...