Maps

Goals

Learn to use the Map<K, V> interface and its most-used implementations.
Explore the Java Collection utilities for maps.

Concepts

Java Collections Framework (JCF)
map
map key
map value

Library

Lesson

Maps

The abstract data types (ADTs) you've seen so far in the Java Collections Framework (JCF) have been those that merely group objects together. The other major division of the JCF focuses on an ADT that associates or maps certain objects to others.

Map: A map is an association of objects in which an object may be later retrieved when given the object it was mapped to.

`Map<K, V>`

The java.util.Map<K, V> interface does not extend Collection<E>, but it is closely related to collections. A Map<K, V> represents associations between keys and values, as you implemented in your HashTableImpl<K, V> class. The difference is that the Java Map<K, V> interface represents a true abstract data type—it represents merely a group of key-value associations, without indicating how those associations are implemented. You'll find that the most popular implementation of Map<K, V> is indeed based upon a hash table, but there are many other implementations of Map<K, V>, including one based on trees!

The fact that maps normally make key comparisons based upon Object.equals(…) can be a little tricky. And be careful: some map implementations are made especially for comparing keys based upon identity rather than on equivalence. These keys bend the contract rules for very useful reasons, though, and they usually make it clear in their names and documentation this departure from the Map<K, V> contract. Still—be careful.

Map<K, V> provides some methods equivalent to the HashTable<K, V> interface in these lessons, along with many others. Here are a few of them:

size(): Returns the number of key-value associations in the map.
isEmpty(): This is a convenience method logically equivalent to checking size() == 0. Calling isEmpty() is preferred over checking the size, because the underlying implementation may have a more efficient way than retrieving the number of key-value associations.
get(Object key): Retrieves the value associated with a key. If the value is not present, it will return null. If the map allows null values, the meaning of a null return value would be ambiguious; you can use containsKey(Object key) to tell for sure if there whether no value is present for that key, or that the value associated with that key is null.
put(K key, V value): Associates a value with a key, replacing the original association, if any.
remove(K key): Removes any value associated with a given key.
clear(): Removes all key-value associations from the map, leaving the map empty. Depending on the specific implementation, this method may be more efficient than removing key-value associations individually.
keySet(): Retrieves a Set<K> of all the keys in the map. The set is a live view, so that modifications will be reflected in the original map, if the map supports removal. The returned collection is a Set<K> because it is known that a Map<K, V> does not contain duplicate keys.
values(): Retrieves a Collection<V> of all the values in the map. The set is a live view, so that modifications will be reflected in the original map, if the map supports removal. The returned object is a Collection<E> because there may be duplication values. The map may return whatever collection type it desires.
entrySet(): Returns a Set<Map.Entry<K, V>> of map entry objects in the map, each of type java.util.Map.Entry<K, V> and containing a key-value association. The set is live, so that modifications to the set, as well as to the individual entries, will be reflected in the original map, if the map supports modification. The Map.Entry<K, V> class is analogous to the Entry<K, V> class you made to implement the HashTable<K, V> interface in an earlier lesson.

When newcomers to Map<K, V> want to look at all the key/value associations, they often attempt to enumerate the keys and then look up each value:

final Map<String, Vehicle> vehiclesById = new HashMap<String, Vehicle>();
for(final String vehicleId : vehiclesById.keySet()) {
  final Vehicle vehicle = vehiclesById.get(vehicleId); //inefficient
  //TODO use the vehicleId and vehicle
}

This approach is unnecessarily inefficient, because for each key you must look up the corresponding value separately. Remember that Map.entrySet() returns a Set<Map.Entry<K, V>>, allowing you to iterate across the actual key/value entries themselves, removing the need for a separate lookup.

final Map<String, Vehicle> vehiclesById = new HashMap<String, Vehicle>();
for(final Map.Entry<String, Vehicle> vehicleEntry : vehiclesById.entrySet()) {
  final String vehicleId = vehicleEntry.getKey();  //each entry has a key…
  final Vehicle vehicle = vehicleEntry.getValue(); //…and value together
  //TODO use the vehicleId and vehicle
}

Subinterfaces

java.util.SortedMap<K, V>: If a Map<K, V> implements this interface, it guarantees some ordering of its keys. This is usually the natural ordering or the ordering of some provided Comparator<T> strategy.
java.util.NavigableMap<K, V>: The NavigableMap<K, V> interface provides additional methods for navigating to values based upon the order of their keys. For example higher(K key) returns the first Map.Entry<K, V> that is higher than the given element. The headMap(K toKey) method returns a view to the map that only includes entries with keys lower than the given element. The fact that a NavigableMap<K, V> has some order might have tipped you off that a NavigablMap<K, V> is a SortedMap<K, V>.

Implementations

