Main Page

Previous Next

Using Maps

As we saw at the beginning of this chapter, a map is a way of storing data that minimizes the need for searching when you want to retrieve an object. Each object is associated with a key that is used to determine where to store the reference to the object, and both the key and the object are stored in the map. Given a key, you can always go more or less directly to the object that has been stored in the map based on the key. It's important to understand a bit more about how the storage mechanism works for a map, and in particular what the implications of using the default hashing process are. We will explore the use of maps primarily in the context of the HashMap class.

The Hashing Process

A map sets aside an array in which it will store key and object pairs. The index to this array is produced from the key object by using the hash code for the object to compute an offset into the array for storing key/object pairs. By default, this uses the hashCode() method for the object that's used as a key. This is inherited in all classes from Object.

Note that, while every key must be unique, each key doesn't have to result in a unique hash code. When two or more different keys produce the same hash value, it's called a collision. A HashMap object deals with collisions by storing all the key/object pairs that have the same hash value in a linked list. If this occurs very often, it is obviously going to slow up the process of storing and retrieving data. Retrieving an object that resulted in a collision when it was stored will be a two-stage process. The key will be hashed to find the location where the key/object pair should be. The linked-list will then have to be searched to sort out the particular key we are searching on from all the others that have the same hash value.

Click To expand

There is therefore a strong incentive to minimize collisions and the price of reducing the possibility of collisions in a hash table is having plenty of empty space in the table.

The class Object defines the method hashCode() so any object can be used as a key and it will hash by default. The method as it is implemented in Object in Java, however, isn't a panacea. Since it usually uses the memory address where an object is stored to produce the hash value, distinct objects will always produce different hash values. In one sense this is a plus, because the more likely it is that a unique hash value will be produced for each key, the more efficient the operation of the hash map is going to be. The downside is that different object instances that have identical data will produce different hash values, so you can't compare them.

This becomes a nuisance if you use the default hashCode() method in objects that you're using as keys. In this case, an object stored in a hash map can never be retrieved using a different key object instance, even though that key object may be identical in all other respects. Yet this is precisely what you'll want to do in many cases.

Consider an application such as a simple address book. You might store map entries keyed on the names of the people to whom the entries relate, and you would want to search the map based on a name that was entered from the keyboard. However, the object representing the newly entered name is inevitably going to be distinct from that used as a key for the entry. Using the former, you will not be able to find the entry corresponding to the name.

The solution to this problem is somehow to make a hash of the instance variables of the object. Then, by comparing the values of the data members of the new name object with those for the name objects used as keys in the hash map, you'll be able to make a match.

Using Your Own Class Objects as Keys

For objects of one of your own classes to be usable as keys in a hash table, you must override the equals() method of the Object class. In its default form, equals() accepts an object of the same class as an argument and returns a boolean value. The equals() method is used by methods in the HashMap class to determine when two keys are equal, so, in order to enable the changes discussed in the previous section, your version of this method should return true when two different objects contain identical data values.

You can also override the default hashCode()method, which returns the hash value for the object as type int. The hashCode() method is used to generate the int value that is the key. Your hashCode() method should produce hash codes that are reasonably uniform over the possible range of keys and generally unique for each key.

Generating Hash Codes

The various techniques for generating hash codes form a big topic, and we can only scratch the surface here. How you write the hashCode() method for your class is up to you, but it needs to meet certain requirements if it is to be effective. You should aim to return a number of type int for an object that has a strong probability of being unique to that object, and the numbers that you produce for several different objects should be as widely distributed across the range of int values as possible.

To achieve the uniqueness, you will typically want to combine the values of all the data members in an object to produce the hash code, so the first step is to produce an integer corresponding to each data member. You must then combine these integers to generate the return value that will be the hash code for the object. One technique you can use to do this is to multiply each of the integers corresponding to the data members by a different prime number and then sum the results. This should produce a reasonable distribution of values that have a good probability of being different for different objects. It doesn't matter which prime numbers you use as multipliers, as long as:

  • They aren't so large as to cause the result to fall outside the range of type int

  • You use a different one for each data member

