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 put(Object key, Object value)


Inserts the <key, value> entry into the map. It returns the value previously associated with the specified key, if any. Otherwise, it returns the null value.

Object get(Object key)

Returns the value to which the specified key is mapped, or null if no entry is found.

Object remove(Object key)


The remove() method deletes the entry for the specified key. It returns the value previously associated with the specified key, if any. Otherwise, it returns the null value.

boolean containsKey(Object key)

Returns true if the specified key is mapped to a value in the map.

boolean containsValue(Object value)

Returns true if there exists one or more keys that are mapped to the specified value.

int size()
boolean isEmpty()

These methods return the number of entries (i.e., number of unique keys in the map) and whether the map is empty or not.

Bulk Operations

void putAll(Map t)


void clear()


The first method copies all entries from the specified map to the current map, and the second method deletes all the entries from the current map.

Collection Views

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

These methods provide different views of a map. Changes in the map are reflected in the view, and vice versa. These methods return a set view of keys, a collection view of values and a set view of <key, value> entries, respectively. Note that the Collection returned by the values() method is not a Set, as several keys can map to the same value, that is, duplicate values can be included in the returned collection. Each <key, value> in the entry set view is represented by an object implementing the nested Map.Entry interface. An entry in the entry set view can be manipulated by methods defined in this interface, which are self-explanatory:

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

{key1=value1, key2=value2, ..., keyn=valuen}

where each keyi and each valuei 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(int initialCapacity)
HashMap(int initialCapacity, float loadFactor)

Constructs a new, empty HashMap, using either specified or default initial capacity and load factor.

HashMap(Map otherMap)

Constructs a new map containing the elements in the specified map.

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)

Constructs a new, empty LinkedHashMap with the specified initial capacity, the specified load factor, and the specified ordering mode. The ordering mode is true for access order and false for key insertion order.

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:

  1. It reads the program arguments, converting each weight to its corresponding weight group and updating the frequency of the weight group:

    The weight group is determined at (1). The count is incremented, if necessary, as shown at (2), and registered for the group, as shown at (3). Since keys are unique in a map, any previous entry is overwritten.

    // 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)
  2. It creates a list of keys (which are weight groups) from the groupFreqData map and sorts them. The keySet() method returns a set view of keys, which is converted to a list, as shown at (4). The key list is sorted by the algorithm sort() from the Collections class, as shown at (5).

    List keys = new ArrayList(groupFreqData.keySet());              // (4)
    Collections.sort(keys);                                         // (5)
  3. It uses an iterator to traverse the keys, looking up the frequency in the groupFreqData map. A map can only be traversed through one of its views.

    The list iterator is created at (6).

    ListIterator keyIterator = keys.listIterator();                 // (6)

    For each key, the corresponding value (i.e., frequency count) is retrieved, as shown at (7) and (8).

    // Current key (group).                                            (7)
    Integer group = (Integer) keyIterator.next();
    // Extract count (value) from the map.
    Integer count = (Integer) groupFreqData.get(group);             // (8)

    A bar for each frequency is created using the fill() method from the Arrays class, as shown at (9).