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
- 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
- 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.
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.