So how do you get from a data member of a class to an integer? Generating an integer for data members of type String is easy: you just call the hashCode() method for the member. This has been implemented in the String class to produce good hash code values that will be the same for identical strings (take a look at the source code if you want to see how). You can use integer data members as they are, but floating point data members need a bit of judgment. If they have a small range in integer terms, you need to multiply them by a value that's going to result in a unique integer when they are cast to type int. If they have a very large range in integer terms you may need to scale them down.

Suppose you intended to use a Person object as a key in a hash table, and the class data members were firstName and surname of type String, and age of type int. You could implement the hashCode() method for the class as:

public int hashCode() {
  return 13*firstName.hashCode() + 17*surname.hashCode() + 19*age;
}

Wherever a data member is an object of another class rather than a variable of one of the basic types, you need to implement the hashCode() method for that class. You can then use that in the computation of the hash code for the key class.

Creating a HashMap

As we saw, all map classes implement the Map interface, so an object of any map class can be referenced using a variable of type Map. We will look in detail at the HashMap class since it is good for most purposes. There are four constructors you can use to create a HashMap object:

Constructor

Description

HashMap()

Creates a map with the capacity to store a default number of objects. The default capacity is 101 objects and the default load factor (more on the load factor below) is 0.75.

HashMap(int capacity)

Creates a map with the capacity to store the number of objects you specify in the argument and a default load factor of 0.75.

HashMap(int capacity, float loadFactor)

Creates a hash table with the capacity and load factor that you specify.

HashMap(Map map)

Creates a map with the capacity and load factor of the Map object passed as an argument.

To create a map using the default constructor, you can write something like this:

HashMap theMap = new HashMap();

The capacity for a map is simply the number of key/object pairs it can store. The capacity increases automatically as necessary, but this is a relatively time consuming operation. The capacity value of the map is combined with the hash code for the key that you specify to compute the index that determines where an object and its key are to be stored. To make this computation produce a good distribution of index values, you should ideally use prime numbers for the capacity of a hash table when you specify it yourself. For example:

HashMap myMap = new HashMap(151);

This map has a capacity for 151 objects and their keys, although the number of objects stored can never actually reach the capacity. There must always be spare capacity in a map for efficient operation. With too little spare capacity, there is an increased likelihood that keys will generate the same table index, so collisions become more likely.

The load factor is used to decide when to increase the size of the hash table. When the size of the table reaches a value which is the product of the load factor and the capacity, the capacity will be increased automatically to twice the old capacity plus 1 – the plus one ensuring it is at least odd, if not prime. The default load factor of 0.75 is a good compromise, but if you want to reduce it you could do so by using the third constructor:

HashMap aMap = new HashMap(151, 0.6f);  // 60% load factor

This map will work a bit more efficiently than the current default, but at the expense of having more unoccupied space. When 90 objects have been stored, the capacity will be increase to 303, (2*151+1).

Storing, Retrieving, and Removing Objects

Storing, retrieving, and removing objects in a HashMap is very simple. The four methods involved in this are:

Method

Description

put(Object key, Object value)

Stores the object value in the map using the key specified by the first argument. value will displace any existing object associated with key. The ejected object will be returned as type Object. If no object is stored at that map location or the key was used to store null as an object, null is returned.

putAll(Map map)

Transfers all the key/object pairs from map to the current map, replacing any objects that exist with the same keys.

get(Object key)

Returns the object stored with the same key as the argument. If no object was stored with this key or null was stored as the object, null is returned. Note that the object remains in the table.

remove(Object key)

Removes the entry associated with key if it exists, and returns the object as type Object. A null is returned if the entry does not exist, or if null was stored using key.

Any kind of object can be stored in a map, since all objects are stored as type Object. As with objects stored in a Vector, you can cast an object back to its original type when you retrieve it. The same caveats we saw for Vector objects, relating to the potential for storing objects of different types, apply to hash maps. If you want to limit the type of object that can be stored, you can use a HashMap object as a member of your own class, and implement its interface get(), put(), and putAll() methods yourself, to restrict what can be stored.

If you attempt to retrieve an object using get() and a null is returned, it is still possible that a null was stored as the object associated with the key that you supplied to the get() method. You can determine if this is the case by passing your key object to the containsKey() method for the map. This will return true if the key is stored in the map.

