By providing useful data structures and algorithms, the Collections Framework frees you to concentrate on the important parts of your program rather than on the low-level “plumbing” required to make it work. By facilitating interoperability among unrelated APIs, the Java Collections Framework frees you from writing adapter objects or conversion code to connect APIs.

This Collections Framework provides high-performance, high-quality implementations of useful data structures and algorithms. The various implementations of each interface are interchangeable, so programs can be easily tuned by switching collection implementations. Because you’re freed from the drudgery of writing your own data structures, you’ll have more time to devote to improving programs’ quality and performance.

The collection interfaces are the vernacular by which APIs pass collections back and forth. If my network administration API furnishes a collection of node names and if your GUI toolkit expects a collection of column headings, our APIs will interoperate seamlessly, even though they were written independently.

Many APIs naturally take collections on input and furnish them as output. In the past, each such API had a small sub-API devoted to manipulating its collections. There was little consistency among these ad hoc collections sub-APIs, so you had to learn each one from scratch, and it was easy to make mistakes when using them. With the advent of standard collection interfaces, the problem went away.

This is the flip side of the previous advantage. Designers and implementers don’t have to reinvent the wheel each time they create an API that relies on collections; instead, they can use standard collection interfaces.

New data structures that conform to the standard collection interfaces are by nature reusable. The same goes for new algorithms that operate on objects that implement these interfaces.

There are two ways to traverse collections: (1) with the for-each construct and (2) by using Iterators.

for (Object o : collection)
  System.out.println(o);

public interface Iterator<E> {
  boolean hasNext();
  E next();
  void remove(); // optional
}

static void filter(Collection<?> c) {
  for (Iterator<?> it = c.iterator(); it.hasNext(); )
    if (!cond(it.next()))
      it.remove();
}

Bulk operations perform an operation on an entire Collection. You could implement these shorthand operations using the basic operations, though in most cases such implementations would be less efficient. The following are the bulk operations:

The addAll, removeAll, and retainAll methods all return true if the target Collection was modified in the process of executing the operation.

As a simple example of the power of bulk operations, consider the following idiom to remove all instances of a specified element, e, from a Collection, c:

c.removeAll(Collections.singleton(e));

More specifically, suppose you want to remove all of the null elements from a Collection:

c.removeAll(Collections.singleton(null));

This idiom uses Collections.singleton, which is a static factory method that returns an immutable Set containing only the specified element.

The toArray methods are provided as a bridge between collections and older APIs that expect arrays on input. The array operations allow the contents of a Collection to be translated into an array. The simple form with no arguments creates a new array of Object. The more complex form allows the caller to provide an array or to choose the runtime type of the output array.

For example, suppose that c is a Collection. The following snippet dumps the contents of c into a newly allocated array of Object whose length is identical to the number of elements in c:

Object[] a = c.toArray();

Suppose that c is known to contain only strings (perhaps because c is of type Collection<String>). The following snippet dumps the contents of c into a newly allocated array of String whose length is identical to the number of elements in c:

String[] a = c.toArray(new String[0]);

The size operation returns the number of elements in the Set (its cardinality). The isEmpty method does exactly what you think it would. The add method adds the specified element to the Set if it’s not already present and returns a boolean indicating whether the element was added. Similarly, the remove method removes the specified element from the Set if it’s present and returns a boolean indicating whether the element was present. The iterator method returns an Iterator over the Set.

The following program^[11] takes the words in its argument list and prints out any duplicate words, the number of distinct words, and a list of the words with duplicates eliminated:

import java.util.*;

public class FindDups {
  public static void main(String[] args) {
    Set<String> s = new HashSet<String>();
    for (String a : args)
      if (!s.add(a))
        System.out.println("Duplicate detected: " + a);

    System.out.println(s.size() + " distinct words: " + s);
  }
}

Now run the program:

java FindDups i came i saw i left

The following output is produced:

Duplicate detected: i
Duplicate detected: i
4 distinct words: [i, left, saw, came]

Note that the code always refers to the Collection by its interface type (Set) rather than by its implementation type (HashSet). This is a strongly recommended programming practice because it gives you the flexibility to change implementations merely by changing the constructor. If either of the variables used to store a collection or the parameters used to pass it around are declared to be of the Collection’s implementation type rather than its interface type, all such variables and parameters must be changed in order to change its implementation type.

Furthermore, there’s no guarantee that the resulting program will work. If the program uses any nonstandard operations present in the original implementation type but not in the new one, the program will fail. Referring to collections only by their interface prevents you from using any nonstandard operations.

The implementation type of the Set in the preceding example is HashSet, which makes no guarantees as to the order of the elements in the Set. If you want the program to print the word list in alphabetical order, merely change the Set’s implementation type from HashSet to TreeSet. Making this trivial one-line change causes the command line in the previous example to generate the following output:

java FindDups i came i saw i left
Duplicate detected: i
Duplicate detected: i
4 distinct words: [came, i, left, saw]

Bulk operations are particularly well suited to Sets; when applied, they perform standard set-algebraic operations. Suppose s1 and s2 are sets. Here’s what bulk operations do:

To calculate the union, intersection, or set difference of two sets nondestructively (without modifying either set), the caller must copy one set before calling the appropriate bulk operation. The following are the resulting idioms:

Set<Type> union = new HashSet<Type>(s1);
union.addAll(s2);

Set<Type> intersection = new HashSet<Type>(s1);
intersection.retainAll(s2);

Set<Type> difference = new HashSet<Type>(s1);
difference.removeAll(s2);

The implementation type of the result Set in the preceding idioms is HashSet, which is, as already mentioned, the best all-around Set implementation in the Java platform. However, any general-purpose Set implementation could be substituted.

Let’s revisit the FindDups program. Suppose you want to know which words in the argument list occur only once and which occur more than once, but you do not want any duplicates printed out repeatedly. This effect can be achieved by generating two sets—one containing every word in the argument list and the other containing only the duplicates. The words that occur only once are the set difference of these two sets, which we know how to compute. Here’s how the resulting program^[12] looks:

import java.util.*;

public class FindDups2 {
  public static void main(String[] args) {
    Set<String> uniques = new HashSet<String>();
    Set<String> dups    = new HashSet<String>();

    for (String a : args)
      if (!uniques.add(a))
        dups.add(a);

    // Destructive set-difference
    uniques.removeAll(dups);

    System.out.println("Unique words:    " + uniques);
    System.out.println("Duplicate words: " + dups);
  }
}

When run with the same argument list used earlier (i came i saw i left), the program yields the following output:

Unique words:    [left, saw, came]
Duplicate words: [i]

A less common set-algebraic operation is the symmetric set difference—the set of elements contained in either of two specified sets but not in both. The following code calculates the symmetric set difference of two sets nondestructively:

Set<Type> symmetricDiff = new HashSet<Type>(s1);
symmetricDiff.addAll(s2);
Set<Type> tmp = new HashSet<Type>(s1);
tmp.retainAll(s2));
symmetricDiff.removeAll(tmp);

The array operations don’t do anything special for Sets beyond what they do for any other Collection. These operations are described in the Collection Interface Array Operations section (page 301).

If you’ve used Vector, you’re already familiar with the general basics of List. (Of course, List is an interface, while Vector is a concrete implementation.) List fixes several minor API deficiencies in Vector. Commonly used Vector operations, such as elementAt and setElementAt, have been given much shorter names. When you consider that these two operations are the List analog of square brackets for arrays, it becomes apparent that shorter names are highly desirable. Consider the following assignment statement:

a[i] = a[j].times(a[k]);

The Vector equivalent is:

v.setElementAt(v.elementAt(j).times(v.elementAt(k)), i);

The List equivalent is:

v.set(i, v.get(j).times(v.get(k)));

You may already have noticed that the set method, which replaces the Vector method setElementAt, reverses the order of the arguments so that they match the corresponding array operation. Consider the following assignment statement:

gift[5] = "golden rings";

The Vector equivalent is:

gift.setElementAt("golden rings", 5);

The List equivalent is:

gift.set(5, "golden rings");

For consistency’s sake, the method add(int, E), which replaces insertElementAt(Object, int), also reverses the order of the arguments.

The various range operations in Vector (indexOf, lastIndexOf, and setSize) have been replaced by a single range-view operation (subList), which is far more powerful and consistent.

The operations inherited from Collection all do about what you’d expect them to do, assuming you’re already familiar with them. If you’re not familiar with them from Collection, now would be a good time to read the Collection Interface Array Operations section (page 301). The remove operation always removes the first occurrence of the specified element from the list. The add and addAll operations always append the new element(s) to the end of the list. Thus, the following idiom concatenates one list to another:

list1.addAll(list2);

Here’s a nondestructive form of this idiom, which produces a third List consisting of the second list appended to the first:

List<Type> list3 = new ArrayList<Type>(list1);
list3.addAll(list2);

Note that the idiom, in its nondestructive form, takes advantage of ArrayList’s standard conversion constructor.

Like the Set interface, List strengthens the requirements on the equals and hashCode methods so that two List objects can be compared for logical equality without regard to their implementation classes. Two List objects are equal if they contain the same elements in the same order.

The basic positional access operations (get, set, add, and remove) behave just like their longer-named counterparts in Vector (elementAt, setElementAt, insertElementAt, and removeElementAt) with one noteworthy exception: The set and remove operations return the old value that is being overwritten or removed; the Vector counterparts (setElementAt and removeElementAt) return nothing (void). The search operations indexOf and lastIndexOf behave exactly like the identically named operations in Vector.

The addAll operation inserts all the elements of the specified Collection starting at the specified position. The elements are inserted in the order they are returned by the specified Collection’s iterator. This call is the positional access analog of Collection’s addAll operation.

Here’s a little method to swap two indexed values in a List. It should look familiar from Programming 101:

public static <E> void swap(List<E> a, int i, int j) {
  E tmp = a.get(i);
  a.set(i, a.get(j));
  a.set(j, tmp);
}

Of course, there’s one big difference. This is a polymorphic algorithm: It swaps two elements in any List, regardless of its implementation type. Here’s another polymorphic algorithm that uses the preceding swap method:

public static void shuffle(List<?> list, Random rnd) {
  for (int i = list.size(); i > 1; i--)
    swap(list, i - 1, rnd.nextInt(i));
}

This algorithm, which is included in the Java platform’s Collections^[16] class, randomly permutes the specified list using the specified source of randomness. It’s a bit subtle: It runs up the list from the bottom, repeatedly swapping a randomly selected element into the current position. Unlike most naive attempts at shuffling, it’s fair (all permutations occur with equal likelihood, assuming an unbiased source of randomness) and fast (requiring exactly list.size()-1 swaps). The following program uses this algorithm to print the words in its argument list in random order:

import java.util.*;

public class Shuffle {
  public static void main(String[] args) {
    List<String> list = new ArrayList<String>();
    for (String a : args)
      list.add(a);
    Collections.shuffle(list, new Random());
    System.out.println(list);
  }
}

In fact, this program can be made even shorter and faster. The Arrays^[17] class has a static factory method called asList, which allows an array to be viewed as a List. This method does not copy the array. Changes in the List write through to the array and vice versa. The resulting List is not a general-purpose List implementation, because it doesn’t implement the (optional) add and remove operations: Arrays are not resizable. Taking advantage of Arrays.asList and calling the library version of shuffle, which uses a default source of randomness, you get the following tiny program^[18] whose behavior is identical to the previous program:

import java.util.*;

public class Shuffle {
  public static void main(String[] args) {
    List<String> list = Arrays.asList(args);
    Collections.shuffle(list);
    System.out.println(list);
  }
}

As you’d expect, the Iterator returned by List’s iterator operation returns the elements of the list in proper sequence. List also provides a richer iterator, called a ListIterator, which allows you to traverse the list in either direction, modify the list during iteration, and obtain the current position of the iterator. The ListIterator interface follows:

public interface ListIterator<E> extends Iterator<E> {
  boolean hasNext();
  E next();
  boolean hasPrevious();
  E previous();
  int nextIndex();
  int previousIndex();
  void remove(); // optional
  void set(E e); // optional
  void add(E e); // optional
}

The three methods that ListIterator inherits from Iterator (hasNext, next, and remove) do exactly the same thing in both interfaces. The hasPrevious and the previous operations are exact analogues of hasNext and next. The former operations refer to the element before the (implicit) cursor, whereas the latter refer to the element after the cursor. The previous operation moves the cursor backward, whereas next moves it forward.

Here’s the standard idiom for iterating backward through a list:

for (ListIterator<Type> it = list.listIterator(list.size());
                                         it.hasPrevious(); ) {
  Type t = it.previous();
  ...
}

Note the argument to listIterator in the preceding idiom. The List interface has two forms of the listIterator method. The form with no arguments returns a ListIterator positioned at the beginning of the list; the form with an int argument returns a ListIterator positioned at the specified index. The index refers to the element that would be returned by an initial call to next. An initial call to previous would return the element whose index was index-1. In a list of length n, there are n+1 valid values for index, from 0 to n, inclusive.

Intuitively speaking, the cursor is always between two elements—the one that would be returned by a call to previous and the one that would be returned by a call to next. The n+1 valid index values correspond to the n+1 gaps between elements, from the gap before the first element to the gap after the last one. Figure 11.2 shows the five possible cursor positions in a list containing four elements.

Figure 11.2. The five possible cursor positions.

Calls to next and previous can be intermixed, but you have to be a bit careful. The first call to previous returns the same element as the last call to next. Similarly, the first call to next after a sequence of calls to previous returns the same element as the last call to previous.

It should come as no surprise that the nextIndex method returns the index of the element that would be returned by a subsequent call to next, and previousIndex returns the index of the element that would be returned by a subsequent call to previous. These calls are typically used either to report the position where something was found or to record the position of the ListIterator so that another ListIterator with identical position can be created.

It should also come as no surprise that the number returned by nextIndex is always one greater than the number returned by previousIndex. This implies the behavior of the two boundary cases: (1) a call to previousIndex when the cursor is before the initial element returns -1 and (2) a call to nextIndex when the cursor is after the final element returns list.size(). To make all this concrete, the following is a possible implementation of List.indexOf:

public int indexOf(E e) {
  for (ListIterator<E> it = listIterator(); it.hasNext(); )
    if (e == null ? it.next() == null : e.equals(it.next()))
      return it.previousIndex();
  return -1;  // Element not found
}

Note that the indexOf method returns it.previousIndex() even though it is traversing the list in the forward direction. The reason is that it.nextIndex() would return the index of the element we are about to examine, and we want to return the index of the element we just examined.

The Iterator interface provides the remove operation to remove the last element returned by next from the Collection. For ListIterator, this operation removes the last element returned by next or previous. The ListIterator interface provides two additional operations to modify the list—set and add. The set method overwrites the last element returned by next or previous with the specified element. The following polymorphic algorithm uses set to replace all occurrences of one specified value with another:

public static <E> void replace(List<E> list, E val, E newVal) {
  for (ListIterator<E> it = list.listIterator(); it.hasNext();)
    if (val == null ?
        it.next() == null : val.equals(it.next()))
      it.set(newVal);
}

The only bit of trickiness in this example is the equality test between val and it.next. You need to special-case a val value of null to prevent a NullPointerException.

The add method inserts a new element into the list immediately before the current cursor position. This method is illustrated in the following polymorphic algorithm to replace all occurrences of a specified value with the sequence of values contained in the specified list:

public static <E> void replace(List<E> list, E val,
                               List<? extends E> newVals) {
  for (ListIterator<E>
       it = list.listIterator(); it.hasNext(); ){
    if (val == null ?
        it.next() == null : val.equals(it.next())) {
      it.remove();
      for (E e : newVals)
        it.add(e);
    }
  }
}

The range-view operation, subList(int fromIndex, int toIndex), returns a List view of the portion of this list whose indices range from fromIndex, inclusive, to toIndex, exclusive. This half-open range mirrors the typical for loop:

for (int i = fromIndex; i < toIndex; i++) {
  ...
}

As the term view implies, the returned List is backed up by the List on which subList was called, so changes in the former are reflected in the latter.

This method eliminates the need for explicit range operations (of the sort that commonly exist for arrays). Any operation that expects a List can be used as a range operation by passing a subList view instead of a whole List. For example, the following idiom removes a range of elements from a List:

list.subList(fromIndex, toIndex).clear();

Similar idioms can be constructed to search for an element in a range:

int i = list.subList(fromIndex, toIndex).indexOf(o);
int j = list.subList(fromIndex, toIndex).lastIndexOf(o);

Note that the preceding idioms return the index of the found element in the subList, not the index in the backing List.

Any polymorphic algorithm that operates on a List, such as the replace and shuffle examples, works with the List returned by subList.

Here’s a polymorphic algorithm whose implementation uses subList to deal a hand from a deck. That is, it returns a new List (the “hand”) containing the specified number of elements taken from the end of the specified List (the “deck”). The elements returned in the hand are removed from the deck:

public static <E> List<E> dealHand(List<E> deck, int n) {
  int deckSize = deck.size();
  List<E> handView = deck.subList(deckSize - n, deckSize);
  List<E> hand = new ArrayList<E>(handView);
  handView.clear();
  return hand;
}

Note that this algorithm removes the hand from the end of the deck. For many common List implementations, such as ArrayList, the performance of removing elements from the end of the list is substantially better than that of removing elements from the beginning.

The following is a program^[19] that uses the dealHand method in combination with Collections.shuffle to generate hands from a normal 52-card deck. The program takes two command-line arguments: (1) the number of hands to deal and (2) the number of cards in each hand:

import java.util.*;

class Deal {
  public static void main(String[] args) {
    int numHands = Integer.parseInt(args[0]);
    int cardsPerHand = Integer.parseInt(args[1]);

    // Make a normal 52-card deck.
    String[] suit = new String[]
      {"spades", "hearts", "diamonds", "clubs"};
    String[] rank = new String[]
      {"ace","2","3","4","5","6","7","8",
           "9","10","jack","queen","king"};
    List<String> deck = new ArrayList<String>();
    for (int i = 0; i < suit.length; i++)
      for (int j = 0; j < rank.length; j++)
        deck.add(rank[j] + " of " + suit[i]);

    Collections.shuffle(deck);

    for (int i=0; i < numHands; i++)
      System.out.println(dealHand(deck, cardsPerHand));
  }
}

Running the program produces the following output:

% java Deal 4 5

[8 of hearts, jack of spades, 3 of spades, 4 of spades,
                                              king of diamonds]
[4 of diamonds, ace of clubs, 6 of clubs, jack of hearts,
                                               queen of hearts]
[7 of spades, 5 of spades, 2 of diamonds, queen of diamonds,
                                                    9 of clubs]
[8 of spades, 6 of diamonds, ace of spades, 3 of hearts,
                                                 ace of hearts]

Although the subList operation is extremely powerful, some care must be exercised when using it. The semantics of the List returned by subList become undefined if elements are added to or removed from the backing List in any way other than via the returned List. Thus, it’s highly recommended that you use the List returned by subList only as a transient object—to perform one or a sequence of range operations on the backing List. The longer you use the subList instance, the greater the probability that you’ll compromise it by modifying the backing List directly or through another subList object. Note that it is legal to modify a sublist of a sublist and to continue using the original sublist (though not concurrently).

Most polymorphic algorithms in the Collections class apply specifically to List. Having all these algorithms at your disposal makes it very easy to manipulate lists. Here’s a summary of these algorithms, which are described in more detail in the Algorithms section (page 355):

If you’ve used Hashtable, you’re already familiar with the general basics of Map. (Of course, Map is an interface, while Hashtable is a concrete implementation.) The following are the major differences:

Finally, Map fixes a minor deficiency in the Hashtable interface. Hashtable has a method called contains, which returns true if the Hashtable contains a given value. Given its name, you’d expect this method to return true if the Hashtable contained a given key, because the key is the primary access mechanism for a Hashtable. The Map interface eliminates this source of confusion by renaming the method containsValue. Also, this improves the interface’s consistency—containsValue parallels containsKey.

The basic operations of Map (put, get, containsKey, containsValue, size, and isEmpty) behave exactly like their counterparts in Hashtable. The following program^[26] generates a frequency table of the words found in its argument list. The frequency table maps each word to the number of times it occurs in the argument list:

import java.util.*;

public class Freq {
  public static void main(String[] args) {
    Map<String, Integer> m = new HashMap<String, Integer>();

    // Initialize frequency table from command line
    for (String a : args) {
      Integer freq = m.get(a);
      m.put(a, (freq == null) ? 1 : freq + 1);
    }

    System.out.println(m.size() + " distinct words:");
    System.out.println(m);
  }
}

The only tricky thing about this program is the second argument of the put statement. That argument is a conditional expression that has the effect of setting the frequency to one if the word has never been seen before or one more than its current value if the word has already been seen. Try running this program with the command:

java Freq if it is to be it is up to me to delegate

The program yields the following output:

8 distinct words:
{to=3, delegate=1, be=1, it=2, up=1, if=1, me=1, is=2}

Suppose you’d prefer to see the frequency table in alphabetical order. All you have to do is change the implementation type of the Map from HashMap to TreeMap. Making this four-character change causes the program to generate the following output from the same command line:

8 distinct words:
{be=1, delegate=1, if=1, is=2, it=2, me=1, to=3, up=1}

Similarly, you could make the program print the frequency table in the order the words first appear on the command line simply by changing the implementation type of the map to LinkedHashMap. Doing so results in the following output:

8 distinct words:
{if=1, it=2, is=2, to=3, be=1, up=1, me=1, delegate=1}

This flexibility provides a potent illustration of the power of an interface-based framework.

Like the Set and List interfaces, Map strengthens the requirements on the equals and hashCode methods so that two Map objects can be compared for logical equality without regard to their implementation types. Two Map instances are equal if they represent the same key-value mappings.

By convention, all general-purpose Map implementations provide constructors that take a Map object and initialize the new Map to contain all the key-value mappings in the specified Map. This standard Map conversion constructor is entirely analogous to the standard Collection constructor: It allows the caller to create a Map of a desired implementation type that initially contains all of the mappings in another Map, regardless of the other Map’s implementation type. For example, suppose you have a Map, named m. The following one-liner creates a new HashMap initially containing all of the same key-value mappings as m:

Map<K, V> copy = new HashMap<K, V>(m);

The clear operation does exactly what you would think it could do: It removes all the mappings from the Map. The putAll operation is the Map analogue of the Collection interface’s addAll operation. In addition to its obvious use of dumping one Map into another, it has a second, more subtle use. Suppose a Map is used to represent a collection of attribute-value pairs; the putAll operation, in combination with the Map conversion constructor, provides a neat way to implement attribute map creation with default values. The following is a static factory method that demonstrates this technique:

static <K, V> Map<K, V> newAttributeMap(
    Map<K, V>defaults, Map<K, V> overrides) {
  Map<K, V> result = new HashMap<K, V>(defaults);
  result.putAll(overrides);
  return result;
}

The Collection view methods allow a Map to be viewed as a Collection in these three ways:

The Collection views provide the only means to iterate over a Map. This example illustrates the standard idiom for iterating over the keys in a Map with a for-each construct:

for (KeyType key : m.keySet())
  System.out.println(key);

and with an iterator:

// Filter a map based on some property of its keys.
for (Iterator<Type> it = m.keySet().iterator(); it.hasNext(); )
  if (it.next().isBogus())
    it.remove();

The idiom for iterating over values is analogous. Following is the idiom for iterating over key-value pairs:

for (Map.Entry<KeyType, ValType> e : m.entrySet())
  System.out.println(e.getKey() + ": " + e.getValue());

At first, many people worry that these idioms may be slow because the Map has to create a new Collection instance each time a Collection view operation is called. Rest easy: There’s no reason that a Map cannot always return the same object each time it is asked for a given Collection view. This is precisely what all the Map implementations in java.util do.

With all three Collection views, calling an Iterator’s remove operation removes the associated entry from the backing Map, assuming that the backing Map supports element removal to begin with. This is illustrated by the preceding filtering idiom.

With the entrySet view, it is also possible to change the value associated with a key by calling a Map.Entry’s setValue method during iteration (again, assuming the Map supports value modification to begin with). Note that these are the only safe ways to modify a Map during iteration; the behavior is unspecified if the underlying Map is modified in any other way while the iteration is in progress.

The Collection views support element removal in all its many forms—remove, removeAll, retainAll, and clear operations, as well as the Iterator.remove operation. (Yet again, this assumes that the backing Map supports element removal.)

