Section 12.3
Map Classes
AN ARRAY OF N ELEMENTS can be thought
of as a way of associating some item with each of the integers
0, 1, ..., N-1. If i is
one of these integers, it's possible to get
the item associated with i, and it's possible to
put a new item in the i-th position.
These "get" and "put" operations define what it means to be an array.
A Map is a kind of generalized array.
Like an array, a map is defined by "get" and "put" operations.
But in a map, these operations are defined not for integers
0, 1, ..., N-1, but for arbitrary
Objects. In fact, some programming languages use the
term associative array instead of "map"
and use the same notation for associative arrays as for regular
arrays. In those languages, for example, you might see the notation
A["fred"] used to indicate the item associated to the string
"fred" in the associative array A. Java does not use array notation
for maps, but the idea is that same: A map is like an array, but
the indices for a map are arbitrary objects, not integers.
In a map, an object that serves as an "index" is called a
key. The object that is associated
with a key is called a value.
Note that a key can have at most one associated value, but the same
value can be associated to several different keys.
In Java, maps are defined by the interface java.util.Map,
which includes put and get methods as well as
other general methods for working with maps. If map is
a variable of type Map, then these are some of the methods
that are defined for map:
- map.get(key) -- returns the
Object that is associated by the map to the Object key.
If the map does not associate any value with obj, then the return
value is null. Note that it's also possible for the return
value to be null when the map explicitely associates the
value null with the key.
Referring to "map.get(key)" is similar to referring to "A[key]"
for an array A. (But note that there is nothing like an
IndexOutOfBoundsException for maps.)
- map.put(key,value) --
Associates the specified value with the specified key,
where key and value can be any objects. If the
map already associated some other value with the key, then the new
value replaces the old one.
This is similar to the command "A[key] = value"
for an array.
- map.putAll(map2) -- if
map2 is any other map, this copies all the associations
from map2 into map.
- map.remove(key) --
if map associates a value to the specified key,
that association is removed from the map.
- map.containsKey(key) -- returns
a boolean value that is true if the map associates some
value to the specified key.
- map.containsValue(value) -- returns
a boolean value that is true if the map associates the
specified value to some key.
- map.size() -- returns an int
that gives the number of associations in the map.
- map.isEmpty() -- returns a boolean
value that is true if the map is empty, that is if it contains
no associations.
- map.clear() -- removes all
associations from the map, leaving it empty.
The put and get methods are certainly the most commonly
used of the methods in the Map interface. In many applications, these
are the only methods that are needed, and in such cases a map is really no
more difficult to use than a standard array.
Java includes two classes that implement the Map interface:
TreeMap and HashMap. In a TreeMap, the key/value
associations are stored in a sorted tree, in which they are sorted according
to their keys. For this to work, it must be possible to compare
the keys to one another. This means either that the keys must implement
the Comparable interface, or that a Comparator must
be provided for comparing keys. (The Comparator can be provided
as a parameter to the TreeMap constructor.)
A HashMap does not store associations in any particular order,
so there are no restrictions on the keys that can be used in a HashMap.
Most operations are a little faster on HashMaps than they are
on TreeMaps. In general, you should use a HashMap unless
you have some particular need for the ordering property of a TreeMap.
In particular, if you are only using the put and get operations,
you can use a HashMap.
Let's look at an example. In Section 8.4,
I presented a simple PhoneDirectory class that associated phone numbers with
names. That class defined operations addEntry(name,number) and
getNumber(name), where both name and number are
given as Strings. In fact, the phone directory is acting just like
a map, with the addEntry method playing the role of the
put operation and getNumber playing the role of get.
In a real programming application, there would be no need to define a new
class; we could simply use a Map. Using a Map does have
the disadvantage that we are forced to work with Objects instead
of Strings. If that is a problem, it's easy to define a
phone directory class that uses a Map in its implementation:
import java.util.HashMap;
public class PhoneDirectory {
private HashMap info = new HashMap(); // Stores the data for
// the phone directory.
public void addEntry(String name, String number) {
// Record the phone number for a specified name.
info.put(name,number);
}
public String getNumber(String name) {
// Retrieve the phone number for a specified name.
// Returns null if there is no number for the name.
return (String)info.get(name);
}
} // end class PhoneDirectory
In the definition of the getNumber() method, the return
value of info.get(name) is type-cast to type String.
Since the return type of the get() method is Object,
a type-cast is typically necessary before the return value can be used.
By "wrapping" the Map in a PhoneDirectory class,
we hide this unsightly type-cast in the implementation of the class
and provide a more natural interface for the phone directory.
Views, SubSets, and SubMaps
A 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 is a roundabout but clever way.
If map is a variable of type Map, then the
method:
map.keySet()
returns the set of all objects that occur as keys for associations
in the map. That is, the return value is an object that implements
the Set interface. 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 objects that are stored
in the map. This "view" of the map implements the Set 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 for
the key set of a map to traverse the map. For example:
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()) {
Object key = keyIter.next(); // Get the next key.
Object value = map.get(key); // Get the value for that 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.
The Map interface defines two other views. If map
is a variable of type Map, then the method:
map.values()
returns a Collection 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 information in this class 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 element of the entry set is an object belonging
to the class Map.Entry. (This class is defined as a static nested class,
so its full name contains a period. However, it can be used in the same way as
any other class to declare variables and do type-casts.)
A 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. We could use the entry set of a map to print all the keys and values.
This is more efficient than using the key set to print the same information,
as I did in the above example, since we don't have to look up the value
associated with each key:
Set entries = map.entrySet();
Iterator entryIter = entries.iterator();
System.out.println("The map contains the following associations:");
while (entryIter.hasNext()) {
Map.Entry entry = (Map.Entry)entryIter.next();
Object key = entry.getKey(); // Get the key from the entry.
Object value = entry.getValue(); // Get the value.
System.out.println( " (" + key + "," + value + ")" );
}
Maps are not the only place in Java's generic programming
framework where views are used. For example, the List
interface defines a sub-list as
a view of a part of a list. The method:
List subList(int fromIndex, int toIndex)
returns a view of the part of the list consisting of the
list elements in positions between fromIndex
and toIndex (including fromIndex but excluding
toIndex). This view lets you operate on the sublist
using any of the operations defined for lists, but the sublist
is not an independent list. Changes made to the sublist are
actually being made to the original list.
Similarly, it is possible to obtain views that represent certain
subsets of a sorted set. If set is a TreeSet,
then set.subSet(fromElement,toElement) returns a Set
that contains all the elements of set that are between
fromElement and toElement (including fromElement
and excluding toElement). For example, if words is
a TreeSet in which all the elements are Strings of lower case letters,
then words.subSet("m","n") contains all the elements of words
that begin with the letter m. This subset is a view of part of the original
set. That is, creating the subset does not involve copying elements, and
changes made to the subset, such as adding or removing elements, are actually
made to the original set. The view set.headSet(toElement) consists
of all elements from the set which are less than toElement, and
set.tailSet(fromElement) is a view that contains all elements from
the set that are greater than or equal to fromElement.
The TreeMap class defines three submap views. A submap is
similar to a subset. A submap is a Map that contains a subset of the keys
from the original Map, along
with their associated values. If map is a variable of type
TreeMap, then map.subMap(fromKey,toKey) returns a view
that contains all key/value pairs from map whose keys are between fromKey
and toKey (including fromKey and excluding toKey).
There are also views map.headMap(toKey) and map.tailMap(fromKey)
which are defined in the obvious way. Suppose, for example, that blackBook
is a TreeMap in which the keys are names and the values are phone numbers.
We can print out all the entries from blackBook where the name begins
with "M" as follows:
Map ems = blackBook.subMap("M","N");
// This submap contains entries for which the key is greater
// than or equal to "M" and strictly less than "N".
if (ems.isEmpty())
System.out.println("No entries beginning with M.");
else {
Iterator iter = ems.entrySet().iterator();
// This iterator will traverse the entries in the submap, ems.
while (iter.hasNext()) {
// Get the next entry and print its key and value.
Map.Entry entry = iter.next();
System.out.println( entry.getKey() + ": " + entry.getValue() );
}
}
Subsets and submaps are probably best thought of as generalized search
operations that make it possible to find all the items in a range of
values, rather than just to find a single value. Suppose, for example
that a database of scheduled events is stored in a TreeMap
in which the keys are the times of the events, and suppose you want
a listing of all events that are scheduled for some time on July 4, 2002.
Just make a submap containing all keys in the range from
12:00 AM, July 4, 2002 to 12:00 AM, July 5, 2002, and output
all the entries from that submap. This type of search,
which is known as a subrange query
is quite common.
Hash Tables
HashSets and HashMaps are implemented using a data
structure known as a hash table. You don't
need to understand hash tables to use HashSets or HashMaps,
but any computer programmer should be familiar with hash tables and
how they work.
Hash tables are an elegant solution to the search problem. A hash
table, like a HashMap, stores key/value pairs. Given a key,
you have to search the table for the corresponding key/value pair.
When a hash table is used to implement a set, the values are all null,
and the only question is whether or not the key occurs in the set.
You still have to search for the key to check whether it is there
or not.
In most
search algorithms, in order to find the item you are interested in,
you have to look through a bunch of other items that don't interest
you. To find something in an unsorted list, you have to go though
the items one-by-one until you come to the one you are looking for.
In a binary sort tree, you have to start at the root and move down
the tree until you find the item you want. When you search for a
key/value pair in a hash table, you can go directly to the location that
contains the item you want. You don't have to look through
any other items. (This is not quite true, but it's close.)
The location of the key/value pair is computed from the key: You just look at
the key, and then you go directly to the location where it is
stored.
How can this work?
If the keys were integers in the range 0 to 99, we could store the
key/value pairs in an array, A, of 100 elements. The key/value
pair with key N would be stored in A[N]. The key
takes us directly to the location of the key/value pair. The problem
is that there are usually far too many different possible keys for us
to be able to use an array with one location for each possible key.
For example, if the key can be any value of type int,
then we would need an array with over four billion locations -- quite
a waste of space if we are only going to store, say, a few thousand
items! If the key can be a string of any length, then the number
of possible keys is infinite, and using an array with one location
for each possible key is simply impossible.
Nevertheless, hash tables store their data in an array, and the
array index where a key is stored is based on the key. The index is not equal
to the key, but it is computed from the key. The array index for a
key is called the hash code for that
key. A function that computes a hash code, given a key,
is called a hash function. To find
a key in a hash table, you just have to compute the hash code of
the key and go directly to the array location given by that hash code.
If the hash code is 17, look in array location number 17.
Now, since there are fewer array locations than there are possible keys,
it's possible that we might try to store two or more keys in the
same array location. This is called a collision.
A collision is not an error. We can't reject a key just because another
key happened to have the same hash code. A hash table must be able to handle
collisions in some reasonable way. In the type of hash table that
is used in Java, each array location actually holds a linked list of key/value
pairs (possibly an empty list). When two items have the same hash code, they are in the
same linked list. The structure of the hash table looks something
like this:
In this diagram, there is one item with hash code 0, no items with hash
code 1, two items with hash code 2, and so on. In a properly designed
hash table, most of the linked lists are of length zero or one, and
the average length of the lists is less than one. Although the hash code
of a key doesn't necessarily take you directly to that key, there are
probably no more than one or two other items that you have to look through
before finding the key you want. For this to work properly, the
number of items in the hash table should be somewhat less than the
number of locations in the array. In Java's implementation, whenever
the number of items exceeds 75% of the array size, the array is
replaced by a larger one and all the items in the old array are
inserted into the new one.
The Object class defines the method hashCode(), which
returns a value of type int. When an object, obj, is stored
in a hash table that has N locations, a hash code in the range
0 to N-1 is needed. This hash code can be computed
as Math.abs(obj.hashCode()) % N, the remainder when
the absolute value of obj.hashCode() is divided by N.
(The Math.abs is necessary because obj.hashCode() can be
a negative integer, and we need a non-negative number to use as an
array index.)
For hashing to work properly, two objects that are equal according to the
equals() method should have the same hash code. In the Object
class, both equals() and hashCode() are based on the
address of the memory location where the object is stored. However, as noted
in Section 1, many classes redefine the equals()
method. If a class redefines the equals() method, and if objects
of that class will be used as keys in hash tables, then the class should
also redefine the hashCode() method.
For example, in the String class, the equals method
is redefined so that two objects of type String are considered to
be equal if they contain the same sequence of characters.
The hashCode() method is also redefined in the String class,
so that the hash code of a string is computed from the characters in that
string rather than from its location in memory. For Java's standard classes,
you can expect equals() and hashCode() to be correctly
defined. However, you might need to define these methods in classes that
you write yourself.
