Map functionality

An ArrayList allows you to select from a sequence of objects using a number, so in a sense it associates numbers to objects. But what if you’d like to select from a sequence of objects using some other criterion? A stack is an example. Its selection criterion is “the last thing pushed on the stack.” A powerful twist on this idea of “selecting from a sequence” is termed a map, a dictionary, or an associative array (you saw a simple example of this in AssociativeArray.java in the previous chapter). Conceptually, it seems like an ArrayList, but instead of looking up objects using a number, you look them up using another object! This is a key technique in programming.

The concept shows up in Java as the Map interface. The put(Object key, Object value) method adds a value (the thing you want) and associates it with a key (the thing you look it up with). get(Object key) produces the value given the corresponding key. You can also test a Map to see if it contains a key or a value with containsKey( ) and containsValue( ).

The standard Java library contains different types of Maps: HashMap, TreeMap, LinkedHashMap, WeakHashMap, and IdentityHashMap. The all have the same basic Map interface, but they differ in behaviors including efficiency, order in which the pairs are held and presented, how long the objects are held by the map, and how key equality is determined.

A big issue with maps is performance. If you look at what must be done for a get( ), it seems pretty slow to search through (for example) an ArrayList for the key. This is where HashMap speeds things up. Instead of a slow search for the key, it uses a special value called a hash code. The hash code is a way to take some information in the object in question and turn it into a “relatively unique” int for that object. All Java objects can produce a hash code, and hashCode( ) is a method in the root class Object. A HashMap takes the hashCode( ) of the object and uses it to quickly hunt for the key. This results in a dramatic performance improvement.^[58]

Hashing is the most commonly used way to store elements in a map. Sometimes you’ll need to know the details of how hashing works, so we’ll look at that a little later.

The following example uses the Collections2.fill( ) method and the test data sets that were previously defined:

//: c11:Map1.java
// Things you can do with Maps.
import java.util.*;
import com.bruceeckel.util.*;

public class Map1 {
  private static Collections2.StringPairGenerator geo =
    Collections2.geography;
  private static Collections2.RandStringPairGenerator
    rsp = Collections2.rsp;
  // Producing a Set of the keys:
  public static void printKeys(Map map) {
    System.out.print("Size = " + map.size() + ", ");
    System.out.print("Keys: ");
    System.out.println(map.keySet());
  }
  public static void test(Map map) {
    // Strip qualifiers from class name:
    System.out.println(
      map.getClass().getName().replaceAll("\\w+\\.", ""));
    Collections2.fill(map, geo, 25);
    // Map has 'Set' behavior for keys:
    Collections2.fill(map, geo.reset(), 25);
    printKeys(map);
    // Producing a Collection of the values:
    System.out.print("Values: ");
    System.out.println(map.values());
    System.out.println(map);
    String key = CountryCapitals.pairs[4][0];
    String value = CountryCapitals.pairs[4][1];
    System.out.println("map.containsKey(\"" + key +
      "\"): " + map.containsKey(key));
    System.out.println("map.get(\"" + key + "\"): "
      + map.get(key));
    System.out.println("map.containsValue(\""
      + value + "\"): " + map.containsValue(value));
    Map map2 = new TreeMap();
    Collections2.fill(map2, rsp, 25);
    map.putAll(map2);
    printKeys(map);
    key = map.keySet().iterator().next().toString();
    System.out.println("First key in map: " + key);
    map.remove(key);
    printKeys(map);
    map.clear();
    System.out.println("map.isEmpty(): " + map.isEmpty());
    Collections2.fill(map, geo.reset(), 25);
    // Operations on the Set change the Map:
    map.keySet().removeAll(map.keySet());
    System.out.println("map.isEmpty(): " + map.isEmpty());
  }
  public static void main(String[] args) {
    test(new HashMap());
    test(new TreeMap());
    test(new LinkedHashMap());
    test(new IdentityHashMap());
    test(new WeakHashMap());
  }
} ///:~

The printKeys( ) and printValues( ) methods are not only useful utilities, they also demonstrate how to produce Collection views of a Map. The keySet( ) method produces a Set backed by the keys in the Map. Similar treatment is given to values( ), which produces a Collection containing all the values in the Map. (Note that keys must be unique, but values may contain duplicates.) Since these Collections are backed by the Map, any changes in a Collection will be reflected in the associated Map.

The rest of the program provides simple examples of each Map operation and tests each type of Map.

As an example of the use of a HashMap, consider a program to check the randomness of Java’s Random class. Ideally, it would produce a perfect distribution of random numbers, but to test this you need to generate a bunch of random numbers and count the ones that fall in the various ranges. A HashMap is perfect for this, since it associates objects with objects (in this case, the value object contains the number produced by Math.random( ) along with the number of times that number appears):

//: c11:Statistics.java
// Simple demonstration of HashMap.
import java.util.*;

class Counter {
  int i = 1;
  public String toString() { return Integer.toString(i); }
}

public class Statistics {
  private static Random rand = new Random();
  public static void main(String[] args) {
    Map hm = new HashMap();
    for(int i = 0; i < 10000; i++) {
      // Produce a number between 0 and 20:
      Integer r = new Integer(rand.nextInt(20));
      if(hm.containsKey(r))
        ((Counter)hm.get(r)).i++;
      else
        hm.put(r, new Counter());
    }
    System.out.println(hm);
  }
} ///:~

In main( ), each time a random number is generated it is wrapped inside an Integer object so that reference can be used with the HashMap. (You can’t use a primitive with a container—only an object reference.) The containsKey( ) method checks to see if this key is already in the container (that is, has the number been found already?). If so, the get( ) method produces the associated value for the key, which in this case is a Counter object. The value i inside the counter is incremented to indicate that one more of this particular random number has been found.

If the key has not been found yet, the method put( ) will place a new key-value pair into the HashMap. Since Counter automatically initializes its variable i to one when it’s created, it indicates the first occurrence of this particular random number.

To display the HashMap, it is simply printed. The HashMap toString( ) method moves through all the key-value pairs and calls the toString( ) for each one. The Integer.toString( ) is predefined, and you can see the toString( ) for Counter. The output from one run (with some line breaks added) is:

{15=529, 4=488, 19=518, 8=487, 11=501, 16=487, 18=507, 3=524, 7=474, 12=485, 17=493, 2=490, 13=540, 9=453, 6=512, 1=466, 14=522, 10=471, 5=522, 0=531} 

You might wonder at the necessity of the class Counter, which seems like it doesn’t even have the functionality of the wrapper class Integer. Why not use int or Integer? Well, you can’t use an int because all of the containers can hold only Object references. After you’ve seen containers, the wrapper classes might begin to make a little more sense to you, since you can’t put any of the primitive types in containers. However, the only thing you can do with the Java wrappers is initialize them to a particular value and read that value. That is, there’s no way to change a value once a wrapper object has been created. This makes the Integer wrapper immediately useless to solve the problem, so we’re forced to create a new class that does satisfy the need.

Thinking in Java
Prev	Contents / Index	Next