Java Collections: introduction to hashing and hash maps

In our using Java collections tutorial, we looked at a type of collection called a map. A map is a set of associations, for example between country codes and their corresponding names, or between IDs and corresponding cached objects, or in fact a whole host of other programming problems. The particular type of Map that we used in our illustration was a Java HashMap. A hash map uses a particular structure internally to try and make looking objects up in the map efficient. On this and the following pages, we'll look in more detail at that structure.

When do I need to worry about how hash maps work?

In our example of using a HashMap, we were just storing plain old Strings in the map. As with many other objects in the standard Java libraries, for storing Strings you don't usually need to worry too much about the gory details of how hash maps work. However, knowing how hash maps work is more important:

• if you want to use keys (the items that you map from) which are of a class that you have written;
• to understand certain performance characteristics of the hash map, and when there might be "worst cases" (this really applies to any collection type or algorithm of course);
• to weigh up the pros and cons of using a HashMap compared to other types of collection (again, the same is really true of other types of collection);
• just for the sake of understanding hashing, which is a common and useful programming technique.

Introducing hashing

The name HashMap (and indeed HashSet) comes from the general name of the technique they use: hashing. On the following pages, we'll look at the general technique of hashing and how it applies to Java collections that use it, notably the HashMap and HashSet classes.

---