My absolute favorite, Cuckoo hashing, has been mentioned already, but so far (239 comment in) nobody has mention this approach (called?) to store an array A[] of N-bit numbers, most of which are zero or small: use N set of numbers S[N], such that for each A[I] you store I in S[J] where J are the bit positions where A[I] have a set bit. In other words, S[J] are the indices of elements from A that has a set bit in position J.
The representation of S can be anything, and even dynamically adapting to the data. I’ve seen trees of bitmaps for example.
In practice Cuckoo sucks, b/c the reading from an unknown index in an array is not a const cost operation. It has an upper bound of course, but its average cost is quite different, depending if you are to hit L1, or L2... or just go for the a cache miss.
"Cache misses" is what dominates performance nowadays.
The representation of S can be anything, and even dynamically adapting to the data. I’ve seen trees of bitmaps for example.