J.9. Maps

Maps associate keys to values. The keys in a Map must be unique, but the associated values need not be. If a Map contains both unique keys and unique values, it’s said to implement a one-to-one mapping. If only the keys are unique, the Map is said to implement a many-to-one mapping—many keys can map to one value.

Maps differ from Sets in that Maps contain keys and values, whereas Sets contain only values. Three of the several classes that implement interface Map are Hashtable, HashMap and TreeMap, and maps are used extensively in Android. Hashtables and HashMaps store elements in hash tables, and TreeMaps store elements in trees—the details of the underlying data structures are beyond the scope of this book. Interface SortedMap extends Map and maintains its keys in sorted order—either the elements’ natural order or an order specified by a Comparator. Class TreeMap implements SortedMap. Figure J.9 uses a HashMap to count the number of occurrences of each word in a string.

Click here to view code image

 1   // Fig. J.9: WordTypeCount.java
 2   // Program counts the number of occurrences of each word in a String.
 3   import java.util.Map;
 4   import java.util.HashMap;
 5   import java.util.Set;
 6   import java.util.TreeSet;
 7   import java.util.Scanner;
 8
 9   public class WordTypeCount
10   {
11      public static void main( String[] args )
12      {
13         // create HashMap to store String keys and Integer values
14         Map< String, Integer > myMap = new HashMap< String, Integer >();
15
16         createMap( myMap ); // create map based on user input
17         displayMap( myMap ); // display map content
18      } // end main
19
20      // create map from user input
21      private static void createMap( Map< String, Integer > map )
22      {
23         Scanner scanner = new Scanner( System.in ); // create scanner
24         System.out.println( "Enter a string:" ); // prompt for user
25         String input = scanner.nextLine();
26
27         // tokenize the input
28         String[] tokens = input.split( " " );
29
30         // processing input text
31         for ( String token : tokens )
32         {
33            String word = token.toLowerCase(); // get lowercase word
34
35            // if the map contains the word
36            if ( map.containsKey( word ) ) // is word in map
37            {
38               int count = map.get( word ); // get current count
39               map.put( word, count + 1 ); // increment count
40            } // end if
41            else
42               map.put( word, 1 ); // add new word with a count of 1 to map
43         } // end for
44      } // end method createMap
45
46      // display map content
47      private static void displayMap( Map< String, Integer > map )
48      {
49         Set< String > keys = map.keySet(); // get keys
50
51         // sort keys
52         TreeSet< String > sortedKeys = new TreeSet< String >( keys );
53
54         System.out.println( " Map contains: Key Value" );
55
56         // generate output for each key in map
57         for ( String key : sortedKeys )
58            System.out.printf( "%-10s_s ", key, map.get( key ) );
59
60         System.out.printf(
61            " size: %d isEmpty: %b ", map.size(), map.isEmpty() );
62      } // end method displayMap
63   } // end class WordTypeCount

Fig. J.9 | Program counts the number of occurrences of each word in a String.

Line 14 creates an empty HashMap with a default initial capacity (16 elements) and a default load factor (0.75)—these defaults are built into the implementation of HashMap. When the number of occupied slots in the HashMap becomes greater than the capacity times the load factor, the capacity is doubled automatically. HashMap is a generic class that takes two type arguments—the type of key (i.e., String) and the type of value (i.e., Integer). Recall that the type arguments passed to a generic class must be reference types, hence the second type argument is Integer, not int.

Line 16 calls method createMap (lines 21–44), which uses a map to store the number of occurrences of each word in the sentence. Line 25 obtains the user input, and line 28 tokenizes it. The loop in lines 31–43 converts the next token to lowercase letters (line 33), then calls Map method containsKey (line 36) to determine whether the word is in the map (and thus has occurred previously in the string). If the Map does not contain a mapping for the word, line 42 uses Map method put to create a new entry in the map, with the word as the key and an Integer object containing 1 as the value. Autoboxing occurs when the program passes integer 1 to method put, because the map stores the number of occurrences of the word as an Integer. If the word does exist in the map, line 38 uses Map method get to obtain the key’s associated value (the count) in the map. Line 39 increments that value and uses put to replace the key’s associated value in the map. Method put returns the key’s prior associated value, or null if the key was not in the map.

Method displayMap (lines 47–62) displays all the entries in the map. It uses HashMap method keySet (line 49) to get a set of the keys. The keys have type String in the map, so method keySet returns a generic type Set with type parameter specified to be String. Line 52 creates a TreeSet of the keys, in which the keys are sorted. The loop in lines 57–58 accesses each key and its value in the map. Line 58 displays each key and its value using format specifier %-10s to left justify each key and format specifier _s to right justify each value. The keys are displayed in ascending order. Line 61 calls Map method size to get the number of key/value pairs in the Map. Line 61 also calls Map method isEmpty, which returns a boolean indicating whether the Map is empty.