Core Java 2, Volume II - Chapter 2: Collections

Print-friendly Version

Books Index

Whenever you add an object to a map, you must supply a key as well. In our case, the key is a string, and the corresponding value is an Employee object. To retrieve an object, you must use (and, therefore, remember) the key.

String s = "1411-16-2536";
e = (Employee)staff.get(s); 
// gets harry

If no information is stored in the map with the particular key specified, then get returns null.

Keys must be unique. You cannot store two values with the same key. If you call the put method twice with the same key, then the second value replaces the first one. In fact, put returns the previous value stored with the key parameter. (This feature is useful; if put returns a non-null value, then you know you replaced a previous entry.)

The remove() method removes an element from the map. The size() method returns the number of entries in the map.

The collections framework does not consider a map itself as a collection. (Other frameworks for data structures consider a map as a collection of pairs, or as a collection of values that is indexed by the keys.) However, you can obtain views of the map, objects that implement the Collection interface or one of its subinterfaces.

There are three views: the set of keys, the collection of values (which is not a set), and the set of key/value pairs. The keys and key/value pairs form a set because there can be only one copy of a key in a map. The methods

Set keySet()
Collection values()
Set entrySet()

return these three views. (The elements of the entry set are objects of the inner class Map.Entry.)

Note that the keySet is not a HashSet or TreeSet, but it is an object of some other class that implements the Set interface. We discuss the Set interface and its purpose in detail in the next section. The Set interface extends the Collection interface. In fact, as you will see, it does not add any new methods. Therefore, you can use it exactly as you use the Collection interface.

For example, you can enumerate all keys of a map:

Set keys = map.keySet();
Iterator iter = keys.iterator();
while (iter.hasNext())
{  Object key = iter.next();
   do something with key
} 

TIP: If you want to look at both keys and values, then you can avoid value lookups by enumerating the entries. Use the following code skeleton:

Set entries = staff.entrySet();
Iterator iter = entries.iterator();
while (iter.hasNext())
{  Map.Entry entry = (
             Map.Entry)iter.next();
   Object key = entry.getKey();
   Object value = entry.getValue();
   do something with key, value
}

If you invoke the remove method of the iterator, you actually remove the key and its associated value from the map. However, you cannot add an element to the key set view. It makes no sense to add a key without also adding a value. If you try to invoke the add method, it throws an UnsupportedOperationException. The key/value set view has the same restriction, even though it would make conceptual sense to add a new key/value pair.

Example 2-4 illustrates a map at work. We first add key/value pairs to a map. Then, we remove one key from the map, which removes its associated value as well. Next, we change the value that is associated with a key and call the get method to look up a value. Finally, we iterate through the entry set.

Example 2-4: MapTest.java

import java.util.*;

public class MapTest
{  public static void main(
                       String[] args)
   {  Map staff = new HashMap();
      staff.put("144-25-5464", 
         new Employee("Angela Hung"));
      staff.put("567-24-2546", 
        new Employee("Harry Hacker"));
      staff.put("157-62-7935", 
         new Employee("Gary Cooper"));
      staff.put("456-62-5527", 
       new Employee("Francesca Cruz"));

      // print all entries
      
      System.out.println(staff);
      
      // remove an entry

      staff.remove("567-24-2546");

      // replace an entry
      
      staff.put("456-62-5527", 
        new Employee("Francesca Miller"));

      // look up a value

      System.out.println(
               staff.get("157-62-7935"));

      // iterate through all entries

      Set entries = staff.entrySet();
      Iterator iter = entries.iterator();
      while (iter.hasNext())
      {  Map.Entry entry = 
               (Map.Entry)iter.next();
         Object key = entry.getKey();
         Object value = entry.getValue();
         System.out.println(
           "key=" + key + ", value=" +
                                value);
      }
   }
}

class Employee
{  public Employee(String n)
   {  name = n;
      salary = 0;
   }

   public String toString()
   {  return "[name=" + name + ", 
          salary=" + salary + "]";
   }

   public void setSalary(double s)
   {  salary = s;
   }

   private String name;
   private double salary;
}

Weak Hash Maps

