Map Implementations – Collections: Part II

15.9 Map Implementations

Figure 15.3, p. 787, shows four implementations of the Map<K, V> interface found in the java.util package: HashMap<K, V>, LinkedHashMap<K, V>, Hashtable<K, V>, and TreeMap<K, V>.

The classes HashMap<K, V> and Hashtable<K, V> implement unordered maps. The class LinkedHashMap<K, V> implements ordered maps, and the class TreeMap<K, V> implements sorted maps (p. 845).

While the HashMap<K, V> class is not thread-safe and permits a null key and null values (analogous to the LinkedHashMap<K, V> class), the Hashtable<K, V> class is thread-safe and permits only non-null keys and values (see Table 15.7). The thread-safety provided by the Hashtable<K, V> class comes with a performance penalty. Thread-safe use of maps is also provided by the methods in the Collections class (p. 856). Like the Vector<E> class, the Hashtable<K, V> class is also a legacy class that has been retrofitted to implement the Map<K, V> interface.

Table 15.7 Map Implementations

Map	null as key	null as value	Kind of map	Thread-safe?
HashMap<K,V>	Allowed	Allowed	Unordered	Not thread-safe
LinkedHashMap<K,V> extends HashMap<K,V>	Allowed	Allowed	Key insertion order/Access order	Not thread-safe
Hashtable<K,V>	Not allowed	Not allowed	Unordered	Thread-safe
TreeMap<K,V>	Not allowed	Allowed	Key-sort order	Not thread-safe

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 (§14.2, p. 744, and §14.3, p. 753).

The LinkedHashMap<K, V> implementation is a subclass of the HashMap<K, V> class. The relationship between the map classes LinkedHashMap<K, V> and HashMap<K, V> is analogous to the relationship between their counterpart set classes LinkedHashSet<E> and HashSet<E>. The entries of a HashMap<K, V> (analogous to a HashSet<E>) are unordered. The entries of a LinkedHashMap<K, V> (analogous to a LinkedHashSet<E>) are ordered. By default, the entries of a LinkedHashMap<K, V> 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 reinserted because no new entry is created if the key’s entry already exists. The elements in a LinkedHashSet<E> are also at (element) insertion order. However, a LinkedHashMap<K, V> can also maintain its entries in 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<K, V> class.

Both the HashMap<K, V> and the LinkedHashMap<K, V> classes provide comparable performance, but the HashMap<K, V> 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 in constant time, as these are based on hashing the key. Operations such as finding the entry with a specific value are in linear time, as these involve searching through the entries.

Adding, removing, and finding entries in a LinkedHashMap<K, V> can be slightly slower than in a HashMap<K, V>, as an ordered doubly linked list has to be maintained. Iteration over a map is through one of its collection views. For an underlying LinkedHashMap<K, V>, the iteration time is proportional to the size of the map— regardless of its capacity. However, for an underlying HashMap<K, V>, it is proportional to the capacity of the map.

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

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

where each keyi and each valuei, where 1 <= i <= n, is the text 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 map. Additional constructors create empty maps with given initial capacities and load factors. The HashMap<K, V> class provides the following constructors:

Click here to view code image

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

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

Click here to view code image

HashMap(Map<? extends K,? extends V> otherMap)

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

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

Click here to view code image

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 15.10 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. A HashMap<Integer, Integer> is used, where the key is the weight group and the value is the frequency. The example illustrates many key-based operations on maps, the creation of key views, and iteration over a map.

We have intentionally used a HashMap<K,V>. It is instructive to compare this with the solution in Example 15.11 that uses a TreeMap<K,V> that simplifies the solution further, when the entries are maintained in key-sort order.

The program proceeds as follows:

• An empty HashMap<Integer, Integer> is created at (1), where the key is the weight group and the associated value is the frequency.
• A for(:) loop is used at (2) to read the weights specified as program arguments, converting each weight to its corresponding weight group and updating the frequency of the weight group.

Each program argument is parsed to a double value at (3), which is then used to determine the correct weight group at (4). The call to the merge() method at (5) updates the frequency map:

Click here to view code image

// With method reference:
groupFreqMap.merge(weightGroup, 1, Integer::sum);                    // (5)
// With lambda expression:
groupFreqMap.merge(weightGroup, 1,
   (oldVal, givenVal) -> Integer.sum(oldVal, givenVal));