|
|
5.6. CollectionsThe Java Collections Framework is a set of important utility classes and interfaces in the java.util package for working with collections of objects. The Collections Framework defines two fundamental types of collections. A Collection is a group of objects while a Map is a set of mappings, or associations, between objects. A Set is a type of Collection with no duplicates, and a List is a Collection in which the elements are ordered. SortedSet and SortedMap are specialized sets and maps that maintain their elements in a sorted order. Collection , Set, List, Map, SortedSet, and SortedMap are all interfaces, but the java.util package also defines various concrete implementations, such as lists based on arrays and linked lists, and maps and sets based on hashtables or binary trees. Other important interfaces are Iterator and ListIterator, which allow you to loop through the objects in a collection. The Collections Framework was added in Java 1.2, but prior to that release you can use Vector and Hashtable, which are approximately the same as ArrayList and HashMap. In Java 1.4, the Collections API added the RandomAccess marker interface, which is implemented by List implementations that support efficient random access (i.e., it is implemented by ArrayList and Vector but not by LinkedList). Java 1.4 also introduced LinkedHashMap and LinkedHashSet, which are hashtable-based maps and sets that preserve the insertion order of elements. Finally, IdentityHashMap is a hashtable-based Map implementation that uses the == operator to compare key objects rather than using the equals() method to compare them. The Collections Framework has been overhauled in Java 5.0 to use generics (see Chapter 4). Java 5.0 also adds EnumSet and EnumMap classes that are specialized for working with enumerated values (see Chapter 4) and the java.lang.Iterable interface used by the new for/in looping statement. Finally, Java 5.0 adds the Queue interface. Most of the interesting Queue implementations are BlockingQueue implementations in java.util.concurrent . 5.6.1. The Collection InterfaceCollection<E> is a parameterized interface that represents a generic group of objects of type E. The group may or may not allow duplicate elements and may or may not impose an ordering on the elements. Methods are defined for adding and removing objects from the group, testing an object for membership in the group, and iterating through all elements in the group. Additional methods return the elements of the group as an array and return the size of the collection. The Java Collections Framework does not provide any implementations of Collection, but this interface is still very important because it defines the features common to all Set , List, and Queue implementations. The following code illustrates the operations you can perform on Collection objects: // Create some collections to work with.
Collection<String> c = new HashSet<String>(); // An empty set
// We'll see these utility methods later
Collection<String> d = Arrays.asList("one", "two"); // immutable
Collection<String> e = Collections.singleton("three"); // immutable
// Add elements to a collection. These methods return true if the collection
// changes, which is useful with Sets that don't allow duplicates.
c.add("zero"); // Add a single element
c.addAll(d); // Add a collection of elements
// Copy a collection: most implementations have a copy constructor
Collection<String> copy = new ArrayList<String>(c);
// Remove elements from a collection.
// All but clear() return true if the collection changes.
c.remove("zero"); // Remove a single element
c.removeAll(e); // Remove a collection of elements
c.retainAll(d); // Remove all elements that are not in e
c.clear(); // Remove all elements from the collection
// Querying collection size
boolean b = c.isEmpty(); // Collection is now empty
int s = c.size(); // Collection size is now 0.
// Restore collection from the copy we made
c.addAll(copy);
// Test membership in the collection. Membership is based on the equals()
// method, not the == operator.
b = c.contains("zero"); // true
b = c.containsAll(d); // true
// Iterate through collection elements with a while loop.
// Some implementations (such as lists) guarantee an order of iteration
// Others make no guarantees.
Iterator<String> iterator = c.iterator();
while(iterator.hasNext()) System.out.println(iterator.next());
// Iteration with a for loop
for(Iterator<String> i = c.iterator(); i.hasNext(); )
System.out.println(i.next());
// Java 5.0 iteration using a for/in loop
for(String word : c) System.out.println(word);
// Most Collection implementations have a useful toString() method
System.out.println(c); // As an alternative to the iterations above
// Obtain an array of collection elements. If the iterator guarantees
// an order, this array has the same order. The array is a copy, not a
// reference to an internal data structure.
Object[] elements = c.toArray();
// If we want the elements in a String[], we must pass one in
String[] strings = c.toArray(new String[c.size()]);
// Or we can pass an empty String[] just to specify the type and
// the toArray() method will allocate an array for us
strings = c.toArray(new String[0]);Remember that you can use any of the methods shown above with any Set, List, or Queue. These subinterfaces may impose membership restrictions or ordering constraints on the elements of the collection but still provide the same basic methods. Methods such as add( ) , remove(), clear( ), and retainAll() that alter the collection are optional, and read-only implementations may throw UnsupportedOperationException. Collection, Map, and their subinterfaces do not extend the Cloneable or Serializable interfaces. All of the collection and map implementation classes provided in the Java Collections Framework, however, do implement these interfaces. Some collection implementations place restrictions on the elements that they can contain. An implementation might prohibit null as an element, for example. And EnumSet restricts membership to the values of a specified enumerated type. Attempting to add a prohibited element to a collection always throws an unchecked exception such as NullPointerException or ClassCastException. Checking whether a collection contains a prohibited element may also throw such an exception, or it may simply return false. 5.6.2. The Set InterfaceA set is a collection of objects that does not allow duplicates: it may not contain two references to the same object, two references to null, or references to two objects a and b such that a.equals(b). Most general-purpose Set implementations impose no ordering on the elements of the set, but ordered sets are not prohibited (see SortedSet and LinkedHashSet). Sets are further distinguished from ordered collections like lists by the general expectation that they have an efficient contains( ) method that runs in constant or logarithmic time. Set defines no additional methods beyond those defined by Collection but places additional restrictions on those methods. The add( ) and addAll() methods of a Set are required to enforce the no-duplicates rules: they may not add an element to the Set if the set already contains that element. Recall that the add() and addAll( ) methods defined by the Collection interface return true if the call resulted in a change to the collection and false if it did not. This return value is relevant for Set objects because the no-duplicates restriction means that adding an element does not always result in a change to the set. Table 5-2 lists the implementations of the Set interface and summarizes their internal representation, ordering characteristics, member restrictions, and the performance of the basic add( ), remove( ), and contains() operations as well as iteration performance. You can read more about each class in the reference section. Note that CopyOnWriteArraySet is in the java.util.concurrent package; all the other implementations are part of java.util. Also note that java.util.BitSet is not a Set implementation. This legacy class is useful as a compact and efficient list of boolean values but is not part of the Java Collections Framework.
The treeSet implementation uses a red-black tree data structure to maintain a set that is iterated in ascending order according to the natural ordering of Comparable objects or according to an ordering specified by a Comparator object. TReeSet actually implements the SortedSet interface, which is a subinterface of Set. SortedSet offers several interesting methods that take advantage of its sorted nature. The following code illustrates: public static void testSortedSet(String[] args) {
// Create a SortedSet
SortedSet<String> s = new TreeSet<String>(Arrays.asList(args));
// Iterate set: elements are automatically sorted
for(String word : s) System.out.println(word);
// Special elements
String first = s.first(); // First element
String last = s.last(); // Last element
// Subrange views of the set
SortedSet<String> tail = s.tailSet(first+'\0'); // all elements but first
SortedSet<String> head = s.headSet(last); // all elements but last
SortedSet<String> middle = s.subSet(first+'\0', // all but ends
last);
}5.6.3. The List InterfaceA List is an ordered collection of objects. Each element of a list has a position in the list, and the List interface defines methods to query or set the element at a particular position, or index. In this respect a List is like an array whose size changes as needed to accommodate the number of elements it contains. Unlike sets, lists allow duplicate elements. In addition to its index-based get( ) and set() methods, the List interface defines methods to add or remove an element at a particular index and also defines methods to return the index of the first or last occurrence of a particular value in the list. The add( ) and remove() methods inherited from Collection are defined to append to the list and to remove the first occurrence of the specified value from the list. The inherited addAll() appends all elements in the specified collection to the end of the list, and another version inserts the elements at a specified index. The retainAll() and removeAll( ) methods behave as they do for any Collection, retaining or removing multiple occurrences of the same value, if needed. The List interface does not define methods that operate on a range of list indexes. Instead it defines a single subList method that returns a List object that represents just the specified range of the original list. The sublist is backed by the parent list, and any changes made to the sublist are immediately visible in the parent list. Examples of subList( ) and the other basic List manipulation methods are below. // Create lists to work with
List<String> l = new ArrayList<String>(Arrays.asList(args));
List<String> words = Arrays.asList("hello", "world");
// Querying and setting elements by index
String first = l.get(0); // First element of list
String last = l.get(l.size()-1); // Last element of list
l.set(0, last); // The last shall be first
// Adding and inserting elements. add() can append or insert
l.add(first); // Append the first word at end of list
l.add(0, first); // Insert first word at the start of the list again
l.addAll(words); // Append a collection at the end of the list
l.addAll(1, words); // Insert collection after first word
// Sublists: backed by the original list
List<String> sub = l.subList(1,3); // second and third elements
sub.set(0, "hi"); // modifies 2nd element of l
// Sublists can restrict operations to a subrange of backing list
String s = Collections.min(l.subList(0,4));
Collections.sort(l.subList(0,4));
// Independent copies of a sublist don't affect the parent list.
List<String> subcopy = new ArrayList<String>(l.subList(1,3));
// Searching lists
int p = l.indexOf(last); // Where does the last word appear?
p = l.lastIndexOf(last); // Search backward
// Print the index of all occurrences of last in l. Note subList()
int n = l.size();
p = 0;
do {
// Get a view of the list that includes only the elements we
// haven't searched yet.
List<String> list = l.subList(p, n);
int q = list.indexOf(last);
if (q == -1) break;
System.out.printf("Found '%s' at index %d%n", last, p+q);
p += q+1;
} while(p < n);
// Removing elements from a list
l.remove(last); // Remove first occurrence of the element
l.remove(0); // Remove element at specified index
l.subList(0,2).clear(); // Remove a range of elements using subList()
l.retainAll(words); // Remove all but elements in words
l.removeAll(words); // Remove all occurrences of elements in words
l.clear(); // Remove everythingA general expectation of List implementations is that they can be efficiently iterated, typically in time proportional to the size of the list. Lists do not all provide efficient random-access to the elements at any index, however. Sequential-access lists, such as the LinkedList class, provide efficient insertion and deletion operations at the expense of random access performance. In Java 1.4 and later, implementations that provide efficient random access implement the RandomAccess marker interface, and you can test for this interface with instanceof if you need to ensure efficient list manipulations: List<?> l = ...; // Arbitrary list we're passed to manipulate // Ensure we can do efficient random access. If not, use a copy constructor // to make a random-access copy of the list before manipulating it. if (!(l instanceof RandomAccess)) l = new ArrayList<?>(l); The Iterator returned by the iterator() method of a List iterates the list elements in the order that they occur in the list. List implements Iterable, and lists can be iterated with a for/in loop just as any other collection can. To iterate just a portion of a list, you can use the subList( ) method to create a sublist view: List<String> words = ...; // Get a list to iterate
// Iterate just all elements of the list but the first
for(String word : words.subList(1, words.size()))
System.out.println(word);In addition to normal iteration, lists also provide enhanced bidirectional iteration using a ListIterator object returned by the listIterator() method. To iterate backward through a List, for example, start with a ListIterator with its cursor positioned after the end of the list: ListIterator<String> li = words.listIterator(words.size());
while(li.hasPrevious()) {
System.out.println(li.previous());
}Table 5-3 summarizes the five general-purpose List implementations in the Java platform. Vector and Stack are legacy implementations left over from Java 1.0. CopyOnWriteArrayList is a new in Java 5.0 and is part of the java.util.concurrent package.
5.6.4. The Map InterfaceA map is a set of key objects and a mapping from each member of that set to a value object. The Map interface defines an API for defining and querying mappings. Map is part of the Java Collections Framework, but it does not extend the Collection interface, so a Map is a little-c collection, not a big-C Collection. Map is a parameterized type with two type variables. Type variable K represents the type of keys held by the map, and type variable V represents the type of the values that the keys are mapped to. A mapping from String keys to Integer values, for example, can be represented with a Map<String,Integer>. The most important Map methods are put(), which defines a key/value pair in the map, get( ), which queries the value associated with a specified key, and remove( ), which removes the specified key and its associated value from the map. The general performance expectation for Map implementations is that these three basic methods are quite efficient: they should usually run in constant time and certainly no worse than in logarithmic time. An important feature of Map is its support for "collection views." Although a Map is not a Collection, its keys can be viewed as a Set, its values can be viewed as a Collection, and its mappings can be viewed as a Set of Map.Entry objects. (Map.Entry is a nested interface defined within Map: it simply represents a single key/value pair.) The sample code below shows the get( ), put(), remove( ), and other methods of a Map and also demonstrates some common uses of the collection views of a Map: // Create maps to work with
Map<String,Integer> m = new HashMap<String,Integer>(); // New, empty map
// Immutable Map containing a single key-value pair
Map<String,Integer> singleton = Collections.singletonMap("testing", -1);
// Note this rarely-used syntax to explicitly specify the parameter
// types of the generic emptyMap() method. The returned map is immutable
Map<String,Integer> empty = Collections.<String,Integer>emptyMap();
// Populate the map using the put() method to define mappings from array
// elements to the index at which each element appears
String[] words = { "this", "is", "a", "test" };
for(int i = 0; i < words.length; i++)
m.put(words[i], i); // Note autoboxing of int to Integer
// Each key must map to a single value. But keys may map to the same value
for(int i = 0; i < words.length; i++)
m.put(words[i].toUpperCase(), i);
// The putAll() method copies mappings from another Map
m.putAll(singleton);
// Query the mappings with the get() method
for(int i = 0; i < words.length; i++)
if (m.get(words[i]) != i) throw new AssertionError();
// Key and value membership testing
m.containsKey(words[0]); // true
m.containsValue(words.length); // false
// Map keys, values, and entries can be viewed as collections
Set<String> keys = m.keySet();
Collection<Integer> values = m.values();
Set<Map.Entry<String,Integer>> entries = m.entrySet();
// The Map and its collection views typically have useful toString() methods
System.out.printf("Map: %s%nKeys: %s%nValues: %s%nEntries: %s%n",
m, keys, values, entries);
// These collections can be iterated.
// Most maps have an undefined iteration order (but see SortedMap)
for(String key : m.keySet()) System.out.println(key);
for(Integer value: m.values()) System.out.println(value);
// The Map.Entry<K,V> type represents a single key/value pair in a map
for(Map.Entry<String,Integer> pair : m.entrySet()) {
// Print out mappings
System.out.printf("'%s' ==> %d%n", pair.getKey(), pair.getValue());
// And increment the value of each Entry
pair.setValue(pair.getValue() + 1);
}
// Removing mappings
m.put("testing", null); // Mapping to null can "erase" a mapping:
m.get("testing"); // Returns null
m.containsKey("testing"); // Returns true: mapping still exists
m.remove("testing"); // Deletes the mapping altogether
m.get("testing"); // Still returns null
m.containsKey("testing"); // Now returns false.
// Deletions may also be made via the collection views of a map.
// Additions to the map may not be made this way, however.
m.keySet().remove(words[0]); // Same as m.remove(words[0]);
m.values().remove(2); // Remove one mapping to the value 2
m.values().removeAll(Collections.singleton(4)); // Remove all mappings to 4
m.values().retainAll(Arrays.asList(2, 3)); // Keep only mappings to 2 & 3
// Deletions can also be done via iterators
Iterator<Map.Entry<String,Integer>> iter = m.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry<String,Integer> e = iter.next();
if (e.getValue() == 2) iter.remove();
}
// Find values that appear in both of two maps. In general, addAll() and
// retainAll() with
keySet() and values() allow union and intersection
Set<Integer> v = new HashSet<Integer>(m.values());
v.retainAll(singleton.values());
// Miscellaneous methods
m.clear(); // Deletes all mappings
m.size(); // Returns number of mappings: currently 0
m.isEmpty(); // Returns true
m.equals(empty); // true: Maps implementations override equalsThe Map interface includes a variety of general-purpose and special-purpose implementations, which are summarized in Table 5-4. As always, complete details are in the reference section. All classes in Table 5-4 are in the java.util package except ConcurrentHashMap, which is part of java.util.concurrent.
The ConcurrentHashMap class of the java.util.concurrent package implements the ConcurrentMap interface of the same package. ConcurrentMap extends Map and defines some additional atomic operations that are important in multithreaded programming. For example, the putIfAbsent() method is like put( ) but adds the key/value pair to the map only if the key is not already mapped. treeMap implements the SortedMap interface, which extends Map to add methods that take advantage of the sorted nature of the map. SortedMap is quite similar to the SortedSet interface. The firstKey() and lastKey( ) methods return the first and last keys in the keySet(). And headMap() , tailMap( ), and subMap() return a restricted range of the original map. 5.6.5. The Queue and BlockingQueue InterfacesA queue is an ordered collection of elements with methods for extracting elements, in order, from the head of the queue. Queue implementations are commonly based on insertion order as in first-in, first-out (FIFO) queues or last in, first-out queues (LIFO queues are also known as stacks). Other orderings are possible, however: a priority queue orders its elements according to an external Comparator object, or according to the natural ordering of Comparable elements. Unlike a Set, Queue implementations typically allow duplicate elements. Unlike List, the Queue interface does not define methods for manipulating queue elements at arbitrary positions. Only the element at the head of the queue is available for examination. It is common for Queue implementations to have a fixed capacity: when a queue is full, it is not possible to add more elements. Similarly, when a queue is empty, it is not possible to remove any more elements. Because full and empty conditions are a normal part of many queue-based algorithms, the Queue interface defines methods that signal these conditions with return values rather than by throwing exceptions. Specifically, the peek() and poll( ) methods return null to indicate that the queue is empty. For this reason, most Queue implementations do not allow null elements. A blocking queue is a type of queue that defines blocking put( ) and take() methods. The put( ) method adds an element to the queue, waiting, if necessary, until there is space in the queue for the element. And the take( ) method removes an element from the head of the queue, waiting, if necessary, until there is an element to remove. Blocking queues are an important part of many multithreaded algorithms, and the BlockingQueue interface (which extends Queue) is defined as part of the java.util.concurrent package. Queue, BlockingQueue, and their implementations are new in Java 5.0. See Section 5.7.7 later in this chapter for a list of BlockingQueue implementations. Queues are not nearly as commonly used as sets, lists, and maps, except perhaps in certain multithreaded programming styles. In lieu of example code here, we'll try to clarify the confusing array of queue insertion and removal operations:
The LinkedList class has been retrofitted, in Java 5.0, to implement Queue. It provides unbounded FIFO (first in, first out) ordering, and insertion and removal operations require constant time. LinkedList allows null elements, although their use is discouraged when the list is being used as a queue. The only other Queue implementation in the java.util package is PriorityQueue, which orders its elements according to a Comparator or orders Comparable elements according to the order defined by their compareTo( ) methods. The head of a PriorityQueue is always the the smallest element according to the defined ordering. The java.util.concurrent package contains a number of BlockingQueue implementations; they are described later in the chapter. This package also contains ConcurrentLinkedQueue, an efficient threadsafe Queue implementation that does not suffer the overhead of synchronized methods. 5.6.6. Collection WrappersThe java.util.Collections class is home to quite a few static utility methods designed for use with collections. One important group of these methods are the collection wrapper methods: they return a special-purpose collection wrapped around a collection you specify. The purpose of the wrapper collection is to wrap additional functionality around a collection that does not provide it itself. Wrappers exist to provide thread-safety, write-protection and runtime type checking. Wrapper collections are always backed by the original collection, which means that the methods of the wrapper simply dispatch to the equivalent methods of the wrapped collection. This means that changes made to the collection through the wrapper are visible through the wrapped collection and vice versa. The first set of wrapper methods provides threadsafe wrappers around collections. Except for the legacy classes Vector and Hashtable, the collection implementations in java.util do not have synchronized methods and are not protected against concurrent access by multiple threads. If you need threadsafe collections, create them with code like this: List<String> list = Collections.synchronizedList(new ArrayList<String>());
Set<Integer> set = Collections.synchronizedSet(new HashSet<Integer>());
Map<String,Integer> map =
Collections.synchronizedMap(new HashMap<String,Integer>());A second set of wrapper methods provides collection objects through which the underlying collection cannot be modified. They return a read-only view of a collection: any attempt to change the content of the collection results in an UnsupportedOperationException. These wrappers are useful when you must pass a collection to a method that must not be allowed to modify or mutate the content of the collection in any way: List<Integer> primes = new ArrayList<Integer>(); List<Integer> readonly = Collections.unmodifiableList(primes); // We can modify the list through primes primes.addAll(Arrays.asList(2, 3, 5, 7, 11, 13, 17, 19)); // But we can't modify through the read-only wrapper readonly.add(23); // UnsupportedOperationException The final set of wrapper methods provides runtime type checking of any values added to the collection. They were added in Java 5.0 to complement the compile-time type safety provided by generics. These wrappers are helpful when working with legacy code that has not been converted to use generics. If you have a SortedSet<String>, for example, and must pass it to a method that expects a Set, you can use a checked wrapper to ensure that that method cannot add anything to the set that is not a String: SortedSet<String> words = new TreeSet<String>(); // A set
SortedSet<String> checkedWords = // A checked set
Collections.checkedSortedSet(words, String.class);
addWordsFromFile(checkedWords, filename); // Passed to legacy method5.6.7. Special-Case CollectionsIn addition to its wrapper methods, the java.util.Collections class also defines utility methods for creating immutable collection instances that contain a single element and other methods for creating empty collections. singleton() , singletonList( ), and singletonMap() return immutable Set , List, and Map objects that contain a single specified object or a single key/value pair. These methods are useful, for example, when you need to pass a single object to a method that expects a collection. The Collections class also includes methods that return empty collections. If you are writing a method that returns a collection, it is usually best to handle the no-values-to-return case by returning an empty collection instead of a special-case value like null: Set<Integer> si = Collections.emptySet(); List<String> ss = Collections.emptyList(); Map<String,Integer> m = Collections.emptyMap(); Finally, nCopies() returns an immutable List that contains a specified number of copies of a single specified object: List<Integer> tenzeros = Collections.nCopies(10, 0); 5.6.8. Converting to and from ArraysArrays of objects and collections serve similar purposes. It is possible to convert from one to the other: String[] a ={ "this", "is", "a", "test" }; // An array
List<String> l = Arrays.asList(a); // View array as an ungrowable list
List<String> m = new ArrayList<String>(l); // Make a growable copy of the view
// In Java 5.0, asList() is a varargs method so we can do this, too:
Set<Character> abc = new HashSet<Character>(Arrays.asList('a', 'b', 'c'));
// Collection defines the toArray() method. The no-args version creates
// an Object[] array, copies collection elements to it and returns it
Object[] members = set.toArray(); // Get set elements as an array
Object[] items = list.toArray(); // Get list elements as an array
Object[] keys = map.keySet().toArray(); // Get map key objects as an array
Object[] values = map.values().toArray(); // Get map value objects as an array
// If you want the return value to be something other than Object[], pass
// in an array of the appropriate type. If the array is not big enough,
// another one of the same type will be allocated. If the array is too big,
// the collection elements copied to it will be null-terminated
String[] c = l.toArray(new String[0]);5.6.9. Collections Utility MethodsJust as the java.util.Arrays class defined methods to operate on arrays, the java.util.Collections class defines methods to operate on collections. Most notable are methods to sort and search the elements of collections: Collections.sort(list); int pos = Collections.binarySearch(list, "key"); // list must be sorted first Here are some other interesting Collections methods: Collections.copy(list1, list2); // Copy list2 into list1, overwriting list1 Collections.fill(list, o); // Fill list with Object o Collections.max(c); // Find the largest element in Collection c Collections.min(c); // Find the smallest element in Collection c Collections.reverse(list); // Reverse list Collections.shuffle(list); // Mix up list 5.6.10. Implementing CollectionsThe Java Collections Framework provides abstract classes that make it simple to implement common types of collections. The following code extends AbstractList to define a QuadraticSequence, a list implementation that computes list values on demand rather than actually storing them in memory anywhere. See also AbstractSet, AbstractMap, AbstractQueue, and AbstractSequentialList. import java.util.*;
/** An immutable List<Double> representing the sequence ax^2 + bx + c */
public class QuadraticSequence extends AbstractList<Double> {
final int size;
final double a, b, c;
QuadraticSequence(double a, double b, double c, int size) {
this.a = a; this.b = b; this.c = c; this.size = size;
}
@Override public int size() { return size; }
@Override public Double get(int index) {
if (index<0 || index>=size) throw new ArrayIndexOutOfBoundsException();
return a*index*index + b*index + c;
}
} |
|
|