The WeakHashMap class was designed to solve an interesting problem. What happens with a value whose key is no longer used anywhere in your program? Suppose the last reference to a key has gone away. Then, there is no longer any way to refer to the value object. But since no part of the program has the key any more, the key/value pair cannot be removed from the map. Why can't the garbage collector remove it? Isn't it the job of the garbage collector to remove unused objects?

Unfortunately, it isn't quite so simple. The garbage collector traces live objects. As long as the map object is live, then all buckets in it are live and they won't be reclaimed. Thus, your program should take care to remove unused values from long-lived maps. Or, you can use aWeakHashMapinstead. This data structure cooperates with the garbage collector to remove key/value pairs when the only reference to the key is the one from the hash table entry.

Here are the inner workings of this mechanism. TheWeakHashMapuses weak references to hold keys. AWeakReferenceobject holds a reference to another object, in our case, a hash table key. Objects of this type are treated in a special way by the garbage collector. Normally, if the garbage collector finds that a particular object has no references to it, it simply reclaims the object. However, if the object is reachable only by a WeakReference, the garbage collector still reclaims the object, but it places the weak reference that led to it onto a queue. The operations of theWeakHashMapperiodically check that queue for newly arrived weak references. When a weak reference arrives in the queue, this is an indication that the key was no longer used by anyone and that it has been collected. TheWeakHashMapthen removes the associated entry.

java.util.Map

• Object get(Object key)
  gets the value associated with the key; returns the object associated with the key, or null if the key is not found in the map.
  Parameters: key the key to use for retrieval (may be null)
• Object put(Object key, Object value)
  puts the association of a key and a value into the map. If the key is already present, the new object replaces the old one previously associated with the key. This method returns the old value of the key, or null if the key was not previously present. Parameters: key the key to use for retrieval (may be null)
  value the associated object (may not be null)
• void putAll(Map entries)
  adds all entries from the specified map to this map. Parameters: entries the map with the entries to be added
• boolean containsKey(Object key)
  returns true if the key is present in the map.
  Parameters: key the key to find
• boolean containsValue(Object value)
  returns true if the value is present in the map.
  Parameters: value the value to find
• Set entrySet()
  returns a set view of Map.Entry objects, the key/value pairs in the map. You can remove elements from this set, and they are removed from the map, but you cannot add any elements.
• Set keySet()
  returns a set view of all keys in the map. You can remove elements from this set, and the key and associated values are removed from the map, but you cannot add any elements.
• Collection values()
  returns a collection view of all values in the map. You can remove elements from this set, and the removed value and its key are removed from the map, but you cannot add any elements.

java.util.Map.Entry

• Object getKey()


• Object getValue()
  return the key or value of this entry.
• Object setValue(Object value)
  changes the value in the associated map to the new value and returns the old value. Parameters: value the new value to associate with the key

java.util.HashMap

• HashMap()
  constructs an empty hash map.
• HashMap(Map entries)
  constructs a hash map and adds all entries from a map.
  Parameters: entries the entries to add
• HashMap(int initialCapacity)


• HashMap(int initialCapacity, float loadFactor)
  construct an empty hash map with the specified capacity and load factor. Parameters: initialCapacity the initial number of buckets loadFactor a number between 0.0 and 1.0 that determines at what percentage of fullness the hash table will be rehashed into a larger one. The default is 0.75

java.util.WeakHashMap

• WeakHashMap()
  constructs an empty weak hash map.
• WeakHashMap(int initialCapacity)


• WeakHashMap(int initialCapacity, float loadFactor)
  construct an empty hash map with the specified capacity and load factor.
  Parameters: initialCapacity the initial number of buckets loadFactor a number between 0.0 and 1.0 that determines at what percentage of fullness the hash table will be rehashed into a larger one. The default is 0.75

java.util.SortedMap

• Comparator comparator()
  returns the comparator used for sorting the keys, or null if the keys are compared with the compareTo method of the Comparable interface.
• Object firstKey()
  
• Object lastKey()
  return the smallest or largest key in the map.

java.util.TreeMap

• TreeMap(Comparator c)
  constructs a tree set and uses the specified comparator for sorting its keys. Parameters: c the comparator to use for sorting
• TreeMap(Map entries)
  constructs a tree map and adds all entries from a map.
  Parameters: entries the entries to add