The Collection views do not support element addition under any circumstances. It would make no sense for the keySet and values views, and it’s unnecessary for the entrySet view, because the backing Map’s put and putAll methods provide the same functionality.

When applied to the Collection views, bulk operations (containsAll, removeAll, and retainAll) are surprisingly potent tools. For starters, suppose you want to know whether one Map is a submap of another—that is, whether the first Map contains all the key-value mappings in the second. The following idiom does the trick:

if (m1.entrySet().containsAll(m2.entrySet())) {
  ...
}

Along similar lines, suppose you want to know whether two Map objects contain mappings for all of the same keys:

if (m1.keySet().equals(m2.keySet())) {
  ...
}

Suppose you have a Map that represents a collection of attribute-value pairs, and two Sets representing required attributes and permissible attributes. (The permissible attributes include the required attributes.) The following snippet determines whether the attribute map conforms to these constraints and prints a detailed error message if it doesn’t:

static <K, V> boolean validate(Map<K, V> attrMap,
          Set<K> requiredAttrs, Set<K>permittedAttrs) {
  boolean valid = true;
  Set<K> attrs = attrMap.keySet();
  if (!attrs.containsAll(requiredAttrs)) {
    Set<K> missing = new HashSet<K>(requiredAttrs);
    missing.removeAll(attrs);
    System.out.println("Missing attributes: " + missing);
    valid = false;
  }
  if (!permittedAttrs.containsAll(attrs)) {
    Set<K> illegal = new HashSet<K>(attrs);
    illegal.removeAll(permittedAttrs);
    System.out.println("Illegal attributes: " + illegal);
    valid = false;
  }
  return valid;
}

Suppose you want to know all the keys common to two Map objects:

Set<KeyType>commonKeys = new HashSet<KeyType>(m1.keySet());
commonKeys.retainAll(m2.keySet());

A similar idiom gets you the common values.

All the idioms presented thus far have been nondestructive; that is, they don’t modify the backing Map. Here are a few that do. Suppose you want to remove all of the key-value pairs that one Map has in common with another:

m1.entrySet().removeAll(m2.entrySet());

Suppose you want to remove from one Map all of the keys that have mappings in another:

m1.keySet().removeAll(m2.keySet());

What happens when you start mixing keys and values in the same bulk operation? Suppose you have a Map, managers, that maps each employee in a company to the employee’s manager. We’ll be deliberately vague about the types of the key and the value objects. It doesn’t matter, as long as they’re the same. Now suppose you want to know who all the “individual contributors” (or nonmanagers) are. The following snippet tells you exactly what you want to know:

Set<Employee> individualContributors =
  new HashSet<Employee>(managers.keySet());
individualContributors.removeAll(managers.values());

Suppose you want to fire all the employees who report directly to some manager, Simon:

Employee simon = ... ;
managers.values().removeAll(Collections.singleton(simon));

Note that this idiom makes use of Collections.singleton, a static factory method that returns an immutable Set with the single, specified element.

Once you’ve done this, you may have a bunch of employees whose managers no longer work for the company (if any of Simon’s direct-reports were themselves managers). The following code will tell you which employees have managers who no longer work for the company.

Map<Employee, Employee> m =
  new HashMap<Employee, Employee>(managers);
m.values().removeAll(managers.keySet());
Set<Employee> slackers = m.keySet();

This example is a bit tricky. First, it makes a temporary copy of the Map, and it removes from the temporary copy all entries whose (manager) value is a key in the original Map. Remember that the original Map has an entry for each employee. Thus, the remaining entries in the temporary Map comprise all the entries from the original Map whose (manager) values are no longer employees. The keys in the temporary copy, then, represent precisely the employees that we’re looking for.

There are many more idioms like the ones contained in this section, but it would be impractical and tedious to list them all. Once you get the hang of it, it’s not that difficult to come up with the right one when you need it.

A multimap is like a Map but it can map each key to multiple values. The Java Collections Framework doesn’t include an interface for multimaps because they aren’t used all that commonly. It’s a fairly simple matter to use a Map whose values are List instances as a multimap. This technique is demonstrated in the next code example, which reads a word list containing one word per line (all lowercase) and prints out all the anagram groups that meet a size criterion. An anagram group is a bunch of words, all of which contain exactly the same letters but in a different order. The program takes two arguments on the command line: (1) the name of the dictionary file and (2) the minimum size of anagram group to print out. Anagram groups containing fewer words than the specified minimum are not printed.

There is a standard trick for finding anagram groups: For each word in the dictionary, alphabetize the letters in the word (that is, reorder the word’s letters into alphabetical order) and put an entry into a multimap, mapping the alphabetized word to the original word. For example, the word bad causes an entry mapping abd into bad to be put into the multimap. A moment’s reflection will show that all the words to which any given key maps form an anagram group. It’s a simple matter to iterate over the keys in the multimap, printing out each anagram group that meets the size constraint.

The following program^[27] is a straightforward implementation of this technique:

import java.util.*;
import java.io.*;

public class Anagrams {

  public static void main(String[] args) {
    int minGroupSize = Integer.parseInt(args[1]);

    // Read words from file and put into a simulated multimap
    Map<String, List<String>> m
      = new HashMap<String, List<String>>();
    try {
      Scanner s = new Scanner(new File(args[0]));
      while (s.hasNext()) {
        String word = s.next();
        String alpha = alphabetize(word);
        List<String> l = m.get(alpha);
        if (l == null)
          m.put(alpha, l=new ArrayList<String>());
        l.add(word);
      }
    } catch (IOException e) {
        System.err.println(e);
        System.exit(1);
    }

    // Print all permutation groups above size threshold
    for (List<String> l : m.values())
      if (l.size() >= minGroupSize)
        System.out.println(l.size() + ": " + l);
  }

  private static String alphabetize(String s) {
    char[] a = s.toCharArray();
    Arrays.sort(a);
    return new String(a);
  }
}

Running this program on a 173,000-word dictionary file with a minimum anagram group size of eight produces the following output:

9: [estrin, inerts, insert, inters, niters, nitres, sinter,
                                                triens, trines]
8: [lapse, leaps, pales, peals, pleas, salep, sepal, spale]
8: [aspers, parses, passer, prases, repass, spares, sparse,
                                                        spears]
10: [least, setal, slate, stale, steal, stela, taels, tales,
                                                  teals, tesla]
8: [enters, nester, renest, rentes, resent, tenser, ternes,
                                                        treens]
8: [arles, earls, lares, laser, lears, rales, reals, seral]
8: [earings, erasing, gainers, reagins, regains, reginas,
                                              searing, seringa]
8: [peris, piers, pries, prise, ripes, speir, spier, spire]
12: [apers, apres, asper, pares, parse, pears, prase, presa,
                                    rapes, reaps, spare, spear]
11: [alerts, alters, artels, estral, laster, ratels, salter,
                                slater, staler, stelar, talers]
9: [capers, crapes, escarp, pacers, parsec, recaps, scrape,
                                                secpar, spacer]
9: [palest, palets, pastel, petals, plates, pleats, septal,
                                                staple, tepals]
9: [anestri, antsier, nastier, ratines, retains, retinas,
                                     retsina, stainer, stearin]
8: [ates, east, eats, etas, sate, seat, seta, teas]
8: [carets, cartes, caster, caters, crates, reacts, recast,
                                                        traces]

Many of these words seem a bit bogus, but that’s not the program’s fault; they’re in the dictionary file^[28] we used. It is derived from the Public Domain ENABLE benchmark reference word list.^[29]

The Comparable interface consists of the following method:

public interface Comparable<T> {
  public int compareTo(T o);
}

The compareTo method compares the receiving object with the specified object and returns a negative integer, 0, or a positive integer depending on whether the receiving object is less than, equal to, or greater than the specified object. If the specified object cannot be compared to the receiving object, the method throws a ClassCastException.

The following class^[32] representing a person’s name implements Comparable:

import java.util.*;

public class Name implements Comparable<Name> {
  private final String firstName, lastName;

  public Name(String firstName, String lastName) {
    if (firstName == null || lastName == null)
      throw new NullPointerException();
    this.firstName = firstName;
    this.lastName = lastName;
  }

  public String firstName() { return firstName; }
  public String lastName()  { return lastName;  }

