compact data structure like set

Question

i am looking for a specific data structure, but i forgot its name. if i knew the name it would be trivial, i would just look it up in wikipedia :)

basically, it is like a set - except you cannot iterate it.

you put some values in it, lets say 80k zip codes.

then you can test if a given string is definately NOT a zip code, but you will eventually get false positives if you insert too many zip codes.

the memory consumption of this structure is quite small.

what is its name, and is there an implementation in java?

Answer 1

I believe you are looking for a Bloom Filter.

Here is a Java implementation.

Answer 2

I think you mean a Bloom filter. Here's one based on Java's BitSet.