You should check that the value returned from the put() method is null. If you don't, you may unwittingly displace an object that was stored in the table earlier using the same key:

String myKey = "Goofy";
Integer theObject = new Integer(12345);

if(aMap.put(myKey, theObject) != null)
  System.out.println("Uh-oh, we bounced an object...");

Of course, you could throw your own exception here instead of displaying a message.

Note that the get() operation will return a reference to the object associated with the key, but it does not remove it from the table. To retrieve an object and delete the entry containing it from the table, you must use the remove() method. This accepts a key of type Object as an argument and returns the object corresponding to the key:

theObject = (Integer)aMap.remove(theKey);

As was noted in the table, if there's no stored object corresponding to theKey or null was stored as the object, null will be returned. Note how we have to explicitly cast the object returned from the hash map to the correct class.

Processing all the Elements in a Map

The Map interface provides three ways of obtaining a collection view of the contents of a map. You can obtain all the keys or all the key/object pairs from a Map object as an object of type Set. You can also

get a Collection object that references all the objects in the map. Note that the Set or Collection object is essentially a view of the contents of a map, so changes to a HashMap object will be reflected in the associated Set or Collection, and vice versa. The three methods involved are:

Method

Description

keySet()

Returns a Set object referencing the keys from the map.

entrySet()

Returns a Set object referencing the key/object pairs – each pair being an object of type Map.Entry.

values()

Returns a Collection object referencing the objects stored in the map.

The type of the key/object pairs in the set returned by entrySet() looks a little unusual. The key/object pairs are of type Map.Entry because Entry is an interface declared within the Map interface.

Let's first see how we can use a set of keys. The method keySet() for the HashMap class returns a Set object referencing the set of keys that you can either use directly to access the keys or use indirectly to get at the objects stored in the map. For a HashMap object aMap, you could get the set of all the keys in the map with the statement:

Set keys = aMap.keySet();

Now you can get an iterator for this set of keys with the statement:

Iterator keyIter = keys.iterator();

You can use the iterator() method for the object keys to iterate over all the keys in the map. Of course, you can combine these two operations to get the iterator directly. For example:

Iterator keyIter = aMap.keySet().iterator();           // Get the iterator

while(keyIter.hasNext())                               // Iterate over the keys
  System.out.println((KeyType)keyIter.next());

This iterates over all the keys and outputs their String representation – KeyType in this fragment represents the class type of the keys.

The method entrySet() returns a Set object referencing the key/object pairs. In a similar way to the one that we used for the set of keys, you can obtain an iterator to make the Map.Entry objects available. Each Map.Entry object will contain the following methods to operate on it:

Method

Description

getKey()

Returns the key for the Map.Entry object as type Object.

getValue()

Returns the object for the Map.Entry object as type Object.

setValue(Object new)

Sets the object for this Map.Entry object to the argument and returns the original object. Remember that this alters the original map. This method throws:

UnsupportedOperationException if put() is not supported by the underlying map.

ClassCastException if the argument cannot be stored because of its type.

IllegalArgumentException if the argument is otherwise invalid.

NullPointerException if the map does not allow null objects to be stored. This last exception does not apply to HashMap.

A Map.Entry object will also need an equals() method for comparisons with another Map.Entry object passed as an argument and a hashCode() method to compute a hash code for the Map.Entry object. With a set of Map.Entry objects you can obviously access the keys and the corresponding objects by obtaining an iterator, and you can modify the object part of each key/object pair if you need to.

Finally the values() method for a HashMap object will return a Collection object that is a collection of all the objects in the map. This enables you to use the iterator() member to obtain an iterator for the collection of objects.

We have waded through a lot of the theory for HashMap objects; let's put together an example that applies it.

We can put together a very simple phone book that uses a map. We won't worry too much about error recovery so that we don't bulk up the code too much. We will reuse the Person class that we saw earlier, and the FormattedInput class with the modified version of the readString() method, plus the InvalidUserInputException class, so copy them to a new directory called TryHashMap or something similar. Besides the Person class we will need a PhoneNumber class, plus an Entry class that represents an entry in our phone book combining the name and number. We could add other stuff such as the address, but this is not necessary to show the principles. We will also define a PhoneBook class to represent the phone book.

