Home  Collections intro  Lists  Maps  Sets  Which collection class?  Sorting  Hashing  Advanced
 Video lecture: hash tables

Search this site:
Threads Database Profiling Regular expressions Random numbers Compression Exceptions C Equivalents in Java

Advanced use of hash codes in Java

In this section, I want to go beyond the standard Java collections framework for some fairly specialised uses. In most cases, the standard collections will serve you extremely well. In particular, HashMap is a very versatile class, and its Java 5 brother ConcurrentHashMap provides an easy-to-use, high-concurrency data structure that suits many uses.

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.

 What do you think of this article? Did it help you? Found a mistake? Feedback and suggestions here


Written by Neil Coffey. Copyright © Javamex UK 2009. All rights reserved.