 |
 |
|
|
|
|
|
|
 |
| ★ wanayoo — archive 1999 http://developer.java.sun.com/developer/Books/corejava/page5.html | Nouvelle recherche | Portail wanayoo |
|
|
|
 |
 |
 |
 |
 |
 |
 |
 |
|
|
Book Excerpt Index
Core Java 2, Volume IIby Cay S. Horstmann and Gary CornellChapter 2: CollectionsWhenever you add an object to a map, you must supply a key as well. In our case, the key is a string, and the corresponding value is an Employee object. To retrieve an object, you must use (and, therefore, remember) the key. String s = "1411-16-2536"; e = (Employee)staff.get(s); // gets harryIf no information is stored in the map with the particular key specified, then get returns null.
Keys must be unique. You cannot store two values with the same key. If you
call the
The
The collections framework does not consider a map itself as a collection.
(Other frameworks for data structures consider a map as a collection of pairs,
or as a collection of values that is indexed by the keys.) However, you can
obtain views of the map, objects that implement the There are three views: the set of keys, the collection of values (which is not a set), and the set of key/value pairs. The keys and key/value pairs form a set because there can be only one copy of a key in a map. The methods Set keySet() Collection values() Set entrySet()return these three views. (The elements of the entry set are objects of the inner class Map.Entry.)
Note that the For example, you can enumerate all keys of a map:
Set keys = map.keySet();
Iterator iter = keys.iterator();
while (iter.hasNext())
{ Object key = iter.next();
do something with key
}
TIP: If you want to look at both keys and values, then you can avoid value lookups by enumerating the entries. Use the following code skeleton:
Set entries = staff.entrySet();
Iterator iter = entries.iterator();
while (iter.hasNext())
{ Map.Entry entry = (
Map.Entry)iter.next();
Object key = entry.getKey();
Object value = entry.getValue();
do something with key, value
}
If you invoke the remove method of the iterator, you actually remove the key
and its associated value from the map. However, you cannot add an element to
the key set view. It makes no sense to add a key without also adding a value.
If you try to invoke the add method, it throws an UnsupportedOperationException.
The key/value set view has the same restriction, even though it would make
conceptual sense to add a new key/value pair.
NOTE: The legacy Hashtable class (which we cover later in this chapter) has
methods that return enumeration objects--the classical analog to iterators--
that traverse keys and values. However, having collection views is more
powerful since they let you operate on all keys or values at once.
Example 2-4 illustrates a map at work. We first add key/value pairs to a map. Then, we remove one key from the map, which removes its associated value as well. Next, we change the value that is associated with a key and call the get method to look up a value. Finally, we iterate through the entry set. Example 2-4: MapTest.java
import java.util.*;
public class MapTest
{ public static void main(
String[] args)
{ Map staff = new HashMap();
staff.put("144-25-5464",
new Employee("Angela Hung"));
staff.put("567-24-2546",
new Employee("Harry Hacker"));
staff.put("157-62-7935",
new Employee("Gary Cooper"));
staff.put("456-62-5527",
new Employee("Francesca Cruz"));
// print all entries
System.out.println(staff);
// remove an entry
staff.remove("567-24-2546");
// replace an entry
staff.put("456-62-5527",
new Employee("Francesca Miller"));
// look up a value
System.out.println(
staff.get("157-62-7935"));
// iterate through all entries
Set entries = staff.entrySet();
Iterator iter = entries.iterator();
while (iter.hasNext())
{ Map.Entry entry =
(Map.Entry)iter.next();
Object key = entry.getKey();
Object value = entry.getValue();
System.out.println(
"key=" + key + ", value=" +
value);
}
}
}
class Employee
{ public Employee(String n)
{ name = n;
salary = 0;
}
public String toString()
{ return "[name=" + name + ",
salary=" + salary + "]";
}
public void setSalary(double s)
{ salary = s;
}
private String name;
private double salary;
}
Weak Hash Maps
The
Unfortunately, it isn't quite so simple. The garbage collector traces live
objects. As long as the map object is live, then all buckets in it are live
and they won't be reclaimed. Thus, your program should take care to remove
unused values from long-lived maps. Or, you can use a
Here are the inner workings of this mechanism. The java.util.Map
The Collections FrameworkA framework is a set of classes that form the basis for building advanced functionality. A framework contains superclasses with useful functionality, policies, and mechanisms. The user of a framework forms sublasses to extend the functionality without having to reinvent the basic mechanisms. For example, Swing is a framework for user interfaces.
The Java collections library forms a framework for
There are two fundamental interfaces for containers: boolean add(Object element)However, maps hold key/value pairs, and you use the put method to insert them.
boolean put(Object key, Object value)To read elements from a collection, you visit them with an iterator. However, you can read values from a map with the get method:
Object get(Object key)A List is an ordered collection. Elements are added into a particular
position in the container. An object can be placed into its position in two
ways: by an integer index and by a list iterator. The List interface defines
methods for random access:
void add(int index, Object element) Object get(int index) void remove(int index)The ListIterator interface defines a method for adding an element
before the
iterator position:
void add(Object element)To get and remove elements at a particular position, you simply use the next and remove methods of the Iterator interface.
NOTE: From a theoretical point of view, it would have made sense to have a separate Array interface that extends the List interface and declares the
random access methods. If there was a separate Array interface, then those
algorithms that require random access would use Array parameters and you could
not accidentally apply them to collections with slow random access. However,
the designers of the collections framework chose not to define a separate
interface. They wanted to keep the number of interfaces in the library small.
Also, they did not want to take a paternalistic attitude toward programmers.
You are free to pass a linked list to algorithms that use random access--you
just need to be aware of the performance costs.
The
NOTE: For sets and lists, there is a well-defined notion of equality. Two sets are equal if they contain the same elements in some order. Two lists are equal if they contain the same elements in the same order. However, there is no well-defined notion of equality for collections. You should therefore not use the equals method on Collection references.
Why make a separate interface if the method signatures are the same?
Conceptually, not all collections are sets. Making a
Finally, the Now, let us turn from the interfaces to the classes that implement them. We already discussed that the collection interfaces have quite a few methods that can be trivially implemented from more fundamental methods. There are five abstract classes that supply many of these routine implementations: AbstractCollection AbstractList AbstractSequentialList AbstractSet AbstractMapIf you implement your own collection class, then you probably want to extend
one of these classes so that you can pick up the implementations of the
routine operations.
The Java library supplies six concrete classes: LinkedList ArrayList HashSet TreeSet HashMap TreeMapFigure 2-10 shows the relationships between these classes.
Finally, there are a number of legacy container classes that have been present since the beginning, before there was a collections framework: Vector Stack Hashtable PropertiesThey have been integrated into the collections framework--see Figure 2-11. We discuss these classes later in this chapter.
Views and Wrappers
If you look at Figure 2-9 and Figure 2-10, you might think it is overkill
to have six interfaces and five abstract classes to implement six concrete
collection classes. However, these figures don't tell the whole story. By
using views, you can obtain other objects that implement the
The technique of views has a number of useful applications in the collections
framework. Here is the most compelling one. Recall that the methods of the
HashMap hashMap = new HashMap(); map = Collections.synchronizedMap(hashMap);Now, you can access the map object from multiple threads. The methods such as
get and put are synchronized--each method call must be finished completely
before another thread can call another method.
There are six methods to obtain synchronized collections: Collections.synchronizedCollection Collections.synchronizedList Collections.synchronizedSet Collections.synchronizedSortedSet Collections.synchronizedMap Collections.synchronizedSortedMapThe views that are returned by these methods are sometimes called wrappers. You should make sure that no thread accesses the data structure through the original unsynchronized methods. The easiest way to ensure this is not to save any reference to the original object, but to simply pass the constructed collection to the wrapper method:
map = Collections.synchronizedMap(
new HashMap());
There is one caveat when accessing a collection from multiple threads.
Recall that you can either have multiple iterators that read from a
collection or have a single thread that modifies the collection. For
that reason, you will want to make sure that any iteration--
Iterator iter = collection.iterator(); while (iter.hasNext()) do something with iter.next();--does not occur at a time when another thread modifies the collection. If it did, then the next method would throw a ConcurrentModificationException.
One way to ensure exclusive access is to place the iteration inside a block
that locks the container:
synchronized (container)
{ Iterator iter =
collection.iterator();
while (iter.hasNext())
do something with iter.next();
}
Since the wrappers wrap the interface and not the actual collection object,
you only have access to those methods that are defined in the interface. For
example, the LinkedList class has convenience methods, addFirst and addLast,
that are not part of the List interface. These methods are not accessible
through the synchronization wrapper.
CAUTION: The synchronizedCollection method (as well as the
unmodifiableCollection method discussed later in this section) returns a
collection whose equals method does not invoke the equals method of the
underlying collection. Instead, it inherits the equals method of the Object
class, which just tests whether the objects are identical. If you turn a
set or list into just a collection, you can no longer test for equal contents.
The wrapper acts in this way because equality testing is not well defined
at this level of the hierarchy.
However, the
The wrappers treat the
The For example, suppose you want to let some part of your code look at, but not touch, the contents of a collection. Here is what you could do.
List staff = new LinkedList();
. . .
lookAt(
new Collections.unmodifiableList(
staff));
The Collections.unmodifiableList method returns an object of a class
implementing the List interface. Its accessor methods retrieve values from
the staff collection. Of course, the lookAt method can call all methods of
the List interface, not just the accessors. But all mutator methods (such as
add) have been redefined to throw an UnsupportedOperationException instead of
forwarding the call to the underlying collection. There are similar methods to
obtain unmodifiable wrappers to the other collection interfaces.
NOTE: In the API documentation, certain methods of the collection interfaces, such as add, are described as optional operations. This is curious--isn't the purpose of an interface to lay out the methods that a class must implement? Indeed, it would have made sense to separate the read-only interfaces from the interfaces that allow full access. But that would have doubled the number of interfaces, which the designers of the library found unacceptable.
The
Card[] cardDeck = new Card[52];
. . .
List cardList =
Arrays.asList(cardDeck);
The returned object is not an ArrayList. It is a view object whose get and
set methods access the underlying array. All methods that would change the
size of the array (such as add and the remove method of the associated
iterator) throw an UnsupportedOperationException.
Subranges You can form subrange views for a number of collections. For example, suppose you have a list staff and want to extract elements 10 to 19. You use the subList method to obtain a view into the subrange of the list. List group2 = staff.subList(10, 20);The first index is inclusive, the second exclusive--just like the parameters for the substring operation of theStringclass.
You can apply any operations to the subrange, and they automatically reflect the entire list. For example, you can erase the entire subrange: group2.clear(); // staff reductionThe elements are now automatically cleared from the staff list.
For sorted sets and maps, you use the sort order, not the element position,
to form subranges. The subSet(from, to) headSet(to) tailSet(from)These return the subsets of all elements that are larger than or equal to from and strictly smaller than to. For sorted maps, there are similar methods
subMap(from, to) headMap(to) tailMap(from)that return views into the maps consisting of all entries where the keys fall into the specified ranges. Lightweight collection wrappers The method call Collections.nCopies(n, anObject)returns an immutable object that implements the List interface and gives the illusion of having nelements, each of which appears as anObject. There
is very little storage cost--the object is only stored once. This is a cute
application of the wrapper technique. You can use such a list to initialize
a concrete container. For example, the following call creates an ArrayList
containing 100 strings, all set to "DEFAULT":
ArrayList settings
= new ArrayList(
Collections.nCopies(
100, "DEFAULT"));
The method call
Collections.singleton(anObject)
returns a wrapper object that implements the Set interface (unlike
ncopies
which produces a List). The returned object implements an immutable
single-element set without the overhead of a hash table or tree. The constants
Collections.EMPTY_LIST and Collections.EMPTY_SET return objects that implement
the List and Set interfaces and contain no elements. The advantage is similar
to that of the singleton method: the returned objects do not have the overhead
of a data structure. Singletons and empty objects are potentially useful as
parameters to methods that expect a list, set, or container.
NOTE: JDK 1.3 adds methods singletonList and
singletonMap and a constant
EMPTY_MAP.A final note on optional operations We'd like to end this section with a few words about the "optional" or unsupported operations in the collection and iterator interfaces. This is undoubtedly the most controversial design decision in the collections framework. The problem is caused by the undeniably powerful and convenient views. Views are good because they lead to efficient code, and their "plug and play" nature means you only need to learn a few basic concepts. A view usually has some restriction--it may be read-only, it may not be able to change the size, or it may support removal, but not insertion, as is the case for the key view of a map. The restriction is different for each view. Making a separate interface for each restricted view would lead to a bewildering tangle of interfaces that would be unusable in practice.
Should you extend the technique of optional methods to your own interfaces?
We think not. Even though collections are used very frequently, the coding
style for implementing them is not typical for other problem domains. The
designers of a java.util.Collections
java.util.Arrays static List asList(Object[] array)returns a list view of the elements in an array that is modifiable but not resizable. Parameters: array the array to wrap
java.util.List
SortedMap subMap(Object from, Object to)
SortedMap headMap(Object to)
SortedMap tailMap(Object from)return a map view of the entries whose keys are within a range. Parameters: from the first key to include in the view
to the first key to exclude in the view
|