  public boolean equals(Object o) {
    if (!(o instanceof Name))
      return false;
    Name n = (Name)o;
    return n.firstName.equals(firstName) &&
                             n.lastName.equals(lastName);
  }
  public int hashCode() {
    return 31*firstName.hashCode() + lastName.hashCode();
  }
  public String toString() {
  return firstName + " " + lastName;
  }
  public int compareTo(Name n) {
    int lastCmp = lastName.compareTo(n.lastName);
    return (lastCmp != 0 ? lastCmp :
            firstName.compareTo(n.firstName));
  }
}

To keep the preceding example short, the class is somewhat limited: It doesn’t support middle names, it demands both a first and a last name, and it is not internationalized in any way. Nonetheless, it illustrates the following important points:

Since this section is about element ordering, let’s talk a bit more about Name’s compareTo method. It implements the standard name-ordering algorithm, where last names take precedence over first names. This is exactly what you want in a natural ordering. It would be very confusing indeed if the natural ordering were unnatural!

Take a look at how compareTo is implemented, because it’s quite typical. First, you compare the most significant part of the object (in this case, the last name). Often, you can just use the natural ordering of the part’s type. In this case, the part is a String and the natural (lexicographic) ordering is exactly what’s called for. If the comparison results in anything other than zero, which represents equality, you’re done: You just return the result. If the most significant parts are equal, you go on to compare the next mostsignificant parts. In this case, there are only two parts—first name and last name. If there were more parts, you’d proceed in the obvious fashion, comparing parts until you found two that weren’t equal or you were comparing the least-significant parts, at which point you’d return the result of the comparison.

Just to show that it all works, here’s a program that builds a list of names and sorts them:^[33]

import java.util.*;

public class NameSort {
  public static void main(String[] args) {
    Name nameArray[] = {
      new Name("John", "Lennon"),
      new Name("Karl", "Marx"),
      new Name("Groucho", "Marx"),
      new Name("Oscar", "Grouch")
    };
    List<Name> names = Arrays.asList(nameArray);
    Collections.sort(names);
    System.out.println(names);
  }
}

If you run this program, here’s what it prints:

[Oscar Grouch, John Lennon, Groucho Marx, Karl Marx]

There are four restrictions on the behavior of the compareTo method, which we won’t go into now because they’re fairly technical and boring and are better left in the API documentation. It’s really important that all classes that implement Comparable obey these restrictions, so read the documentation for Comparable if you’re writing a class that implements it. Attempting to sort a list of objects that violate the restrictions has undefined behavior. Technically speaking, these restrictions ensure that the natural ordering is a total order on the objects of a class that implements it; this is necessary to ensure that sorting is well defined.

What if you want to sort some objects in an order other than their natural ordering? Or what if you want to sort some objects that don’t implement Comparable? To do either of these things, you’ll need to provide a Comparator^[34]—an object that encapsulates an ordering. Like the Comparable interface, the Comparator interface consists of a single method:

public interface Comparator<T> {
  int compare(T o1, T o2);
}

The compare method compares its two arguments, returning a negative integer, 0, or a positive integer depending on whether the first argument is less than, equal to, or greater than the second. If either of the arguments has an inappropriate type for the Comparator, the compare method throws a ClassCastException.

Much of what was said about Comparable applies to Comparator as well. Writing a compare method is nearly identical to writing a compareTo method, except that the former gets both objects passed in as arguments. The compare method has to obey the same four technical restrictions as Comparable’s compareTo method for the same reason—a Comparator must induce a total order on the objects it compares.

Suppose you have a class called Employee, as follows:

public class Employee implements Comparable<Employee> {
  public Name name()     { ... }
  public int number()    { ... }
  public Date hireDate() { ... }
  ...
}

Let’s assume that the natural ordering of Employee instances is Name ordering (as defined in the previous example) on employee name. Unfortunately, the boss has asked for a list of employees in order of seniority. This means we have to do some work, but not much. The following program will produce the required list:

import java.util.*;
public class EmpSort {
  static final Comparator<Employee> SENIORITY_ORDER =
      new Comparator<Employee>() {
    public int compare(Employee e1, Employee e2) {
      return e2.hireDate().compareTo(e1.hireDate());
    }
  };

  // Employee database
  static final Collection<Employee> employees = ... ;

  public static void main(String[] args) {
    List<Employee>e = new ArrayList<Employee>(employees);
    Collections.sort(e, SENIORITY_ORDER);
    System.out.println(e);
  }
}

The Comparator in the program is reasonably straightforward. It relies on the natural ordering of Date applied to the values returned by the hireDate accessor method. Note that the Comparator passes the hire date of its second argument to its first rather than vice versa. The reason is that the employee who was hired most recently is the least senior; sorting in the order of hire date would put the list in reverse seniority order.

Another technique people sometimes use to achieve this effect is to maintain the argument order but to negate the result of the comparison:

// Don't do this!!
return -r1.hireDate().compareTo(r2.hireDate());

You should always use the former technique in favor of the latter because the latter is not guaranteed to work. The reason for this is that the compareTo method can return any negative int if its argument is less than the object on which it is invoked. There is one negative int that remains negative when negated, strange as it may seem:

-Integer.MIN_VALUE == Integer.MIN_VALUE

The Comparator in the preceding program works fine for sorting a List, but it does have one deficiency: It cannot be used to order a sorted collection, such as TreeSet, because it generates an ordering that is not compatible with equals. This means that this Comparator equates objects that the equals method does not. In particular, any two employees who were hired on the same date will compare as equal. When you’re sorting a List, this doesn’t matter; but when you’re using the Comparator to order a sorted collection, it’s fatal. If you use this Comparator to insert multiple employees hired on the same date into a TreeSet, only the first one will be added to the set; the second will be seen as a duplicate element and will be ignored.

To fix this problem, simply tweak the Comparator so that it produces an ordering that is compatible with equals. In other words, tweak it so that the only elements seen as equal when using compare are those that are also seen as equal when compared using equals. The way to do this is to perform a two-part comparison (as for Name), where the first part is the one we’re interested in—in this case, the hire date—and the second part is an attribute that uniquely identifies the object. Here the employee number is the obvious attribute. This is the Comparator that results:

static final Comparator<Employee> SENIORITY_ORDER =
                             new Comparator<Employee>() {
  public int compare(Employee e1, Employee e2) {
    int dateCmp = e2.hireDate().compareTo(e1.hireDate());
    if (dateCmp != 0)
      return dateCmp;
    return (e1.number() < e2.number() ? -1 :
      (e1.number() == e2.number() ? 0 : 1));
  }
};

One last note: You might be tempted to replace the final return statement in the Comparator with the simpler:

return e1.number() - e2.number();

Don’t do it unless you’re absolutely sure no one will ever have a negative employee number! This trick does not work in general because the signed integer type is not big enough to represent the difference of two arbitrary signed integers. If i is a large positive integer and j is a large negative integer, i - j will overflow and will return a negative integer. The resulting comparator violates one of the four technical restrictions we keep talking about (transitivity) and produces horrible, subtle bugs. This is not a purely theoretical concern; people get burned by it.

The operations that SortedSet inherits from Set behave identically on sorted sets and normal sets with two exceptions:

Although the interface doesn’t guarantee it, the toString method of the Java platform’s SortedSet implementations returns a string containing all the elements of the sorted set, in order.

By convention, all general-purpose Collection implementations provide a standard conversion constructor that takes a Collection; SortedSet implementations are no exception. In TreeSet, this constructor creates an instance that sorts its elements according to their natural ordering. This was probably a mistake. It would have been better to check dynamically to see whether the specified collection was a SortedSet instance and, if so, to sort the new TreeSet according to the same criterion (comparator or natural ordering). Because TreeSet took the approach that it did, it also provides a constructor that takes a SortedSet and returns a new TreeSet containing the same elements sorted according to the same criterion. Note that it is the compile-time type of the argument, not its runtime type, that determines which of these two constructors is invoked (and whether the sorting criterion is preserved).

SortedSet implementations also provide, by convention, a constructor that takes a Comparator and returns an empty set sorted according to the specified Comparator. If null is passed to this constructor, it returns a set that sorts its elements according to their natural ordering.

