A map is an object that stores associations between keys and values, or key/value pairs. Given a key, you can find its value. Both keys and values are objects. The keys must be unique, but the values may be duplicated. Some maps can accept a null key and null values, others cannot.
The Map Interfaces
Because the map interfaces define the character and nature of maps, this discussion of maps begins with them. The following interfaces support maps:
Map: Maps unique keys to values.
Map.Entry: Describes an element (a key/value pair) in a map. This is an inner class of Map.
SortedMap: Extends Map so that the keys are maintained in ascending order.
Each interface is examined next, in turn.
The Map Interface
The Map interface maps unique keys to values. A key is an object that you use to retrieve a value at a later date. Given a key and a value, you can store the value in a Map object. After the value is stored, you can retrieve it by using its key. Several methods throw a NoSuchElementException when no items exist in the invoking map. A ClassCastException is thrown when an object is incompatible with the elements in a map. A NullPointerException is thrown if an attempt is made to use a null object and null is not allowed in the map. An UnsupportedOperationException is thrown when an attempt is made to change an unmodifiable map.
The Methods Defined by Map
void clear( ): Removes all key/value pairs from the invoking map.
boolean containsKey(Object k): Returns true if the invoking map contains k as a key. Otherwise, returns false.
boolean containsValue(Object v): Returns true if the map contains v as a value. Otherwise, returns false.
Set entrySet( ): Returns a Set that contains the entries in the map. The set contains objects of type Map.Entry. This method provides a set-view of the invoking map.
boolean equals(Object obj): Returns true if obj is a Map and contains the same entries. Otherwise, returns false.
Object get(Object k): Returns the value associated with the key k.
int hashCode( ): Returns the hash code for the invoking map.
boolean isEmpty( ): Returns true if the invoking map is empty. Otherwise, returns false.
Set keySet( ): Returns a Set that contains the keys in the invoking map. This method provides a set-view of the keys in the invoking map.
Object put(Object k, Object v): Puts an entry in the invoking map, overwriting any previous value associated with the key. The key and value are k and v, respectively. Returns null if the key did not already exist. Otherwise, the previous value linked to the key is returned.
void putAll(Map m): Puts all the entries from m into this map.
Object remove(Object k): Removes the entry whose key equals k.
int size( ): Returns the number of key/value pairs in the map.
Collection values( ): Returns a collection containing the values in the map. This method provides a collection-view of the values in the map.
Maps revolve around two basic operations: get( ) and put( ). To put a value into a map, use put( ), specifying the key and the value. To obtain a value, call get( ), passing the key as an argument. The value is returned.
As mentioned earlier, maps are not collections because they do not implement the Collection interface, but you can obtain a collection-view of a map. To do this, you can use the entrySet( ) method. It returns a Set that contains the elements in the map. To obtain a collection-view of the keys, use keySet( ). To get a collection-view of the values, use values( ). Collection-views are the means by which maps are integrated into the collections framework.
The SortedMap Interface
The SortedMap interface extends Map. It ensures that the entries are maintained in ascending key order. Several methods throw a NoSuchElementException when no items are in the invoking map. A ClassCastException is thrown when an object is incompatible with the elements in a map. A NullPointerException is thrown if an attempt is made to use a null object when null is not allowed in the map.
Sorted maps allow very efficient manipulations of submaps (in other words, a subset of a map). To obtain a submap, use headMap( ), tailMap( ), or subMap( ). To get the first key in the set, call firstKey( ). To get the last key, use lastKey( ).
The Methods Defined by SortedMap
Comparator comparator( ): Returns the invoking sorted map’s comparator. If the natural ordering is used for the invoking map, null is returned.
Object firstKey( ): Returns the first key in the invoking map.
SortedMap headMap(Object end): Returns a sorted map for those map entries with keys that are less than end.
Object lastKey( ): Returns the last key in the invoking map.
SortedMap subMap(Object start, Object end): Returns a map containing those entries with keys that are greater than or equal to start and less than end.
SortedMap tailMap(Object start): Returns a map containing those entries with keys that are greater
than or equal to start.
The Map.Entry Interface
The Map.Entry interface enables you to work with a map entry. Recall that the entrySet( ) method declared by the Map interface returns a Set containing the map entries. Each of these set elements is a Map.Entry object. Table 15-8 summarizes the methods declared by this interface.
The Map Classes
Several classes provide implementations of the map interfaces. The classes that can be used for maps are summarized here:
AbstractMap: Implements most of the Map interface.
HashMap: Extends AbstractMap to use a hash table.
TreeMap: Extends AbstractMap to use a tree.
WeakHashMap: Extends AbstractMap to use a hash table with weak keys.
LinkedHashMap: Extends HashMap to allow insertion-order iterations.
IdentityHashMap: Extends AbstractMap and uses reference equality when comparing documents.
The Methods Defined by Map.Entry
boolean equals(Object obj): Returns true if obj is a Map.Entry whose key and value are equal to that of the invoking object.
Object getKey( ): Returns the key for this map entry.
Object getValue( ): Returns the value for this map entry.
int hashCode( ): Returns the hash code for this map entry.
Object setValue(Object v): Sets the value for this map entry to v. A ClassCastException is thrown if v is not the correct type for the map. An IllegalArgumentException is thrown if there is a problem with v. A NullPointerException is thrown if v is null and the map does not permit null keys. An UnsupportedOperationException is thrown if the map cannot be changed.
Notice that AbstractMap is a superclass for all concrete map implementations. WeakHashMap implements a map that uses “weak keys,” which allows an element in a map to be garbage-collected when its key is unused. This class is not discussed further here. The others are described next.
The HashMap Class
The HashMap class uses a hash table to implement the Map interface. This allows the execution time of basic operations, such as get( ) and put( ), to remain constant even for large sets.
The following constructors are defined:
HashMap( )
HashMap(Map m)
HashMap(int capacity)
HashMap(int capacity, float fillRatio)
The first form constructs a default hash map. The second form initializes the hash map by using the elements of m. The third form initializes the capacity of the hash map to capacity. The fourth form initializes both the capacity and fill ratio of the hash map by using its arguments. The meaning of capacity and fill ratio is the same as for HashSet, described earlier.
HashMap implements Map and extends AbstractMap. It does not add any methods of its own. You should note that a hash map does not guarantee the order of its elements. Therefore, the order in which elements are added to a hash map is not necessarily the order in which they are read by an iterator.
The following program illustrates HashMap. It maps names to account balances. Notice how a set-view is obtained and used.
import java.util.*;
class HashMapDemo {
public static void main(String args[]) {
// Create a hash map
HashMap hm = new HashMap();
// Put elements to the map
hm.put("John Doe", new Double(3434.34));
hm.put("Tom Smith", new Double(123.22));
hm.put("Jane Baker", new Double(1378.00));
hm.put("Todd Hall", new Double(99.22));
hm.put("Ralph Smith", new Double(-19.08));
// Get a set of the entries
Set set = hm.entrySet();
// Get an iterator
Iterator i = set.iterator();
// Display elements
while(i.hasNext()) {
Map.Entry me = (Map.Entry)i.next();
System.out.print(me.getKey() + ": ");
System.out.println(me.getValue());
}
System.out.println();
// Deposit 1000 into John Doe's account
double balance = ((Double)hm.get("John Doe")).doubleValue();
hm.put("John Doe", new Double(balance + 1000));
System.out.println("John Doe's new balance: " +
hm.get("John Doe"));
}
}
Output from this program is shown here (the precise order may vary).
Todd Hall: 99.22
Ralph Smith: -19.08
John Doe: 3434.34
Jane Baker: 1378.0
Tom Smith: 123.22
John Doe’s current balance: 4434.34
The program begins by creating a hash map and then adds the mapping of names to balances. Next, the contents of the map are displayed by using a set-view, obtained by calling entrySet( ). The keys and values are displayed by calling the getKey( ) and getValue( ) methods that are defined by Map.Entry. Pay close attention to how the deposit is made into John Doe’s account. The put( ) method automatically replaces any preexisting value that is associated with the specified key with the new value. Thus, after John Doe’s account is updated, the hash map will still contain just one “John Doe” account.
The TreeMap Class
The TreeMap class implements the Map interface by using a tree. A TreeMap provides an efficient means of storing key/value pairs in sorted order, and allows rapid retrieval. You should note that, unlike a hash map, a tree map guarantees that its elements will be sorted in ascending key order.
The following TreeMap constructors are defined:
TreeMap( )
TreeMap(Comparator comp)
TreeMap(Map m)
TreeMap(SortedMap sm)
The first form constructs an empty tree map that will be sorted by using the natural order of its keys. The second form constructs an empty tree-based map that will be sorted by using the Comparator comp. (Comparators are discussed later in this chapter.) The third form initializes a tree map with the entries from m, which will be sorted by using the natural order of the keys. The fourth form initializes a tree map with the entries from sm, which will be sorted in the same order as sm.
TreeMap implements SortedMap and extends AbstractMap. It does not define any additional methods of its own.
The following program reworks the preceding example so that it uses TreeMap:
import java.util.*;
class TreeMapDemo {
public static void main(String args[]) {
// Create a tree map
TreeMap tm = new TreeMap();
// Put elements to the map
tm.put("John Doe", new Double(3434.34));
tm.put("Tom Smith", new Double(123.22));
tm.put("Jane Baker", new Double(1378.00));
tm.put("Todd Hall", new Double(99.22));
tm.put("Ralph Smith", new Double(-19.08));
// Get a set of the entries
Set set = tm.entrySet();
// Get an iterator
Iterator i = set.iterator();
// Display elements
while(i.hasNext()) {
Map.Entry me = (Map.Entry)i.next();
System.out.print(me.getKey() + ": ");
System.out.println(me.getValue());
}
System.out.println();
// Deposit 1000 into John Doe's account
double balance = ((Double)tm.get("John Doe")).doubleValue();
tm.put("John Doe", new Double(balance + 1000));
System.out.println("John Doe's new balance: " +
tm.get("John Doe"));
}
}
The following is the output from this program:
Jane Baker: 1378.0
John Doe: 3434.34
Ralph Smith: -19.08
Todd Hall: 99.22
Tom Smith: 123.22
John Doe’s current balance: 4434.34
Notice that TreeMap sorts the keys. However, in this case, they are sorted by first name instead of last name. You can alter this behavior by specifying a comparator when the map is created, as described shortly.
The LinkedHashMap Class
Java 2, version 1.4 adds the LinkedHashMap class. This class extends HashMap.
LinkedHashMap maintains a linked list of the entries in the map, in the order in which
they were inserted. This allows insertion-order iteration over the map. That is, when
iterating a LinkedHashMap, the elements will be returned in the order in which they
were inserted. You can also create a LinkedHashMap that returns its elements in the
order in which they were last accessed.
LinkedHashMap defines the following constructors.
LinkedHashMap( )
LinkedHashMap(Map m)
LinkedHashMap(int capacity)
LinkedHashMap(int capacity, float fillRatio)
LinkedHashMap(int capacity, float fillRatio, boolean Order)
The first form constructs a default LinkedHashMap. The second form initializes the LinkedHashMap with the elements from m. The third form initializes the capacity. The fourth form initializes both capacity and fill ratio. The meaning of capacity and fill ratio are the same as for HashMap. The last form allows you to specify whether the elements will be stored in the linked list by insertion order, or by order of last access. If Order is true, then access order is used. If Order is false, then insertion order is used. LinkedHashMap adds only one method to those defined by HashMap. This method is removeEldestEntry( ) and it is shown here.
protected boolean removeEldestEntry(Map.Entry e)
This method is called by put( ) and putAll( ). The oldest entry is passed in e. By default, this method returns false and does nothing. However, if you override this method, then you can have the LinkedHashMap remove the oldest entry in the map. To do this, have your override return true. To keep the oldest entry, return false.
The IdentityHashMap Class
Java 2, version 1.4 adds the IdentityHashMap class. This class implements AbstractMap. It is similar to HashMap except that it uses reference equality when comparing elements. The Java 2 documentation explicitly states that IdentityHashMap is not for general use.
No comments:
Post a Comment