20.1.1. The Map Interface¶

The Map<K, V> interface is modeled after looking up definitions for words in a dictionary. In computer science, you will hear people refer to these kinds of “look up” structures using names like “map”, “dictionary”, “hash”, or even “associative array”. You can think of a map as a collection of pairs of elements that are associated with each other. A pair consists of a key that corresponds to a value you can look up, and a value corresponding to the result you will find when you look up its key. If you think of a dictionary of words, for example, each entry in the dictionary consists of a “word” and its “definition”. We would call the “word” a “key”, and its definition would be a “value”, and the dictionary itself is a collection of pairs of keys and values (words and definitions). You will sometimes hear the elements in a map referred to as a key-value pair because it contains pairs of connected values.

Pairs can be added to maps and can be removed from maps. Maps cannot have distinct pairs with the same keys; if you attempt to add a pair to a map that already contains a pair with the same key, the second pair will replace the first.

The Map<K, V> interface defines the map operations. It takes two separate generic type parameters: K is the type parameter specifying the key type, and V is the type parameter specifying the value type. For example K could be Integer and a V could be String. Or K and V could both be Boolean. Or K could be String and V could be List<Book>. There are no limits on possible combinations, as long as they are object types and not primitive types.

The most important Map operations are:

public interface MHCMap<K, V> {
    /** 
     * Get the value associated with a key
     * @param key the key to look up
     * @return the value associated with the key or null if the key is not
     * in the map.
     */
    public V get (K key);

    /** 
     * Associates a value with a key.
     * @param key the key whose value is set
     * @param value the value to be associated with the key
     * @return if the key previously had a value, return the previous value.  If the key
     * was not in the table, return null.
     */
    public V put (K key, V value);

    /** 
     * Returns true if the map has an entry for the key
     * @param key the key to look up
     * @return true if the key is in the table.  Otherwise return false.
     */
    public boolean containsKey (K key);

    /** 
     * Removes the entry for the key.
     * @param key the key for the entry to remove
     * @return If the key was in the table, the value previously associated with 
     *  the key is returned.  If the key was not in the table, null is returned.
     */
    public V remove (K key);
}

20.1.2. Classes that Implement Map¶

HashMap and TreeMap are two classes in the java.util collections framework that implement the Map interface. They both provide fast operations to look up a key in a map. They also provide quick insertion of a pair into the map or removal of a pair from a map. For large volumes of data, both are much, much faster at lookup tasks than storing items in a List or an array. We usually use HashMap as the default choice when we create new maps, similar to choosing ArrayList as the default choice for new List objects. The HashMap class works well in most cases.

One situation when you would prefer to use TreeMap is when you would like to iterate over all the keys in the map in sorted order. For example, in a dictionary, you might expect words to be stored in alphabetical order, and in a phone book, you might expect names to be stored in alphabetical order. If keys have a natural ordering, the TreeMap class will use this order when iterating over keys, although his can slightly impact the overall performance of the map by a small amount. The HashMap does not keep keys in any predictable order.

20.1.3. Using a Map¶

Let’s think about a simple example for using a map data structure. Suppose that a programmer is developing an application for a large company for maintaining a no-call list. The programmer wishes to store pairs of names and phone numbers. We could represent both using strings, so we could use a Map<String, String> to store these pairs. The resulting map will act sort of like a phone book, associating names (keys) with phone numbers (values) in pairs.

public static void testMap()
{
    Map<String, String> noCallMap = new HashMap<String, String>();
}

public static void testMap()
{
    Map<String, String> noCallMap = new HashMap<String, String>();

    noCallMap.put("Roger M", "090−997−2918");
    noCallMap.put("Jane Q", "999-777-1234");
}

public static void testMap()
{
    Map<String, String> noCallMap = new HashMap<String, String>();

    noCallMap.put("Roger M", "090−997−2918");
    noCallMap.put("Jane Q", "999-777-1234");

    System.out.print("Jane Q's number is: " + noCallMap.get("Jane Q"));
}

"Jane Q's number is: 999-777-1234"

public static void testMap()
{
    Map<String, String> noCallMap = new HashMap<String, String>();

    noCallMap.put("Roger M", "090−997−2918");
    noCallMap.put("Jane Q", "999-777-1234");

    noCallMap.remove("Jane Q");
    System.out.print(noCallMap.containsKey("Jane Q"));
}