Map interfaces class diagram.
Map interfaces class diagram.

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.

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!

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:

Returns the number of key-value associations in the map.
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.
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.
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.
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.
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.
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>.
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>.


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

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);



In the Real World

Self Evaluation


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

See Also