Maps

You can create a map using one of its three concrete classes: HashMap,
LinkedHashMap, or TreeMap. A map is a container object that stores a collection of key/value pairs. It enables fast retrieval, deletion, and updating of the pair through the key. A map stores the values along with the keys. The keys are like indexes. In List, the indexes are integers. In Map, the keys can be any objects. A map cannot contain duplicate keys. Each key maps to one value. A key and its corresponding value form an entry stored in a map, as shown in Figure below (a). Figure below (b) shows a map in which each entry consists of a Social Security number as the key and a name as the value.

There are three types of maps: HashMap, LinkedHashMap, and TreeMap. The common features of these maps are defined in the Map interface. Their relationship is shown in Figure below.

The Map interface provides the methods for querying, updating, and obtaining a collection of values and a set of keys, as shown in Figure below.

The update methods include clear, put, putAll, and remove. The clear() method removes all entries from the map. The put(K key, V value) method adds an entry for the specified key and value in the map. If the map formerly contained an entry for this key, the old value is replaced by the new value and the old value associated with the key is returned. The putAll(Map m) method adds all entries in m to this map. The remove(Object key) method removes the entry for the specified key from the map.

The query methods include containsKey, containsValue, isEmpty, and size. The containsKey(Object key) method checks whether the map contains an entry for the specified key. The containsValue(Object value) method checks whether the map contains an entry for this value. The isEmpty() method checks whether the map contains any entries. The size() method returns the number of entries in the map.

You can obtain a set of the keys in the map using the keySet() method, and a collection of the values in the map using the values() method. The entrySet() method returns a set of entries. The entries are instances of the Map.Entry interface, where Entry is an inner interface for the Map interface, as shown in Figure below. Each entry in the set is a key/value pair in the underlying map.

The AbstractMap class is a convenience abstract class that implements all the methods in the Map interface except the entrySet() method.

The HashMap, LinkedHashMap, and TreeMap classes are three concrete implementations of the Map interface, as shown in Figure below.

The HashMap class is efficient for locating a value, inserting an entry, and deleting an entry.

LinkedHashMap extends HashMap with a linked-list implementation that supports an ordering of the entries in the map. The entries in a HashMap are not ordered, but the entries in a LinkedHashMap can be retrieved either in the order in which they were inserted into the map (known as the insertion order) or in the order in which they were last accessed, from least recently to most recently accessed (access order). The no-arg constructor constructs a LinkedHashMap with the insertion order. To construct a LinkedHashMap with the access order, use LinkedHashMap(initialCapacity, loadFactor, true).

The TreeMap class is efficient for traversing the keys in a sorted order. The keys can be sorted using the Comparable interface or the Comparator interface. If you create a TreeMap using its no-arg constructor, the compareTo method in the Comparable interface is used to compare the keys in the map, assuming that the class for the keys implements the Comparable interface. To use a comparator, you have to use the TreeMap(Comparator comparator) constructor to create a sorted map that uses the compare method in the comparator to order the entries in the map based on the keys.

SortedMap is a subinterface of Map, which guarantees that the entries in the map are sorted. Additionally, it provides the methods firstKey() and lastKey() for returning the first and last keys in the map, and headMap(toKey) and tailMap(fromKey) for returning a portion of the map whose keys are less than toKey and greater than or equal to fromKey, respectively.

NavigableMap extends SortedMap to provide the navigation methods lowerKey(key), floorKey(key), ceilingKey(key), and higherKey(key) that return keys respectively less than, less than or equal, greater than or equal, and greater than a given key and return null if there is no such key. The pollFirstEntry() and pollLastEntry() methods remove and return the first and last entry in the tree map, respectively.

Prior to Java 2, java.util.Hashtable was used for mapping keys with values. Hashtable was redesigned to fit into the Java Collections Framework with all its methods retained for compatibility. Hashtable implements the Map interface and is used in the same way as HashMap, except that the update methods in Hashtable are synchronized.

The code below gives an example that creates a hash map, a linked hash map, and a tree map for mapping students to ages. The program first creates a hash map with the student’s name as its key and the age as its value. The program then creates a tree map from the hash map and displays the entries in ascending order of the keys. Finally, the program creates a linked hash map, adds the same entries to the map, and displays the entries.

Display entries in HashMap
{Cook=29, Smith=30, Lewis=29, Anderson=31}
Display entries in ascending order of key
{Anderson=31, Cook=29, Lewis=29, Smith=30}
The age for Lewis is 29
Display entries in LinkedHashMap
{Smith=30, Anderson=31, Cook=29, Lewis=29}

As shown in the output, the entries in the HashMap are in random order. The entries in the TreeMap are in increasing order of the keys. The entries in the LinkedHashMap are in the order of their access, from least recently accessed to most recently.

All the concrete classes that implement the Map interface have at least two constructors. One is the no-arg constructor that constructs an empty map, and the other constructs a map from an instance of Map. Thus, new TreeMap(hashMap) (lines 18) constructs a tree map from a hash map.

You can create an insertion-ordered or access-ordered linked hash map. An access-ordered linked hash map is created in lines 23. The most recently accessed entry is placed at the end of the map. The entry with the key Lewis is last accessed in line 30, so it is displayed last in line 33.

If you don’t need to maintain an order in a map when updating it, use a HashMap. When you need to maintain the insertion order or access order in the map, use a LinkedHashMap. When you need the map to be sorted on keys, use a TreeMap.