Advanced use of hash codes in Java

However, the Java hash map (and derived classes such as HashSet) does have a few limitations. In particular, it doesn't let us trade off memory and object usage for accuracy. Because of some implementational decisions, the Java hash map is forced to store entire keys in memory. It also uses an object-hungry linked list structure for its buckets. In certain restricted circumstances, we can use hashing in slightly different ways:

• with a wider, stronger hash code we may be able to dispense with storing the keys and just store the hash codes;
• we can implement a much more compact hash set if we are prepared to accept a trade-off between accuracy and memory storage.

To understand how these works, it's first worth understanding a few brief statistics about hash codes.