• TreeMap(SortedMap entries)
  constructs a tree set, adds all entries from a sorted map, and uses the same element comparator as the given sorted map.
  Parameters: entries the sorted set with the entries to add and the comparator to use

The Collections Framework

A framework is a set of classes that form the basis for building advanced functionality. A framework contains superclasses with useful functionality, policies, and mechanisms. The user of a framework forms sublasses to extend the functionality without having to reinvent the basic mechanisms. For example, Swing is a framework for user interfaces.

The Java collections library forms a framework for collection classes. It defines a number of interfaces and abstract classes for implementors of collections (see Figure 2-9), and it prescribes certain mechanisms, such as the iteration protocol. You can use the collection classes without having to know much about the framework--we did just that in the preceding sections. However, if you want to implement generic algorithms that work for multiple collection types, or if you want to add a new collection type, then it is helpful to understand the framework.

Figure 2-9: The interfaces of the collections framework

There are two fundamental interfaces for containers: Collection and Map. You insert elements into a collection with a method:

boolean add(Object element)

However, maps hold key/value pairs, and you use the put method to insert them.

boolean put(Object key, Object value)

To read elements from a collection, you visit them with an iterator. However, you can read values from a map with the get method:

Object get(Object key)

A List is an ordered collection. Elements are added into a particular position in the container. An object can be placed into its position in two ways: by an integer index and by a list iterator. The List interface defines methods for random access:

void add(int index, Object element)
Object get(int index)
void remove(int index)

The ListIterator interface defines a method for adding an element before the iterator position:

void add(Object element)

To get and remove elements at a particular position, you simply use the next and remove methods of the Iterator interface.

The Set interface is identical to the Collection interface, but the behavior of the methods is more tightly defined. The add method of a set should reject duplicates. The equals method of a set should be defined so that two sets are identical if they have the same elements, but not necessarily in the same order. ThehashCodemethod should be defined such that two sets with the same elements yield the same hash code.

Why make a separate interface if the method signatures are the same? Conceptually, not all collections are sets. Making a Set interface enables programmers to write methods that only accept sets.

Finally, the SortedSet and SortedMap interfaces expose the comparison object used for sorting, and they define methods to obtain views of subsets of the containers. We discuss these views in the next section.

Now, let us turn from the interfaces to the classes that implement them. We already discussed that the collection interfaces have quite a few methods that can be trivially implemented from more fundamental methods. There are five abstract classes that supply many of these routine implementations:

AbstractCollection
AbstractList
AbstractSequentialList
AbstractSet
AbstractMap

If you implement your own collection class, then you probably want to extend one of these classes so that you can pick up the implementations of the routine operations.

The Java library supplies six concrete classes:

LinkedList
ArrayList
HashSet
TreeSet
HashMap
TreeMap

Figure 2-10 shows the relationships between these classes.

Figure 2-10: Classes in the collections framework

Finally, there are a number of legacy container classes that have been present since the beginning, before there was a collections framework:

Vector
Stack
Hashtable
Properties

They have been integrated into the collections framework--see Figure 2-11. We discuss these classes later in this chapter.

Figure 2-11: Legacy classes in the collections framework

Views and Wrappers

If you look at Figure 2-9 and Figure 2-10, you might think it is overkill to have six interfaces and five abstract classes to implement six concrete collection classes. However, these figures don't tell the whole story. By using views, you can obtain other objects that implement the Collection or Map interfaces. You saw one example of this with the keySet method of the map classes. At first glance, it appears as if the method creates a new set, fills it with all keys of the map, and returns it. However, that is not the case. Instead, the keySet method returns an object of a class that implements the Set interface and whose methods manipulate the original map. Such a collection is called a view. You have no way of knowing, and you need not know, exactly what class the library uses to implement the view.

The technique of views has a number of useful applications in the collections framework. Here is the most compelling one. Recall that the methods of the Vector class are synchronized, which is unnecessarily slow if the vector is only accessed from a single thread. For that reason, we recommended the use of the ArrayList instead of the Vector class. However, if you do access a collection from multiple threads, it is very important that the methods are synchronized. For example, it would be disastrous if one thread tried to add to a hash table while another thread is rehashing the elements. The library designers could have implemented companion classes with synchronized methods for all data structures. But they did something more useful. They supplied a mechanism that produces synchronized views for all interfaces. For example, the static synchronizedMap class in the Collections class can turn any Map into a Map with synchronized access methods:

