Maps in the Java Collection Framework

Most programs eventually have to deal with many objects at once. A program might keep a list of students in a course, the set of distinct words in a document, or a lookup table that connects a name to a phone number. Writing a separate variable for each of these items would not scale, because the number of items is not fixed and the program needs to add, search, and remove them while it runs.

The Java Collection Framework is the part of Java's standard library that provides ready-made, generic data structures for holding and manipulating groups of objects. Instead of inventing your own way to store a group, you choose from a set of tested structures. This article maps out the framework's main pieces. Later articles on specific classes will have a clear place to fit once you understand this map.

A useful way to start is to ask one question about any group you want to store: does the group behave like a sequence of positions, or like a bag of distinct things? The answer determines which part of the framework you reach for. Keep this question in mind, because the rest of the article is organized around it.

Consider two situations. In the first, you record the order in which customers arrive at a counter, and the same customer may come back several times. In the second, you collect the distinct email addresses that have ever signed up, and a duplicate would be a mistake. The first situation is a sequence of positions. The second is a bag of distinct things. Hold on to that difference, because it is what separates a list from a set later in this article.

The generic data structures in the framework fall into two families. The first family is the collection, which is simply a group of objects. The second family is the map, which pairs objects from one set with objects from another set. A map works like a dictionary that pairs each word with its definition, or like a phone book that pairs each name with a number. Its job is to answer the question of what one thing corresponds to, rather than to hold a plain group.

In Java, these two families are described by two parameterized interfaces. Collection<T> represents collections, and Map<T,S> represents maps. The letter T stands for a type parameter that can be any non-primitive type, so Collection<String> is a collection of strings and Collection<Integer> is a collection of Integer objects. Map has two type parameters, which is one reason it is treated separately from collections. This article and the next one concentrate on collections, while maps are left for their own later treatment.

The difference between the two families shows up in how you find things. In a sequence, an item is located by its position: it is the third item, or the item after the first. In a map, an item is located by a key. You do not ask for the value at position 2. You ask for the value that belongs to a particular key, such as the phone number that belongs to a particular name.

The figure shows a phone book in the spirit of the source's example. Each key on the left is paired with exactly one value on the right, and the question you ask is always 'what corresponds to this key?' A list would answer a different question, namely 'what is stored at this position?' Keeping those two questions apart is the core skill of this article.

Inside the collection family, the framework recognizes two main kinds of collection. A list is a collection whose objects sit in a linear sequence, so it has a first item, a second item, and so on, and every item except the last has an item that directly follows it. A set is a collection built around a single rule: no object can appear in it more than once. The elements of a set are not thought of as having any particular order.

These two ideas are represented by the parameterized interfaces List<T> and Set<T>. Both are subinterfaces of Collection<T>. The practical consequence is that any object that implements List<T> or Set<T> automatically implements Collection<T> as well. Collection<T> holds the operations that every collection shares, while List<T> and Set<T> each add the operations that suit their own kind of group.

Read the figure from the bottom up. An ArrayList<T> must implement the matching list interface. Because List<T> extends Collection<T>, an ArrayList can use every method declared in the list and collection interfaces. The concrete classes are covered in the next article, so for now it is enough to see that the interfaces describe what a collection can do, and the classes describe how it is actually built.

The two kinds of collection differ on exactly the two dimensions the opening question raised: order and duplicates. A list keeps its objects in a linear sequence. A set forbids duplicates and does not attach a particular order to its elements. The table below puts the two side by side.

Because a collection can be a list, a set, or something else built on Collection<T>, the operations that the interface defines have to be general. They apply to a collection of any non-primitive type. Suppose coll is an object that implements Collection<T> for some specific type T. The interface then makes the operations below available for coll. Read them as a family of questions you can ask of a group, and as a family of actions you can take on it.

The best way to understand these operations is to follow a short sequence of calls and watch the contents change. Start with an empty set of words and apply each call in order. Before you read the trace, predict what the set holds after the fourth call.