This reminds me of the HyperLoglog [1] algorithm for approximating the cardinality of a huge set with limited memory.
I really would love to see a book that basically just covers all the cool data structures people have come up with using hash functions.