Try It Out – Using a HashMap Map

We need to improve our old Person class to make Person objects usable as keys in the map that we will use – to store the phone book entries. We must add an equals() method and we'll override the default hashCode() method just to show how this can work. The extended version of the class will be as follows:

public class Person implements Comparable, Serializable {
  public boolean equals(Object person) {
    return compareTo(person) == 0;
  }

  public int hashCode() {
    return 7*firstName.hashCode()+13*surname.hashCode();
  }

  // The rest of the class as before...
}

Since the String class defines a good hashCode() method, we can easily produce a hash code for a Person object from the data members. To implement the equals() method we just call the method that we implemented for the Comparable interface. As it is likely to be required in this application, we have made the class serializable

There's another thing we could do that will be useful. We could add a static method to read data for a Person object from the keyboard:

import java.io.*;

public class Person implements Comparable, Serializable {
  // Read a person from the keyboard
  public static Person readPerson() {
    FormattedInput in = new FormattedInput();
    // Read in the first name and remove blanks front and back
    System.out.println("\nEnter first name:");
    String firstName = in.readString().trim();
    // Read in the surname, also trimming blanks
    System.out.println("Enter surname:");
    String surname = in. readString ().trim();
    return new Person(firstName,surname);
  }

  // Rest of the class as before...
}

You should have no trouble seeing how this works as it's almost identical to the readPerson() method we used previously.

We can make the PhoneNumber class very simple:

class PhoneNumber implements Serializable {
  public PhoneNumber(String areacode, String number) {
    this.areacode = areacode;
    this.number = number;
 
 }

  public String toString() {
    return areacode + ' ' + number;  
  }

  private String areacode;
  private String number;
}

We could do a whole lot of validity checking of the number here, but it's not important for our example.

We could use a static method to read a number from the keyboard so let's add that too:

import java.io.*;

class PhoneNumber implements Serializable {
  // Read a phone number from the keyboard
  public static PhoneNumber readNumber() {
    FormattedInput in = new FormattedInput();

    int maxTries = 5;                                  // Maximum number of errors
                                                       // in input
    String area = null;                                // Stores the area code
    String localcode = null;                           // Stores the local code

    for(;;) {                                          // Loop to allow retries
      try {
        // Read in the area code
        if(area == null) {                             // If there's no area code
          System.out.println("\nEnter the area code:");
          area = Integer.toString(in.readInt());       // read one from the k/b
        }
        // Read in the number
        if(localcode == null) {                        // If there's no local code
          System.out.println("Enter the local code:");
          localcode = Integer.toString(in.readInt());  // read one from the k/b
        }

        System.out.println("Enter the number:");      
        String code = Integer.toString(in.readInt());  // Read last part of the 
                                                       // number
        localcode += " " + code;                       // and append to local code
        return new PhoneNumber(area,localcode);

      } catch(InvalidUserInputException e) {
        if(--maxTries == 0) {                  //  If there were maxTries errors
          System.out.println("Maximum number of errors exceeded. Terminating...");
          System.exit(1);                             // then quit
        }
        System.err.println(e.getMessage()+"\nTry again");
        continue;                                     // otherwise try again
      }
    }
  }

  // Rest of the class as before...
}

This is again similar to the readPerson() method except that we read the parts of the telephone number as integers and convert them to String objects. If you wanted to read them as String objects, then they would need to be entered between quotes if spaces are to be permitted. We allow for errors in the input here by reading the component parts of a number in a loop. If an invalid character is entered when reading a value, the String reference will be left as null. By testing for area and localcode being null before we read a value, we ensure that only the component that was in error needs to be reentered. If after five tries it's still not correct, we end the program.

An entry in the phone book will combine the name and the number, and would probably include other things such as the address. We can get by with the basics:

import java.io.*;

class BookEntry implements Serializable {
  public BookEntry(Person person, PhoneNumber number) {
   this.person = person;
    this.number = number;
  }

  public Person getPerson() {
    return person;  
  }

  public PhoneNumber getNumber() {
    return number;  
  }

  public String toString() {
    return person.toString() + '\n' + number.toString();
  }