The range-view operations are somewhat analogous to those provided by the List interface, but there is one big difference. Range views of a sorted set remain valid even if the backing sorted set is modified directly. This is feasible because the endpoints of a range view of a sorted set are absolute points in the element space rather than specific elements in the backing collection, as is the case for lists. A range view of a sorted set is really just a window onto whatever portion of the set lies in the designated part of the element space. Changes to the range view write back to the backing sorted set and vice versa. Thus, it’s okay to use range views on sorted sets for long periods of time, unlike range views on lists.

Sorted sets provide three range-view operations. The first, subSet, takes two endpoints, like subList. Rather than indices, the endpoints are objects and must be comparable to the elements in the sorted set, using the Set’s Comparator or the natural ordering of its elements, whichever the Set uses to order itself. Like subList, the range is half open, including its low endpoint but excluding the high one.

Thus, the following line of code tells you how many words between "doorbell" and "pickle", including "doorbell" but excluding "pickle", are contained in a SortedSet of strings called dictionary:

int count = dictionary.subSet("doorbell", "pickle").size();

In like manner, the following one-liner removes all the elements beginning with the letter f:

dictionary.subSet("f", "g").clear();

A similar trick can be used to print a table telling you how many words begin with each letter:

for (char ch = 'a'; ch <= 'z'; ) {
  String from = String.valueOf(ch++);
  String to = String.valueOf(ch);
  System.out.println(from + ": " +
                     dictionary.subSet(from, to).size());
}

Suppose you want to view a closed interval, which contains both of its endpoints, instead of an open interval. If the element type allows for the calculation of the successor of a given value in the element space, merely request the subSet from lowEndpoint to successor(highEndpoint). Although it isn’t entirely obvious, the successor of a string s in String’s natural ordering is s + ""—that is, s with a null character appended.

Thus, the following one-liner tells you how many words between "doorbell" and "pickle", including doorbell and pickle, are contained in the dictionary:

count = dictionary.subSet("doorbell", "pickle").size();

A similar technique can be used to view an open interval, which contains neither endpoint. The open-interval view from lowEndpoint to highEndpoint is the half-open interval from successor(lowEndpoint) to highEndpoint. Use the following to calculate the number of words between "doorbell" and "pickle", excluding both:

count = dictionary.subSet("doorbell", "pickle").size();

The SortedSet interface contains two more range-view operations—headSet and tailSet, both of which take a single Object argument. The former returns a view of the initial portion of the backing SortedSet, up to but not including the specified object. The latter returns a view of the final portion of the backing SortedSet, beginning with the specified object and continuing to the end of the backing SortedSet. Thus, the following code allows you to view the dictionary as two disjoint volumes (a-m and n-z):

SortedSet<String> volume1 = dictionary.headSet("n");
SortedSet<String> volume2 = dictionary.tailSet("n");

The SortedSet interface contains operations to return the first and last elements in the sorted set, not surprisingly called first and last. In addition to their obvious uses, last allows a workaround for a deficiency in the SortedSet interface. One thing you’d like to do with a SortedSet is to go into the interior of the Set and iterate forward or backward. It’s easy enough to go forward from the interior: Just get a tailSet and iterate over it. Unfortunately, there’s no easy way to go backward.

The following idiom obtains the first element that is less than a specified object o in the element space:

Object predecessor = ss.headSet(o).last();

This is a fine way to go one element backward from a point in the interior of a sorted set. It could be applied repeatedly to iterate backward, but this is very inefficient, requiring a lookup for each element returned.

The SortedSet interface contains an accessor method called comparator that returns the Comparator used to sort the set, or null if the set is sorted according to the natural ordering of its elements. This method is provided so that sorted sets can be copied into new sorted sets with the same ordering. It is used by the SortedSet constructor described previously in the Standard Constructors section (page 336).

The operations SortedMap inherits from Map behave identically on sorted maps and normal maps with two exceptions:

Although it isn’t guaranteed by the interface, the toString method of the Collection views in all the Java platform’s SortedMap implementations returns a string containing all the elements of the view, in order.

By convention, all general-purpose Map implementations provide a standard conversion constructor that takes a Map; SortedMap implementations are no exception. In TreeMap, this constructor creates an instance that orders its entries according to their keys’ natural ordering. This was probably a mistake. It would have been better to check dynamically to see whether the specified Map instance was a SortedMap and, if so, to sort the new map according to the same criterion (comparator or natural ordering). Because TreeMap took the approach it did, it also provides a constructor that takes a SortedMap and returns a new TreeMap containing the same mappings as the given SortedMap, sorted according to the same criterion. Note that it is the compile-time type of the argument, not its runtime type, that determines whether the SortedMap constructor is invoked in preference to the ordinary map constructor.

SortedMap implementations also provide, by convention, a constructor that takes a Comparator and returns an empty map sorted according to the specified Comparator. If null is passed to this constructor, it returns a Set that sorts its mappings according to their keys’ natural ordering.

Because this interface is a precise Map analog of SortedSet, all the idioms and code examples in The SortedSet Interface section (page 335) apply to SortedMap with only trivial modifications.

You can find answers to these Questions and Exercises at:

tutorial/collections/interfaces/QandE/answers.html

There are three general-purpose Set implementations—HashSet, TreeSet, and LinkedHashSet. Which of these three to use is generally straightforward. HashSet is much faster than TreeSet (constant-time versus log-time for most operations) but offers no ordering guarantees. If you need to use the operations in the SortedSet interface, or if value-ordered iteration is required, use TreeSet; otherwise, use HashSet. It’s a fair bet that you’ll end up using HashSet most of the time.

LinkedHashSet is in some sense intermediate between HashSet and TreeSet. Implemented as a hash table with a linked list running through it, it provides insertion-ordered iteration (least recently inserted to most recently) and runs nearly as fast as HashSet. The LinkedHashSet implementation spares its clients from the unspecified, generally chaotic ordering provided by HashSet without incurring the increased cost associated with TreeSet.

One thing worth keeping in mind about HashSet is that iteration is linear in the sum of the number of entries and the number of buckets (the capacity). Thus, choosing an initial capacity that’s too high can waste both space and time. On the other hand, choosing an initial capacity that’s too low wastes time by copying the data structure each time it’s forced to increase its capacity. If you don’t specify an initial capacity, the default is 16. In the past, there was some advantage to choosing a prime number as the initial capacity. This is no longer true. Internally, the capacity is always rounded up to a power of two. The initial capacity is specified by using the int constructor. The following line of code allocates a HashSet whose initial capacity is 64:

Set<String> s = new HashSet<String>(64);

The HashSet class has one other tuning parameter called the load factor. If you care a lot about the space consumption of your HashSet, read the HashSet documentation for more information. Otherwise, just accept the default; it’s almost always the right thing to do.

If you accept the default load factor but want to specify an initial capacity, pick a number that’s about twice the size to which you expect the set to grow. If your guess is way off, you may waste a bit of space, time, or both, but it’s unlikely to be a big problem.

LinkedHashSet has the same tuning parameters as HashSet, but iteration time is not affected by capacity. TreeSet has no tuning parameters.

There are two special-purpose Set implementations—EnumSet^[39] and CopyOnWrite-ArraySet.^[40]

EnumSet is a high-performance Set implementation for enum types. All of the members of an enum set must be of the same enum type. Internally, it is represented by a bitvector, typically a single long. Enum sets support iteration over ranges of enum types. For example, given the enum declaration for the days of the week, you can iterate over the weekdays. The EnumSet class provides a static factory that makes it easy:

for (Day d : EnumSet.range(Day.MONDAY, Day.FRIDAY))
  System.out.println(d);

Enum sets also provide a rich, typesafe replacement for traditional bit flags:

EnumSet.of(Style.BOLD, Style.ITALIC)

CopyOnWriteArraySet is a Set implementation backed up by a copy-on-write array. All mutative operations, such as add, set, and remove, are implemented by making a new copy of the array; no locking is ever required. Even iteration may safely proceed concurrently with element insertion and deletion. Unlike most Set implementations, the add, remove, and contains methods require time proportional to the size of the set. This implementation is only appropriate for sets that are rarely modified but frequently iterated. It is well suited to maintaining event-handler lists that must prevent duplicates.

