24.19. Key Terms
| | 22.9. (Optional) Maps |
The Collection interface represents a collection of elements stored in a set or a list. The Map interface maps keys to the elements. The keys are like indexes. In List , the indexes are integers. In Map , the keys can be any objects. A map cannot contain duplicate keys. Each key maps to one value. The Map interface provides the methods for querying, updating, and obtaining a collection of values and a set of keys, as shown in Figure 22.21.
Figure 22.21. The Map interface maps keys to values.
The update methods include clear , put , putAll , and remove . The clear() method removes all mappings from the map. The put(Object key, Object value) method associates the specified value with the specified key in the map. If the map formerly contained a mapping for this key, the old value associated with the key is returned. The putAll(Map m) method adds the specified map to this map. The remove(Object key) method removes the map elements for the specified key from the map.
The query methods include containsKey , containsValue , isEmpty , and size . The containsKey(Object key) method checks whether the map contains a mapping for the specified key. The containsValue(Object value) method checks whether the map contains a mapping for this value. The isEmpty() method checks whether the map contains any mappings. The size() method returns the number of mappings in the map.
You can obtain a set of the keys in the map using the keySet() method, and a collection of the values in the map using the values() method. The entrySet() method returns a collection of objects that implement the Map.Entry interface, where Entry is an inner interface for the Map interface. Each object in the collection is a specific key-value pair in the underlying map.
The AbstractMap class is a convenience class that implements all the methods in the Map interface except the entrySet() method. The SortedMap interface extends the Map interface to maintain the mapping in ascending order of keys with additional methods firstKey() and lastKey() for returning the lowest and highest key, headMap(toKey) for returning the portion of the map whose keys are less than toKey , and tailMap(fromKey) for returning the portion of the map whose keys are greater than or equal to fromKey .
The HashMap , LinkedHashMap , and TreeMap classes are three concrete implementations of the Map interface, as shown in Figure 22.22.
Figure 22.22. The Java Collections Framework provides three concrete map classes.
The HashMap class is efficient for locating a value, inserting a mapping, and deleting a mapping.
LinkedHashMap was introduced in JDK 1.4. It extends HashMap with a linked list implementation that supports an ordering of the entries in the map. The entries in a HashMap are not ordered, but the entries in a LinkedHashMap can be retrieved either in the order in which they were inserted into the map (known as the insertion order ) or in the order in which they were last accessed, from least recently accessed to most recently accessed ( access order ). The no-arg constructor constructs a LinkedHashMap with the insertion order. To construct a LinkedHashMap with the access order, use the LinkedHashMap(initialCapacity, loadFactor, true) .
The TreeMap class, implementing SortedMap , is efficient for traversing the keys in a sorted order. The keys can be sorted using the Comparable interface or the Comparator interface. If you create a TreeMap using its no-arg constructor, the compareTo method in the Comparable interface is used to compare the elements in the set, assuming that the class of the elements implements the Comparable interface. To use a comparator, you have to use the TreeMap(Comparator comparator) constructor to create a sorted map that uses the compare method in the comparator to order the elements in the map based on the keys.
Note
| | Prior to JDK 1.2, Map was supported in java.util.Hashtable . Hashtable was redesigned to fit into the Java Collections Framework with all its methods retained for compatibility. Hashtable implements the Map interface and is used in the same way as HashMap except that Hashtable is synchronized. |
Listing 22.9 gives an example that creates a hash map, a linked hash map, and a tree map that map students to ages. The program first creates a hash map with the student's name as its key and the age as its value. The program then creates a tree map from the hash map and displays the mappings in ascending order of the keys. Finally, the program creates a linked hash map, adds the same entries to the map, and displays the entries. The output of the program is shown in Figure 22.23.
Figure 22.23. The program demonstrates the use of HashMap , LinkedHashMap , and TreeMap .
(This item is displayed on page 736 in the print version)
Listing 22.9. TestMap.java
(This item is displayed on pages 735 - 736 in the print version)
1 import java.util.*; 2 3 public class TestMap { 4 public static void main(String[] args) { 5 // Create a HashMap 6 Map<String, Integer> hashMap = new HashMap<String, Integer>(); 7 hashMap.put( "Smith" , 30 ); 8 hashMap.put( "Anderson" , 31 ); 9 hashMap.put( "Lewis" , 29 ); 10 hashMap.put( "Cook" , 29 ); 11 12 System.out.println( "Display entries in HashMap" ); 13 System.out.println(hashMap); 14 15 // Create a TreeMap from the previous HashMap 16 Map<String, Integer> treeMap = 17 new TreeMap<String, Integer>(hashMap); 18 System.out.println( "\nDisplay entries in ascending order of key" ); 19 System.out.println(treeMap); 20 21 // Create a LinkedHashMap 22 Map<String, Integer> linkedHashMap = 23 new LinkedHashMap<String, Integer>( 16 , 0.75f , true ); 24 linkedHashMap.put( "Smith" , 30 ); 25 linkedHashMap.put( "Anderson" , 31 ); 26 linkedHashMap.put( "Lewis" , 29 ); 27 linkedHashMap.put( "Cook" , 29 ); 28 29 // Display the age for Lewis 30 System.out.println( "The age for " + "Lewis is " + 31 linkedHashMap.get( "Lewis" ).intValue()); 32 33 System.out.println( "\nDisplay entries in LinkedHashMap" ); 34 System.out.println(linkedHashMap); 35 } 36 } |
As shown in Figure 22.23, the entries in the HashMap are in random order. The entries in the TreeMap are in increasing order of the keys. The entries in the LinkedHashMap are in the order of their access, from least recently accessed to most recently.
All the concrete classes that implement the Map interface have at least two constructors. One is the no-arg constructor that constructs an empty map, and the other constructs a map from an instance of Map . Thus new TreeMap<String, Integer>(hashMap) (line 16) constructs a tree map from a hash map.
You can create an insertion-ordered or access-ordered linked hash map. An access-ordered linked hash map is created in line 22. The most recently accessed entry is placed at the end of the map. The entry with the key Lewis is last accessed in line 30, so it is displayed last in line 33.
Tip
| | If you don't need to maintain an order in a map when updating it, use a HashMap , because less time is needed to insert and remove mappings in a HashMap . When you need to maintain the insertion order or access order in the map, use a LinkedHashMap . When you need the map to be sorted on keys, convert it to a tree map. |
22.9.1. Case Study: Occurrences of Words
This case study writes a program that counts the occurrences of words in a text and displays the words and their occurrences in ascending order of word frequency. The program uses a hash map to store a pair consisting of a word and its count. For each word, check whether it is already a key in the map. If not, add the key and value 1 to the map. Otherwise, increase the value for the word (key) by 1 in the map. To sort the map, convert it to a tree map.
Listing 22.10 gives the solution to the problem. The output of the program is shown in Figure 22.24.
Figure 22.24. The program finds the occurrences of each word in a text.
(This item is displayed on page 737 in the print version)
Listing 22.10. CountOccurrenceOfWords.java
(This item is displayed on pages 736 - 737 in the print version)
1 import java.util.*; 2 3 public class CountOccurrenceOfWords { 4 public static void main(String[] args) { 5 // Text in a string 6 String text = "Have a good day. Have a good class. " + 7 "Have a good visit. Have fun!" ; 8 9 // Create a hash map to hold words as key and count as value 10 Map<String, Integer> hashMap = new HashMap<String, Integer>(); 11 12 String[] words = text.split( "[ .!?]" ); 13 for ( int i = ; i < words.length; i++) { 14 if (words[i].length() > 1 ) { 15 if (hashMap.get(words[i]) != null ) { 16 int value = hashMap.get(words[i]).intValue(); 17 value++; 18 hashMap.put(words[i], value); 19 } 20 else 21 hashMap.put(words[i], 1 ); 22 } 23 } 24 25 // Create a tree map from the hash map 26 Map<String, Integer> treeMap = 27 new TreeMap<String, Integer>(hashMap); 28 29 // Display mappings 30 System.out.println( "Display words and their count in " + 31 "ascending order of the words" ); 32 System.out.print(treeMap); 33 } 34 } |
The pairs of words and their occurrence counts are stored in the map. The words serve as the keys. Since all elements in the map must be stored as objects, the count is wrapped in an Integer object.
The program extracts a word from a text using the split method in the String class and checks whether it is already stored as a key in the map (Line 15). If not, a new pair consisting of the word and its initial count ( 1 ) is stored to the map (line 21). Otherwise, the count for the word is incremented by 1 (lines 16 “18).
The program first stores the pairs in a hash map, then creates a tree map from the hash map (line 26). It then displays all the entries in the set. Each entry consists of a word and its count connected by the = sign in ascending order of word frequency. To display them in ascending order of the occurrence counts, see Exercise 22.7.
EAN: N/A
Pages: 503