java.util.HashMap<K, V>: A map based on a hash table. This is the analogue of HashTableImpl<E> in these lessons. HashMap<K, V> should be the default Map<K, V> implementation you choose unless you have reason to choose another implementation.
java.util.LinkedHashMap<K, V>: Equivalent to a HashMap<K, V>, except that it also maintains a doubly-linked list to maintain iteration order. The order in which iteration occurs is based on the insertion-order, the order in which you add items to the set.
java.util.IdentityHashMap<K, V>: A map based on a hash table in which keys are compared using identity (==) rather than equality. These maps slightly bend the rules of object lookup, and are used for special cases such as associating metadata with specific object instances.
java.util.TreeMap<K, V>: A Map<K, V> that automatically sorts entries by their keys, using a tree data structure to maintain order. The keys are either sorted by their natural ordering, or by a Comparable<T> provided in the constructor. A TreeMap<K, V> is a NavigableMap<K, V>, which implies it is also a SortedMap<K, V>.

Utilities

The java.util.Collections class contains many utilities for working with maps as well. The most useful ones are explained below.

You may want to statically import java.util.Collections.* so that the utility methods read more fluently.

Empty Maps

If you know that your method will return an empty map, instead of creating a collection implementation such as HashMap<K, V> you can use one of Java's pre-made, immutable, empty maps. The Collections class provides the method emptyMap() which returns the correct generic type of map you require.

Immutable Maps

Sometimes you need to have a collection that you do not allow anyone to modify. Rather implementing this functionality into each collection type, Java provides the immutability utility method unmodifiableMap(…) which turns any map instance into an immutable one. The original map is still mutable; Java instead returns a new map instance that is provides immutable access to your existing collection. Calling any modifying method will result in an UnsupportedOperationException.

Converting Sets to Maps

You may have found a Map<K, V> in some third-party library that provides some cool functionality, but unfortunately that library provides no equivalent Set<E> with the same capabilities. You can use the newSetFromMap(Map<E, Boolean>) method, which will instantiate a new set for you, backed by the map you provide! The only requrement is that you provide a Map<K, Boolean>—that is, your map must use Boolean values. Java is able to create a Set<E> from a Map<K, Boolean> by considering a set to be a mapping of any object to Boolean.TRUE—indicating that the element is contained in the set.

The following example shows how we could make the equivalent of a HashSet<E> (if that class didn't exist) by converting a HashMap<K, Boolean> to a Set<E> using newSetFromMap(Map<E, Boolean>).

Converting a set to a map.

final Map<String, Boolean> map = new HashMap<String, Boolean>();
final Set<String> setFromMap = java.util.Collections.newSetFromMap(map);

Using Boolean as the mapping value is only a convention. The actual value being mapped doesn't matter, as any Map<K, V> makes sure that no keys have duplicates. Therefore if the map has a certain key, that key can be considered in the set. In fact the reference HashSet<K, V> implementation simply uses an arbitrary Object instance as the token value.

Review

Gotchas

If a Map<K, V> allows null values, there is no way to tell whether a null return value from Map.get(…) indicates that no value is present for that key, or that the value associated with that key is null. You may need to use Map.containsKey(…).
Don't assume that Map.keySet() or Map.values() will return the items in any particular order.
To find all a map's key/value associations, don't iterate over Map.keySet() and look up values separately. Instead iterate over Map.entrySet().
An IdentiyHashMap<K, V> compares keys by identical reference, not by using Object.equals(…); this behavior is slightly different than most maps.

In the Real World

A HashMap<K, V> will be the Map<K, V> implementation you use most, and should be the first Map<K, V> you reach for unless there are atypical considerations for your use case.

Self Evaluation

In what order does an iterator of a LinkedHashMap<K, V> return its values? How does this differ from the iterator of a plain HashMap<K, V>?
What is an object's natural ordering?

Task

Convert your booker project to use Java maps rather than your hash table implementations from your datastruct project.

Replace your HashTable<> classes with the appropriate classes from the JCF.
Find one of the JCF classes mentioned in this lesson to replace your BinarySearchTree<> classes.
- You should be able to utilize your existing Comparator<> unmodified.
- Move the BinarySearchTree.printAll() functionality into Booker itself.
  - Placing the printing functionality inside the data structure was not the best design in the first place, and was done only for explanatory purposes.
  - If you choose the correct JCF class, the values will be returned in the correct order for you to print them.
Once you are finished, you should have no references to any datastruct classes or interfaces.
Remove the datastruct dependency from your booker project POM.

References

Collections Framework Overview (Oracle)

Resources

The Collections Framework (Oracle - Java™ Platform Overview)

Maps

Goals

Concepts

Library

Lesson

Maps

Map<K, V>

Subinterfaces

Implementations

Utilities

Empty Maps

Immutable Maps

Converting Sets to Maps

Review

Gotchas

In the Real World

Self Evaluation

Task

See Also

References

Resources

`Map<K, V>`