11.5 Maps

A Map defines mappings from keys to values. The <key, value> pair is called an entry. A map does not allow duplicate keys, in other words, the keys are unique. Each key maps to one value at the most, implementing what is called a single-valued map. Thus, there is a many-to-one relation between keys and values. For example, in a student-grade map, a grade (value) can be awarded to many students (keys), but each student has only one grade.

Both the keys and the values must be objects. This means that primitive values must be wrapped in their respective wrapper objects, if they are to be put in a map.

A map is not a collection and the Map interface does not extend the Collection interface. However, the mappings can be viewed as a collection in various ways: a key set, a value collection, or an entry set. These collection views are the only means of traversing a map.

The Map interface specifies some optional methods. Implementations should throw an UnsupportedOperationException if they do not support such an operation. The implementations of maps from the java.util package support all the optional operations of the Map interface (see Table 11.2 and Figure 11.3).

Basic Operations

These operations constitute the basic functionality provided by a map.

Object get(Object key)

boolean containsKey(Object key)

boolean containsValue(Object value)

int size()
boolean isEmpty()

Bulk Operations

Collection Views

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

interface Entry {
    Object getKey();
    Object getValue();
    Object setValue(Object value);
}

HashMap, LinkedHashMap, and Hashtable

Figure 11.3 shows four implementations of the Map interface in the java.util package: HashMap, LinkedHashMap, TreeMap, and Hashtable.

The classes HashMap and Hashtable implement unordered maps. The class LinkedHashMap implements ordered maps, which are discussed below. The class TreeMap implements sorted maps (see Section 11.6, p. 452).

While the HashMap class is not thread-safe and permits one null key, the Hashtable class is thread-safe and permits non-null keys and values only. The thread-safety the Hashtable class provides has a performance penalty. Thread-safe use of maps is also provided by the methods in the Collections class (see Section 11.8, p. 481). Like the Vector class, the Hashtable class is also a legacy class that has been retrofitted to implement the Map interface.

These map implementations are based on a hashing algorithm. Operations on a map thus rely on the hashCode() and equals() methods of the key objects (see Section 11.7, p. 461).

The LinkedHashMap implementation is a subclass of the HashMap class. The relationship between the map classes LinkedHashMap and HashMap is analogous to the relationship between their counterpart set classes LinkedHashSet and HashSet. Elements of a HashMap (and a HashSet) are unordered. The elements of a LinkedHashMap (and a LinkedHashSet) are ordered. By default, the entries of a LinkedHashMap are in key insertion order, that is, the order in which the keys are inserted in the map. This order does not change if a key is re-inserted, because no new entry is created if the key's entry already exists from before. The elements in a LinkedHashSet are in (element) insertion order. However, a LinkedHashMap can also maintain its elements in (element) access order, that is, the order in which its entries are accessed, from least-recently accessed to most-recently accessed entries. This ordering mode can be specified in one of the constructors of the LinkedHashMap class.

Both the HashMap and LinkedHashMap classes provide comparable performance, but the HashMap class is the natural choice if ordering is not an issue. Operations such as adding, removing, or finding an entry based on a key are constant time, as these hash the key. Operations such as finding the entry with a particular value are in linear time, as these involve searching through the entries.

Adding, removing, and finding entries in a LinkedHashMap can be slightly slower than in a HashMap, as an ordered doubly-linked list has to be maintained. Traversal of a map is through one of its collection-views. For an underlying LinkedHashMap, the traversal time is proportional to the size of the map?regardless of its capacity. However, for an underlying HashMap, it is proportional to the capacity of the map.

The concrete map classes override the toString() method. The standard textual representation generated by the toString() method for a map is

{key₁=value₁, key₂=value₂, ..., key_n=value_n}

where each key_i and each value_i is the textual representation generated by the toString() method of the individual key and value objects in the map, respectively.

As was the case with collections, implementation classes provide a standard constructor that creates a new empty map, and a constructor that creates a new map based on an existing one. These classes also create a new empty map with an initial capacity and/or load factor. The HashMap class provides the following constructors:

HashMap()
HashMap(int initialCapacity)
HashMap(int initialCapacity, float loadFactor)

HashMap(Map otherMap)

The LinkedHashMap and Hashtable classes have constructors analogous to the four constructors for the HashMap class. In addition, the LinkedHashMap class provides a constructor where the ordering mode can also be specified:

LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

Example 11.4 Using Maps

import java.util.*;

public class WeightGroups {
    public static void main(String[] args) {

        // Create a map to store the frequency for each group.
        Map groupFreqData = new HashMap();

        int numArgs = args.length;
        for (int i=0; i<numArgs; i++) {
            // Get the value from an argument and group into intervals of 5.(1)
            double weight = Double.parseDouble(args[i]);
            Integer weightGroup = new Integer((int) Math.round(weight/5)*5);
            // Increment count, set to 1 if it's the first value of group.  (2)
            Integer oldCount = (Integer) groupFreqData.get(weightGroup);
            Integer newCount = (oldCount==null) ?
                new Integer(1) :
                new Integer(oldCount.intValue()+1);
            groupFreqData.put(weightGroup, newCount);                    // (3)
        }
        /* Print by traversing a sorted list of groups (keys),
           and extracting count (values) from the groupFreqData map. */

        /* Create a list of groups (keys), and use the sort algorithm from
           the Collections class to sort the keys. */
        List keys = new ArrayList(groupFreqData.keySet());               // (4)
        Collections.sort(keys);                                          // (5)

        /* Create an iterator on the sorted keys. Traverse the keys,
           looking up the frequency from the frequency map. */
        ListIterator keyIterator = keys.listIterator();                  // (6)
        while (keyIterator.hasNext()) {
            // Current key (group).                                         (7)
            Integer group = (Integer) keyIterator.next();
            // Extract count (value) from the map.
            Integer count = (Integer) groupFreqData.get(group);          // (8)
            int intCount = count.intValue();

            /* Use the fill() method from the Arrays class to create a
               string consisting of intCount number of '*'. */
            char[] bar = new char[intCount];
            Arrays.fill(bar, '*');                                       // (9)

            System.out.println(group + ":\t" + new String(bar));
        } // end while
    } // end main()
} // end of class

Running the program with the following arguments:

>java WeightGroups 74 75 93 75 93 82 61 92 10 185

gives the following output:

10:     *
60:     *
75:     ***
80:     *
90:     *
95:     **
185:    *

Example 11.4 prints a textual histogram for the frequency of weight measurements in a weight group, where a weight group is defined as an interval of five units. The weight measurements are supplied as program arguments. The example illustrates the use of maps, creation of key views, and the use of a list iterator to traverse a map. The program proceeds as follows: