Views, Subsets and Submaps

Map is not a Collection, and maps do not implement all the operations defined on collections. In particular, there are no iterators for maps. Sometimes, though, it’s useful to be able to iterate through all the associations in a map. Java makes this possible in a roundabout but clever way. If map is a variable of type Map<K,V>, then the method


map.keySet()

returns the set of all objects that occur as keys for associations in the map. The value returned by this method is an object that implements the interface Set<K>. The elements of this set are the map’s keys. The obvious way to implement the keySet() method would be to create a new set object, add all the keys from the map, and return that set. But that’s not how it’s done. The value returned by map.keySet() is not an independent object. It is what is called a view of the actual objects that are stored in the map. This “view” of the map implements the Set<K> interface, but it does it in such a way that the methods defined in the interface refer directly to keys in the map. For example, if you remove a key from the view, that key – along with its associated value – is actually removed from the map. It’s not legal to add an object to the view, since it doesn’t make sense to add a key to a map without specifying the value that should be associated to the key. Since map.keySet() does not create a new set, it’s very efficient, even for very large maps.

One of the things that you can do with a Set is get an Iterator for it and use the iterator to visit each of the elements of the set in turn. We can use an iterator (or a for-each loop) for the key set of a map to traverse the map. For example, if map is of type Map<String,Double>, we could write:


Set keys = map.keySet();     // The set of keys in the map.
Iterator keyIter = keys.iterator();
System.out.println("The map contains the following associations:");
while (keyIter.hasNext()) {
   String key = keyIter.next();  // Get the next key.
   Double value = map.get(key);  // Get the value for that key.
   System.out.println( "   (" + key + "," + value + ")" );
}

Or we could do the same thing more easily, avoiding the explicit use of an iterator, with a for-each loop:


System.out.println("The map contains the following associations:");
for ( String key : map.keySet() ) { // "for each key in the map's key set"
   Double value = map.get(key);
   System.out.println( " (" + key + "," + value + ")" );
}

If the map is a TreeMap, then the key set of the map is a sorted set, and the iterator will visit the keys in ascending order. For a HashMap, the keys are visited in an arbitrary, unpredictable order.

The Map interface defines two other views. If map is a variable of type Map<K,V>, then the method:


map.values()

returns an object of type Collection<V> that contains all the values from the associations that are stored in the map. The return value is a Collection rather than a Set because it can contain duplicate elements (since a map can associate the same value to any number of keys). The method:


map.entrySet()

returns a set that contains all the associations from the map. The elements in the set are objects of type Map.Entry<K,V>Map.Entry<K,V> is defined as a static nested interface inside the interface Map<K,V>, so its full name contains a period. However, the name can be used in the same way as any other type name. (The return type of the method map.entrySet() is written as Set<Map.Entry<K,V>>. The type parameter in this case is itself a parameterized type. Although this might look confusing, it’s just Java’s way of saying that the elements of the set are of type Map.Entry<K,V>.)

The information in the set returned bymap.entrySet() is actually no different from the information in the map itself, but the set provides a different view of this information, with different operations. Each Map.Entry object contains one key/value pair, and defines methods getKey() and getValue() for retrieving the key and the value. There is also a method, setValue(value), for setting the value; calling this method for a Map.Entry object will modify the map itself, just as if the map’s put method were called. As an example, we can use the entry set of a map to print all the key/value pairs in the map. This is more efficient than using the key set to print the same information, as we did in the above example, since we don’t have to use the get() method to look up the value associated with each key. Suppose again that map is of type Map<String,Double>. Then we can write:


Set<Map.Entry<String,Double>> entries = map.entrySet();
Iterator<Map.Entry<String,Double>> entryIter = entries.iterator();
System.out.println("The map contains the following associations:");
while (entryIter.hasNext()) {
   Map.Entry<String,Double> entry = entryIter.next();
   String key = entry.getKey();  // Get the key from the entry.
   Double value = entry.getValue();  // Get the value.
   System.out.println( "   (" + key + "," + value + ")" );
}

or, using a for-each loop:


System.out.println("The map contains the following associations:");
for ( Map.Entry<String,Double> entry : map.entrySet() )
   System.out.println( "   (" + entry.getKey() + "," + entry.getValue() + ")" );

Next: Hash Tables and Hash Codes