An interesting probabilistic datastructure is called "bloom filters", which can quickly tell you whether an item's possibly in a set or definitely not. Useful for when the true check is very expensive.

The way they work is by allocating a finite number of bits, and using a hash function to determine which, say, 3 bits should be set for any given item you'd want to check. To add an item (you can't remove them) you enable those bits to 1. To check an item you see if they're all already 1.

1/2