There are two general-purpose List implementations—ArrayList and LinkedList. Most of the time you’ll probably use ArrayList, which offers constant-time positional access and is just plain fast. It does not have to allocate a node object for each element in the List, and it can take advantage of System.arraycopy when it has to move multiple elements at the same time. Think of ArrayList as Vector without the synchronization overhead.

If you frequently add elements to the beginning of the List or iterate over the List to delete elements from its interior, you should consider using LinkedList. These operations require constant-time in a LinkedList and linear-time in an ArrayList. But you pay a big price in performance. Positional access requires linear-time in a LinkedList and constant-time in an ArrayList. Furthermore, the constant factor for LinkedList is much worse. If you think you want to use a LinkedList, measure the performance of your application with both LinkedList and ArrayList before making your choice; ArrayList is usually faster.

ArrayList has one tuning parameter—the initial capacity, which refers to the number of elements the ArrayList can hold before it has to grow. LinkedList has no tuning parameters and seven optional operations, one of which is clone. The other six are addFirst, getFirst, removeFirst, addLast, getLast, and removeLast. LinkedList also implements the Queue interface.

CopyOnWriteArrayList^[41] is a List implementation backed up by a copy-on-write array. This implementation is similar in nature to CopyOnWriteArraySet. No synchronization is necessary, even during iteration, and iterators are guaranteed never to throw ConcurrentModificationException. This implementation is well suited to maintaining event-handler lists, in which change is infrequent, and traversal is frequent and potentially time-consuming.

If you need synchronization, a Vector will be slightly faster than an ArrayList synchronized with Collections.synchronizedList. But Vector has loads of legacy operations, so be careful to always manipulate the Vector with the List interface or else you won’t be able to replace the implementation at a later time.

If your List is fixed in size—that is, you’ll never use remove, add, or any of the bulk operations other than containsAll—you have a third option that’s definitely worth considering. See Arrays.asList in the Convenience Implementations section (page 352) for more information.

The three general-purpose Map implementations are HashMap, TreeMap, and LinkedHashMap. If you need SortedMap operations or key-ordered Collection-view iteration, use TreeMap; if you want maximum speed and don’t care about iteration order, use HashMap; if you want near-HashMap performance and insertion-order iteration, use LinkedHashMap. In this respect, the situation for Map is analogous to Set. Likewise, everything else in The Set Interface section (page 301) also applies to Map implementations.

LinkedHashMap provides two capabilities that are not available with LinkedHashSet. When you create a LinkedHashMap, you can order it based on key access rather than insertion. In other words, merely looking up the value associated with a key brings that key to the end of the map. Also, LinkedHashMap provides the removeEldestEntry method, which may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map. This makes it very easy to implement a custom cache.

For example, this override will allow the map to grow up to as many as 100 entries, and then it will delete the eldest entry each time a new entry is added, maintaining a steady state of 100 entries:

private static final int MAX_ENTRIES = 100;

protected boolean removeEldestEntry(Map.Entry eldest) {
  return size() > MAX_ENTRIES;
}

There are three special-purpose Map implementations—EnumMap,^[42] WeakHashMap,^[43] and IdentityHashMap.^[44] EnumMap, which is internally implemented as an array, is a high-performance Map implementation for use with enum keys. This implementation combines the richness and safety of the Map interface with a speed approaching that of an array. If you want to map an enum to a value, you should always use an EnumMap rather than an array.

WeakHashMap is an implementation of the Map interface that stores only weak references to its keys. Storing only weak references allows a key-value pair to be garbagecollected when its key is no longer referenced outside of the WeakHashMap. This class provides the easiest way to harness the power of weak references. It is useful for implementing “registry-like” data structures, where the utility of an entry vanishes when its key is no longer reachable by any thread.

IdentityHashMap is an identity-based Map implementation based on a hash table. This class is useful for topology-preserving object graph transformations, such as serialization or deep-copying. To perform such transformations, you need to maintain an identity-based “node table” that keeps track of which objects have already been seen. Identity-based maps are also used to maintain object-to-meta-information mappings in dynamic debuggers and similar systems. Finally, identity-based maps are useful in thwarting “spoof attacks” that are a result of intentionally perverse equals methods because IdentityHashMap never invokes the equals method on its keys. An added benefit of this implementation is that it is fast.

The java.util.concurrent^[45] package contains the ConcurrentMap^[46] interface, which extends Map with atomic putIfAbsent, remove, and replace methods, and the ConcurrentHashMap^[47] implementation of that interface.

ConcurrentHashMap is a highly concurrent, high-performance implementation backed up by a hash table. This implementation never blocks when performing retrievals and allows the client to select the concurrency level for updates. It is intended as a drop-in replacement for Hashtable: In addition to implementing ConcurrentMap, it supports all the legacy methods peculiar to Hashtable. Again, if you don’t need the legacy operations, be careful to manipulate it with the ConcurrentMap interface.

As mentioned in the previous section, LinkedList implements the Queue interface, providing FIFO queue operations for add, poll, and so on.

The PriorityQueue class is a priority queue based on the heap data structure. This queue orders elements according to an order specified at construction time, which can be the elements’ natural ordering or the ordering imposed by an explicit Comparator.

The queue retrieval operations—poll, remove, peek, and element—access the element at the head of the queue. The head of the queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements; ties are broken arbitrarily.

PriorityQueue and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The iterator provided in method iterator is not guaranteed to traverse the elements of the PriorityQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

The java.util.concurrent package contains a set of synchronized Queue interfaces and classes. BlockingQueue extends Queue with operations that wait for the queue to become nonempty when retrieving an element and for space to become available in the queue when storing an element. This interface is implemented by the following classes:

The synchronization wrappers add automatic synchronization (thread-safety) to an arbitrary collection. Each of the six core collection interfaces—Collection, Set, List, Map, SortedSet, and SortedMap—has one static factory method:

public static <T> Collection<T>
  synchronizedCollection(Collection<T> c);
public static <T> Set<T>
  synchronizedSet(Set<T> s);
public static <T> List<T>
  synchronizedList(List<T> list);
public static <K,V> Map<K,V>
  synchronizedMap(Map<K,V> m);
public static <T> SortedSet<T>
  synchronizedSortedSet(SortedSet<T> s);
public static <K,V> SortedMap<K,V>
  synchronizedSortedMap(SortedMap<K,V> m);

Each of these methods returns a synchronized (thread-safe) Collection backed up by the specified collection. To guarantee serial access, all access to the backing collection must be accomplished through the returned collection. The easy way to guarantee this is not to keep a reference to the backing collection. Create the synchronized collection with the following trick:

List<Type> list =
  Collections.synchronizedList(new ArrayList<Type>());

A collection created in this fashion is every bit as thread-safe as a normally synchronized collection, such as a Vector.

In the face of concurrent access, it is imperative that the user manually synchronize on the returned collection when iterating over it. The reason is that iteration is accomplished via multiple calls into the collection, which must be composed into a single atomic operation. The following is the idiom to iterate over a wrapper-synchronized collection:

Collection<Type> c =
  Collections.synchronizedCollection(myCollection);
synchronized(c) {
  for (Type e : c)
    foo(e);
}

If an explicit iterator is used, the iterator method must be called from within the synchronized block. Failure to follow this advice may result in nondeterministic behavior. The idiom for iterating over a Collection view of a synchronized Map is similar. It is imperative that the user synchronize on the synchronized Map when iterating over any of its Collection views rather than synchronizing on the Collection view itself, as shown in the following example:

Map<KeyType, ValType> m =
  Collections.synchronizedMap(new HashMap<KeyType, ValType>());
  ...
Set<KeyType> s = m.keySet();
  ...
synchronized(m) { // Synchronizing on m, not s!
  while (KeyType k : s)
    foo(k);
}

One minor downside of using wrapper implementations is that you do not have the ability to execute any noninterface operations of a wrapped implementation. So, for instance, in the preceding List example, you cannot call ArrayList’s ensureCapacity operation on the wrapped ArrayList.

Unlike synchronization wrappers, which add functionality to the wrapped collection, the unmodifiable wrappers take functionality away. In particular, they take away the ability to modify the collection by intercepting all the operations that would modify the collection and throwing an UnsupportedOperationException. Unmodifiable wrappers have two main uses, as follows:

Like synchronization wrappers, each of the six core Collection interfaces has one static factory method:

public static <T> Collection<T>
  unmodifiableCollection(Collection<? extends T> c);