HashMap hashMap = new HashMap();
map = Collections.synchronizedMap(hashMap);

Now, you can access the map object from multiple threads. The methods such as get and put are synchronized--each method call must be finished completely before another thread can call another method.

There are six methods to obtain synchronized collections:

Collections.synchronizedCollection
Collections.synchronizedList
Collections.synchronizedSet
Collections.synchronizedSortedSet
Collections.synchronizedMap
Collections.synchronizedSortedMap

The views that are returned by these methods are sometimes called wrappers.

You should make sure that no thread accesses the data structure through the original unsynchronized methods. The easiest way to ensure this is not to save any reference to the original object, but to simply pass the constructed collection to the wrapper method:

map = Collections.synchronizedMap(
                   new HashMap());

There is one caveat when accessing a collection from multiple threads. Recall that you can either have multiple iterators that read from a collection or have a single thread that modifies the collection. For that reason, you will want to make sure that any iteration--

Iterator iter = collection.iterator();
while (iter.hasNext())
   do something with iter.next();
   

--does not occur at a time when another thread modifies the collection. If it did, then the next method would throw a ConcurrentModificationException. One way to ensure exclusive access is to place the iteration inside a block that locks the container:

synchronized (container)
{  Iterator iter = 
          collection.iterator();
   while (iter.hasNext())
    do something with iter.next();
}

Since the wrappers wrap the interface and not the actual collection object, you only have access to those methods that are defined in the interface. For example, the LinkedList class has convenience methods, addFirst and addLast, that are not part of the List interface. These methods are not accessible through the synchronization wrapper.

However, the synchronizedSet and synchronizedList class do not hide the equals methods of the underlying collections.

The wrappers treat thehashCodemethod in the same way.

The Collections class has another potentially useful set of wrappers to produce unmodifiable views of collections. These wrappers add a runtime check to an existing collection. If an attempt to modify the collection is detected, then an exception is thrown and the collection remains untouched.

For example, suppose you want to let some part of your code look at, but not touch, the contents of a collection. Here is what you could do.

List staff = new LinkedList();
. . .

lookAt(
 new Collections.unmodifiableList(
                           staff));

The Collections.unmodifiableList method returns an object of a class implementing the List interface. Its accessor methods retrieve values from the staff collection. Of course, the lookAt method can call all methods of the List interface, not just the accessors. But all mutator methods (such as add) have been redefined to throw an UnsupportedOperationException instead of forwarding the call to the underlying collection. There are similar methods to obtain unmodifiable wrappers to the other collection interfaces.

The Arrays class has a static asList method that returns a List wrapper around a plain Java array. This method lets you pass the array to a method that expects a list or collection argument. For example,

Card[] cardDeck = new Card[52];
. . .
List cardList = 
      Arrays.asList(cardDeck);

The returned object is not an ArrayList. It is a view object whose get and set methods access the underlying array. All methods that would change the size of the array (such as add and the remove method of the associated iterator) throw an UnsupportedOperationException.

Subranges

You can form subrange views for a number of collections. For example, suppose you have a list staff and want to extract elements 10 to 19. You use the subList method to obtain a view into the subrange of the list.

List group2 = staff.subList(10, 20);

The first index is inclusive, the second exclusive--just like the parameters for the substring operation of theStringclass.

You can apply any operations to the subrange, and they automatically reflect the entire list. For example, you can erase the entire subrange:

group2.clear(); // staff reduction

The elements are now automatically cleared from the staff list.

For sorted sets and maps, you use the sort order, not the element position, to form subranges. The SortedSet interface declares three methods:

subSet(from, to)
headSet(to)
tailSet(from)

These return the subsets of all elements that are larger than or equal to from and strictly smaller than to. For sorted maps, there are similar methods

subMap(from, to)
headMap(to)
tailMap(from)

that return views into the maps consisting of all entries where the keys fall into the specified ranges.

Lightweight collection wrappers

The method call
Collections.nCopies(n, anObject)

returns an immutable object that implements the List interface and gives the illusion of havingnelements, each of which appears as anObject. There is very little storage cost--the object is only stored once. This is a cute application of the wrapper technique. You can use such a list to initialize a concrete container. For example, the following call creates an ArrayList containing 100 strings, all set to "DEFAULT":