  // Read an entry from the keyboard
  public static BookEntry readEntry() {
    return new BookEntry(Person.readPerson(), PhoneNumber.readNumber());
  }

  private Person person;
  private PhoneNumber number;
}

This is all pretty standard stuff. In the static method readEntry(), we just make use of the methods that read Person and PhoneNumber objects so this becomes very simple.

Now we come to the class that implements the phone book – called the PhoneBook class, of course:

import java.io.*;
import java.util.*;

class PhoneBook implements Serializable {
  public void addEntry(BookEntry entry) {
    phonebook.put(entry.getPerson(), entry);
  }

  public BookEntry getEntry(Person key) {
    return (BookEntry)phonebook.get(key);  
  }

  public PhoneNumber getNumber(Person key) {
    return getEntry(key).getNumber();  
  }

  private HashMap phonebook = new HashMap();
}

To store BookEntry objects we use a HashMap member, phonebook. We will use the Person object corresponding to an entry as the key, so the addEntry() method only has to retrieve the Person object from the BookEntry object that is passed to it, and use that as the first argument to the put() method for phonebook. Note that when we retrieve an entry, we must cast the object that is returned by the get() method to the BookEntry type, as get() returns type Object. All we need now is a class containing main() to test these classes:

class TryPhoneBook {
  public static void main(String[] args) {
    PhoneBook book = new PhoneBook();                 // The phone book
    FormattedInput in = new FormattedInput();         // Keyboard input
    Person someone;
for(;;) {
      System.out.println("Enter 1 to enter a new phone book entry\n"+
                         "Enter 2 to find the number for a name\n"+
                         "Enter 9 to quit.");
      int what = 0;                                  // Stores input selection
      try {
        what = in.readInt();

      } catch(InvalidUserInputException e) { 
        System.out.println(e.getMessage()+"\nTry again.");
        continue;
      }      

      switch(what) {
        case 1:
          book.addEntry(BookEntry.readEntry());
          break;
        case 2:
          someone = Person.readPerson();
          BookEntry entry = book.getEntry(someone);
          if(entry == null)
            System.out.println("The number for " + someone +
                               " was not found. ");
          else           
            System.out.println("The number for " + someone +
                               " is " + book.getEntry(someone).getNumber());
          break;
        case 9:
          System.out.println("Ending program.");
          return;
        default:
          System.out.println("Invalid selection, try again.");
          break;
      }
    }
  }
}

This is what the example produces with my input:

Enter 1 to enter a new phone book entry
Enter 2 to find the number for a name
Enter 9 to quit.
1
Enter first name:
Slim
Enter surname:
Pickens
Enter the area code:
914
Enter the local code:
238
Enter the number:
6778
Enter 1 to enter a new phone book entry
Enter 2 to find the number for a name
Enter 9 to quit.
2

Enter first name:
Slim
Enter surname:
"Pickens"
The number for Slim Pickens is 914 238 6778
Enter 1 to enter a new phone book entry
Enter 2 to find the number for a name
Enter 9 to quit.
9
Ending program.

Of course, you can try it with several entries if you have the stamina.

How It Works

The main() method runs an ongoing loop that will continue until a 9 is entered. When a 1 is entered, the addEntry() method for the PhoneBook object is called with the expression BookEntry.readEntry() as the argument. The static method readEntry() calls the static methods in the Person class and the PhoneNumber class to read from the keyboard and create objects of these classes. The readEntry() method then passes these objects to the constructor for the BookEntry class, and the object that is created is returned. This object will be added to the HashMap member of the PhoneBook object.

If a 2 is entered, the getEntry() method is called. The argument expression calls the readPerson() member of the Person class to obtain the Person object corresponding to the name entered from the keyboard. This object is then used to retrieve an entry from the map in the PhoneBook object. Of course, if there is no such entry null will be returned, so we have to check for it and act accordingly.

Storing a Map in a File

This phone book is not particularly useful. The process of echoing what we just keyed in doesn't hold one's interest for long. What we need is a phone book that is held in a file. That's not difficult. We just need to add a constructor and another method to the PhoneBook class:

import java.util.*;
import java.io.*;
class PhoneBook implements Serializable {
  public PhoneBook() {
    if(filename.exists())
    try {
      ObjectInputStream in = new ObjectInputStream(
      new FileInputStream(filename));
      phonebook = (HashMap)in.readObject();
      in.close();

    } catch(ClassNotFoundException e) {
      System.out.println(e);

    } catch(IOException e) {
      System.out.println(e);
    }
  }

  public void save() {
    try {
      System.out.println("Saving phone book");
      ObjectOutputStream out = new ObjectOutputStream(
      new FileOutputStream(filename));
      out.writeObject(phonebook);
      System.out.println(" Done");
      out.close();

    } catch(IOException e) {
      System.out.println(e);
    }
  }

  private File filename = new File("Phonebook.bin"); 

  // Other members of the class as before...
}

The new private data member, filename, defines the name of the file where the map holding the phone book entries is to be stored. Since we have only specified the file name and extension, the file will be assumed to be in the current directory. The filename object is used in the constructor that now reads the HashMap object from the file if it exists. If it doesn't exist it does nothing and the PhoneBook object will use the default empty HashMap object.

The save() method provides for storing the map away, so we will need to call this method before ending the program. To make it a little more interesting we could add a method to list all the entries in a phone book:

import java.util.*;
import java.io.*;
class PhoneBook implements Serializable {
  // List all entries in the book
  public void listEntries() {
    // Get the keys as a list
    LinkedList persons = new LinkedList(phonebook.keySet());
    Collections.sort(persons);                     // Sort the keys
    Iterator iter = persons.iterator();            // Get iterator for sorted keys

    while(iter.hasNext())
      System.out.println(phonebook.get((Person)iter.next()));
  }

  // Other members as before...
}

If we want to list the entries in name sequence we have to do a little work. The keySet() method in HashMap returns a Set object for the keys, which are Person objects, but these will not be ordered in any way. By creating a LinkedList object from the set, we obtain a collection that we can sort using the sort() method from the Collections class. Finally we get an iterator to go through the HashMap using the keys in alphabetical order in the collection.

We can update main() to take advantage of the new features of the PhoneBook class:

class TryPhoneBook {
  public static void main(String[] args) {
    PhoneBook book = new PhoneBook();                 // The phone book
    FormattedInput in = new FormattedInput();         // Keyboard input
    Person someone;

    for(;;) {
      System.out.println("Enter 1 to enter a new phone book entry\n"+
                         "Enter 2 to find the number for a name\n"+
                         "Enter 3 to list all the entries\n" +
                         "Enter 9 to quit.");
      int what = 0;
      try {
        what = in.readInt();

      } catch(InvalidUserInputException e) { 
        System.out.println(e.getMessage()+"\nTry again.");
        continue;
      }      

      switch(what) {
        case 1:
          book.addEntry(BookEntry.readEntry());
          break;
        case 2:
          someone = Person.readPerson();
          BookEntry entry = book.getEntry(someone);
          if(entry == null)
            System.out.println("The number for " + someone +
                               " was not found. ");
          else           
            System.out.println("The number for " + someone +
                               " is " + book.getEntry(someone).getNumber());
          break;
        case 3:
          book.listEntries();
          break;
        case 9:
          book.save();
          System.out.println("Ending program.");
          return;
        default:
          System.out.println("Invalid selection, try again.");
          break;
      }
    }
  }
}

How It Works

The first changes here are an updated prompt for input and a new case in the switch to list the entries in the phone book. The other change is to call the save() method to write the map that stores the phone book to a file before ending the program.

Important 

Be aware of the default hashCode() method in the Object class when storing maps. The hash codes are generated from the address of the object, and getting a key object back from a file in exactly the same place in memory is about as likely as finding hairs on a frog. The result is that the hashcode generated from the key when it is read back will be different from when it was originally produced, so you will never find the entry in the map to which it corresponds.

If we override the default hashCode() method then our hash codes are produced from the data members of the key objects, so they are always the same regardless of where the key objects are stored in memory.

The first time you run this version of TryPhoneBook it will create a new file and store the entire phone book in it. On subsequent occasions the PhoneBook constructor will read from the file, so all the previous entries are available.

In the next chapter we'll move on to look at some of the other components from the java.util package.

Previous Next
JavaScript Editor Java Tutorials Free JavaScript Editor