public static <T> Set<T>
  unmodifiableSet(Set<? extends T> s);
public static <T> List<T>
  unmodifiableList(List<? extends T> list);
public static <K,V> Map<K, V>
  unmodifiableMap(Map<? extends K, ? extends V> m);
public static <T> SortedSet<T>
  unmodifiableSortedSet(SortedSet<? extends T> s);
public static <K,V> SortedMap<K, V>
  unmodifiableSortedMap(SortedMap<K, ? extends V> m);

The Collections.checked interface wrappers are provided for use with generic collections. These implementations return a dynamically type-safe view of the specified collection, which throws a ClassCastException if a client attempts to add an element of the wrong type. The generics mechanism in the language provides compile-time (static) type-checking, but it is possible to defeat this mechanism. Dynamically type-safe views eliminate this possibility entirely.

The Arrays.asList method returns a List view of its array argument. Changes to the List write through to the array and vice versa. The size of the collection is that of the array and cannot be changed. If the add or the remove method is called on the List, an UnsupportedOperationException will result.

The normal use of this implementation is as a bridge between array-based and collection-based APIs. It allows you to pass an array to a method expecting a Collection or a List. However, this implementation also has another use. If you need a fixed-size List, it’s more efficient than any general-purpose List implementation. This is the idiom:

List<String> list = Arrays.asList(new String[size]);

Note that a reference to the backing array is not retained.

Occasionally you’ll need an immutable List consisting of multiple copies of the same element. The Collections.nCopies method returns such a list. This implementation has two main uses. The first is to initialize a newly created List; for example, suppose you want an ArrayList initially consisting of 1,000 null elements. The following incantation does the trick:

List<Type> list =
  new ArrayList<Type>(Collections.nCopies(1000, (Type)null);

Of course, the initial value of each element need not be null. The second main use is to grow an existing List. For example, suppose you want to add 69 copies of the string "fruit bat" to the end of a List<String>. It’s not clear why you’d want to do such a thing, but let’s just suppose you did. The following is how you’d do it:

lovablePets.addAll(Collections.nCopies(69, "fruit bat"));

By using the form of addAll that takes both an index and a Collection, you can add the new elements to the middle of a List instead of to the end of it.

Sometimes you’ll need an immutable singleton Set, which consists of a single, specified element. The Collections.singleton method returns such a Set. One use of this implementation is to remove all occurrences of a specified element from a Collection:

c.removeAll(Collections.singleton(e));

A related idiom removes all elements that map to a specified value from a Map. For example, suppose you have a Map—job—that maps people to their line of work and suppose you want to eliminate all the lawyers. The following one-liner will do the deed:

job.values().removeAll(Collections.singleton(LAWYER));

One more use of this implementation is to provide a single input value to a method that is written to accept a collection of values.

The Collections class provides methods to return the empty Set, List, and Map—emptySet, emptyList, and emptyMap. The main use of these constants is as input to methods that take a Collection of values when you don’t want to provide any values at all, as in this example:

tourist.declarePurchases(Collections.emptySet());

You can find answers to these Questions and Exercises at:

tutorial/collections/implementations/QandE/answers.html

Suppose that you’re using an API that returns legacy collections in tandem with another API that requires objects implementing the collection interfaces. To make the two APIs interoperate smoothly, you’ll have to transform the legacy collections into modern collections. Luckily, the Java Collections Framework makes this easy.

Suppose the old API returns an array of objects and the new API requires a Collection. The Collections Framework has a convenience implementation that allows an array of objects to be viewed as a List. You use Arrays.asList to pass an array to any method requiring a Collection or a List:

Foo[] result = oldMethod(arg);
newMethod(Arrays.asList(result));

If the old API returns a Vector or a Hashtable, you have no work to do at all because Vector was retrofitted to implement the List interface and Hashtable was retrofitted to implement Map. Therefore, a Vector may be passed directly to any method calling for a Collection or a List:

Vector result = oldMethod(arg);
newMethod(result);

Similarly, a Hashtable may be passed directly to any method calling for a Map:

Hashtable result = oldMethod(arg);
newMethod(result);

Less frequently, an API may return an Enumeration that represents a collection of objects. The Collections.list method translates an Enumeration into a Collection:

Enumeration e = oldMethod(arg);
newMethod(Collections.list(e));

Suppose you’re using an API that returns modern collections in tandem with another API that requires you to pass in legacy collections. To make the two APIs interoperate smoothly, you have to transform modern collections into old collections. Again, the Java Collections Framework makes this easy.

Suppose the new API returns a Collection and the old API requires an array of Object. As you’re probably aware, the Collection interface contains a toArray method designed expressly for this situation:

Collection c = newMethod();
oldMethod(c.toArray());

What if the old API requires an array of String (or another type) instead of an array of Object? You just use the other form of toArray—the one that takes an array on input:

Collection c = newMethod();
oldMethod((String[]) c.toArray(new String[0]));

If the old API requires a Vector, the standard collection constructor comes in handy:

Collection c = newMethod();
oldMethod(new Vector(c));

The case where the old API requires a Hashtable is handled analogously:

Map m = newMethod();
oldMethod(new Hashtable(m));

Finally, what do you do if the old API requires an Enumeration? This case isn’t common, but it does happen from time to time, and the Collections.enumeration method was provided to handle it. This is a static factory method that takes a Collection and returns an Enumeration over the elements of the Collection:

Collection c = newMethod();
oldMethod(Collections.enumeration(c));

If your API contains a method that requires a collection on input, it is of paramount importance that you declare the relevant parameter type to be one of the collection interface types (see the Interfaces section, page 295). Never use an implementation (see the Implementations section, page 342) type because this defeats the purpose of an interface-based Collections Framework, which is to allow collections to be manipulated without regard to implementation details.

Further, you should always use the least-specific type that makes sense. For example, don’t require a List (see The List Interface section, page 306) or a Set (see The Set Interface section, page 301) if a Collection (see The Collection Interface section, page 298) would do. It’s not that you should never require a List or a Set on input; it is correct to do so if a method depends on a property of one of these interfaces. For example, many of the algorithms provided by the Java platform require a List on input because they depend on the fact that lists are ordered. As a general rule, however, the best types to use on input are the most general: Collection and Map.

You can afford to be much more flexible with return values than with input parameters. It’s fine to return an object of any type that implements or extends one of the collection interfaces. This can be one of the interfaces or a special-purpose type that extends or implements one of these interfaces.

For example, one could imagine an image-processing package, called ImageList, that returned objects of a new class that implements List. In addition to the List operations, ImageList could support any application-specific operations that seemed desirable. For example, it might provide an indexImage operation that returned an image containing thumbnail images of each graphic in the ImageList. It’s critical to note that even if the API furnishes ImageList instances on output, it should accept arbitrary Collection (or perhaps List) instances on input.

In one sense, return values should have the opposite behavior of input parameters: It’s best to return the most specific applicable collection interface rather than the most general. For example, if you’re sure that you’ll always return a SortedMap, you should give the relevant method the return type of SortedMap rather than Map. SortedMap instances are more time-consuming to build than ordinary Map instances and are also more powerful. Given that your module has already invested the time to build a SortedMap, it makes good sense to give the user access to its increased power. Furthermore, the user will be able to pass the returned object to methods that demand a SortedMap, as well as those that accept any Map.

There are currently plenty of APIs out there that define their own ad hoc collection types. While this is unfortunate, it’s a fact of life given that there was no Collections Framework in the first two major releases of the Java platform. If you own one of these APIs, here’s what you can do about it.

If possible, retrofit your legacy collection type to implement one of the standard collection interfaces. Then all the collections you return will interoperate smoothly with other collection-based APIs. If this is impossible (for example, because one or more of the preexisting type signatures conflict with the standard collection interfaces), define an adapter class that wraps one of your legacy collections objects, allowing it to function as a standard collection. (The Adapter class is an example of a custom implementation; see the Custom Collection Implementations section, page 360.)

Retrofit your API with new calls that follow the input guidelines to accept objects of a standard collection interface, if possible. Such calls can coexist with the calls that take the legacy collection type. If this is impossible, provide a constructor or static factory for your legacy type that takes an object of one of the standard interfaces and returns a legacy collection containing the same elements (or mappings). Either of these approaches will allow users to pass arbitrary collections into your API.