Recap

List models a numbered sequence of elements where the client can control the ordering of the elements.

Set models a group of unique elements (no duplicates) where the client has no control over the ordering of the elements.

Map

Map models a group of elements that are accessed by keys:

• keys must be unique (i.e., the keys form a set)
• each key maps to at most one value
• multiple keys can map to the same value (i.e., the values form a collection that is not necessarily a set)
• key-value pairs are called entries

Map Examples

Map Interface

Map does not extend Collection; instead, it is a separate interface:

public interface Map<K,V> {

    // Basic operations
    V put(K key, V value);
    V get(Object key);
    V remove(Object key);
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    int size();
    boolean isEmpty();

    // Bulk operations
    void putAll(Map<? extends K, ? extends V> m);
    void clear();

    // Collection Views
    public Set<K> keySet();
    public Collection<V> values();
    public Set<Map.Entry<K,V>> entrySet();

    // Interface for entrySet elements
    public interface Entry {
        K getKey();
        V getValue();
        V setValue(V value);
    }
}

Map of Provinces to Capitals

Map<String, String> capitals = new HashMap<String, String>();

capitals.put("Ontario", "Toronto");
capitals.put("Quebec", "Quebec City");
capitals.put("Nova Scotia", "Halifax");
capitals.put("New Brunswick", "Fredericton");
capitals.put("Manitoba", "Winnipeg");
capitals.put("British Columbia", "Victoria");
capitals.put("Prince Edward Island", "Charlottetown");
capitals.put("Saskatchewan", "Regina");
capitals.put("Alberta", "Edmonton");
capitals.put("Newfoundland and Labrador", "St. John\'s");

Map of Provinces to Capitals

Set<String> keys = capitals.keySet();
for (String province : keys)
{
   String city = capitals.get(province);
   out.printf("Capital of %25s : %s%n", province, city);
}

Capital of             New Brunswick : Fredericton
Capital of                    Quebec : Quebec City
Capital of               Nova Scotia : Halifax
Capital of          British Columbia : Victoria
Capital of Newfoundland and Labrador : St. John's
Capital of                  Manitoba : Winnipeg
Capital of                   Alberta : Edmonton
Capital of              Saskatchewan : Regina
Capital of      Prince Edward Island : Charlottetown
Capital of                   Ontario : Toronto

Maps

A map uses a key to insert, remove, and retrieve values. For example, suppose you wanted to count the number of times each word was used in a text document:

Everything starts somewhere, although many physicists disagree.
  But people have always been dimly aware of the problem with the start of things. They wonder aloud how the snowplough driver gets to work, or how the makers of dictionaries look up the spelling of the words. Yet there is the constant desire to find some point in the twisting, knotting, ravelling nets of space-time on which a metaphorical finger can be put to indicate that, here, is the point where it all began...

Opening paragraphs of Hogfather, Terry Pratchett

to              3
they            1
but             1
everything      1
aware           1
somewhere       1
where           1
people          1
space-time      1
been            1
of              5
although        1
began           1
wonder          1
on              1
snowplough      1
be              1
work            1
ravelling       1
how             2
or              1
spelling        1
here            1
disagree        1
finger          1
always          1
many            1
that            1
start           1
makers          1
some            1
dictionaries    1
put             1
can             1
have            1
dimly           1
indicate        1
nets            1
metaphorical    1
words           1
driver          1
all             1
find            1
twisting        1
look            1
aloud           1
with            1
is              2
knotting        1
it              1
constant        1
desire          1
a               1
physicists      1
gets            1
problem         1
the             9
in              1
up              1
point           2
which           1
starts          1
there           1
things          1
yet             1

Counting Words

To count the number of times a word appears in a document, you want to map a word (the key) to its count (the value). The appropriate collection is a map with String keys and Integer values:

import java.util.Map;
import java.util.HashMap;

public class WordCount
{
   public static void main(String[] args)
   {
      Map<String, Integer> wordCount =
            new HashMap<String, Integer>();
            
   }
}

Classes Implementing Map

• HashMap
  • O(1) get, put, containsKey
  • makes no guarantees as to the iteration order of the key set; in particular, it does not guarantee that the order will remain constant over time
• TreeMap
  • O(log N) get, put, containsKey
  • keys are ordered by their natural ordering (sorted)
  • keys must* have type that implements Comparable

Counting Words

Let's assume that you have created a scanner for the text file and created a loop to read in each word.

Suppose you read in a word. If the word is a new word, you want to insert the word as a key with a value of 1 (the word has been counted once). If the word is not a new word, you want to add one to the count for that word.

How can you tell if a word is already a key in the map?

Counting Words

There are two ways to check if a map holds a key.

boolean containsKey(Object key)
Returns true if this map contains a mapping for the specified key.

V get(Object key)
Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.

For the word counting problem, you have to call get if you need to update the word count, so you might as well use get:

// is word already in the map?
Integer count = wordCount.get(word);
if (count == null)
{
   // word is not in the map
}
else
{
   // word is in the map
}

Counting Words

Once you know if a word is a key in the map, you want to update the value associated with the key.

The method put inserts a key-value pair into the map.

V put(K key, V value)
Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.

// is word already in the map?
Integer count = wordCount.get(word);
if (count == null)
{
   wordCount.put(word, 1);
}
else
{
   wordCount.put(word, count + 1);
}

Note on WordCount Example

put returns a value

Maps only allow a key to map to single value; this means that the keys in a map must be unique (ie. the keys form a set). If you use an existing key to insert a value, the old value is replaced by the new value, and put returns the old value.

put returns null if the key used is not currently in the map.

Retrieving all Keys

The keys in a map are unique so they form a set. A client can ask a map for its set of keys:

      // Map<String, Integer> wordCount ...
      
      Set<String> words = wordCount.keySet();
      
      output.println(words);

The code fragment above prints:

[to, they, but, everything, aware, somewhere, where, people, space-time, been, of, although, began, wonder, on, snowplough, be, work, ravelling, how, or, spelling, here, disagree, finger, always, many, that, start, makers, some, dictionaries, put, can, have, dimly, indicate, nets, metaphorical, words, driver, all, find, twisting, look, aloud, with, is, knotting, it, constant, desire, a, physicists, gets, problem, the, in, up, point, which, starts, there, things, yet]

Notice that HashMap does not order the keys. If you want sorted keys, use TreeMap.

for Loops and Collections

The easiest way to traverse a list or a set is to use the enhanced for loop (also called the for each loop). This type of loop only works for classes that implement the Collection interface (and arrays).

Recall that the keys for our word counting map are all strings. If we want to print each key, one key per line, we would want a loop like:

for each key in the map's keyset
  print the key followed by a newline

You can use a for-each loop:

      for (String key : wordCount.keySet())
      {
         output.println(key);
      }

The Complete WordCount Program

The text file used in this example.

WordCount.java