I recently discovered these fascinating little data structures that I should have already known about. They are called Bloom filters, and they are a representation of a set of keys. Like a hash table storing booleans, they have constant time lookup, but they are really more like a hash function indexing into a bit vector. The link is to a nice description with a little perl code for illustration; an alternative description is at Wikipedia.

Bloom filters are very intuitive and have a number of appealing properties:

• simple to describe and implement
• much more compact than just a hash table of booleans
• can be OR'd together to form set unions
• variable probability of false positives which can actually has privacy-preserving applications

Check them out and you will likely be pleased.
(While we're on the topic of neat little data structures that aren't talked about enough, check out skip lists if you're not already familiar with them.)