> ### 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.

[ Next Section | Previous Section | Chapter Index | Main Index ]