ArrayList settings 
   = new ArrayList(
    Collections.nCopies(
    100, "DEFAULT"));
The method call
Collections.singleton(anObject)

returns a wrapper object that implements the Set interface (unlike ncopies which produces a List). The returned object implements an immutable single-element set without the overhead of a hash table or tree. The constants Collections.EMPTY_LIST and Collections.EMPTY_SET return objects that implement the List and Set interfaces and contain no elements. The advantage is similar to that of the singleton method: the returned objects do not have the overhead of a data structure. Singletons and empty objects are potentially useful as parameters to methods that expect a list, set, or container.

A final note on optional operations

We'd like to end this section with a few words about the "optional" or unsupported operations in the collection and iterator interfaces. This is undoubtedly the most controversial design decision in the collections framework. The problem is caused by the undeniably powerful and convenient views. Views are good because they lead to efficient code, and their "plug and play" nature means you only need to learn a few basic concepts. A view usually has some restriction--it may be read-only, it may not be able to change the size, or it may support removal, but not insertion, as is the case for the key view of a map. The restriction is different for each view. Making a separate interface for each restricted view would lead to a bewildering tangle of interfaces that would be unusable in practice.

Should you extend the technique of optional methods to your own interfaces? We think not. Even though collections are used very frequently, the coding style for implementing them is not typical for other problem domains. The designers of a collection class library have to resolve a particularly brutal set of conflicting requirements. Users want the library to be easy to learn, convenient to use, completely generic, idiot-proof, and at the same time as efficient as hand-coded algorithms. It is plainly impossible to achieve all these goals simultaneously, or even to come close. Look at a few other libraries, such as the JGL library from ObjectSpace Objectpspace.com, to see a different set of trade-offs. Or, even better, try your hand at designing your own library of collections and algorithms. You will soon run into the inevitable conflicts and feel much more sympathy with the folks from Sun. But in your own programming problems, you will rarely encounter such an extreme set of constraints. You should be able to find solutions that do not rely on the extreme measure of optional interface operations.

java.util.Collections

• static Collection synchronizedCollection(Collection c)
• static List synchronizedList(List c)
• static Set synchronizedSet(Set c)
• static SortedSet synchronizedSortedSet(SortedSet c)
• static Map synchronizedMap(Map c)
• static SortedMap synchronizedSortedMap(SortedMap c)
  construct a view of the collection whose methods are synchronized. Parameters: c the collection to wrap
• static Collection unmodifiableCollection(Collection c)
• static List unmodifiableList(List c)
• static Set unmodifiableSet(Set c)
• static SortedSet unmodifiableSortedSet(SortedSet c)
• static Map unmodifiableMap(Map c)
• static SortedMap unmodifiableSortedMap(SortedMap c) construct a view of the collection whose mutator methods throw an UnsupportedOperationException.
Parameters: c the collection to wrap
• static List nCopies(int n, Object value)
• static Set singleton(Object value)
  construct a view of the object as either an unmodifiable list withn identical elements or a set with a single element.
  Parameters: n the number of times to repeat the value in the list value the element value in the collection
• static final List EMPTY_LIST
• static final Set EMPTY_SET
  

An unmodifiable wrapper for an empty list or set.

java.util.Arrays

• static List asList(Object[] array)
  returns a list view of the elements in an array that is modifiable but not resizable. Parameters: array the array to wrap

java.util.List

• List subList(int from, int to)
  returns a list view of the elements within a range of positions. Parameters: from the first position to include in the view to the first position to exclude in the view

java.util.SortedSet

• SortedSet subSet(Object from, Object to)
• SortedSet headSet(Object to)
• SortedSet tailSet(Object from)
  return a view of the elements within a range.
  Parameters: from the first element to include in the view to the first element to exclude in the view

java.util.SortedMap

• SortedMap subMap(Object from, Object to)
• SortedMap headMap(Object to)
• SortedMap tailMap(Object from)
  return a map view of the entries whose keys are within a range. Parameters: from the first key to include in the view to the first key to exclude in the view

• Collection Interfaces
• Concrete Collections
• The Collections Framework
• Algorithms
• Legacy Collections