Java Collections: maps

The map is a fundamental type of structure that allows associations to be set up between one set of objects and another. By association, we typically mean situations where we want to say "for a given X, what is the Y?". For example:

In other words, maps have a wide variety of uses. Various routines would be inefficient and fiddly to write without them. Generally we can see that a map, or an instance of the Java Map interface, is a set of associations. So for example, we could have a map of string parameters to integer values:

Map<String,Integer> params = ...

Then, we can set and get parameters on this map:

params.set("maxConnections", 20);
params.set("maxThreads", 10);
...
int maxConnections = params.get("maxConnections");
int maxThreads = params.get("maxThreads");

The items that we associate from are referred to as keys. The items that we associate to (the integers in this case) are, in Java at least, usually referred to simply as values. Conceptually, you could imagine (and in principle implement) a Map as an array containing the keys and another array containing the values, with code such as the following to get an item out of the map:

public Integer get(String key) {
  for (int i = 0; i < keys.length; i++) {
    if (key.equals(keys[i])) {
      return values[i];
    }
  }
  return null;
}

Note that instances of Map always map objects to objects. So in fact, a Map of strings to integers would store Integer objects as the values. In our above example, we can (so long as we're careful about nulls) read and write straight to int primitives thanks to the 'autoboxing' feature of Java 5.

Introducing the hash map

Now, implementing a map with two arrays like this is conceptually simple, but would actually be quite inefficient for maps of any significant size. For example, imagine if the map had 10,000 entries in it (and in practical uses, it's not uncommon to want to store tens of thousands of items if not more in a map). In that case, on average we'd have to compare 5,000 items with the one passed in every time we called get()! One improvement that may be appropriate in some cases is to store the list sorted (and actually, Java provides some map implementations based on keeping the map data sorted, albeit in a more sophisticated way than a simple list). But that in turn can make insertions and deletions from the map expensive, since on every operation we have to maintain the map in its sorted state.

An alternative to keeping the map data sorted is to use hasing. On the next pages, we explore hashing and hash maps.