Java in a Nutshell, 5th Edition [Electronic resources] نسخه متنی

5.6. Collections

The 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 Interface

Collection<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 Interface

A

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 Interface

A 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 everything

A
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 Interface

A

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 equals

The
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 Interfaces

A

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:

• Adding elements to queues

add()

This Collection method simply adds an element in
the normal way. In bounded queues, this method may throw an exception
if the queue is full.

offer()

This Queue method is like add(
) but returns false instead of throwing
an exception if the element cannot be added because a bounded queue
is full.

BlockingQueue defines a timeout version of
offer( ) that waits up to a specified amount of
time for space to become available in a full queue. Like the basic
version of the method, it returns true if the
element was inserted and false otherwise.

put( )

This BlockingQueue method blocks: if the element
cannot be inserted because the queue is full, put(
) waits until some other thread removes an element from the
queue, and space becomes available for the new element.

• Removing elements from queues

remove()

In addition to the Collection.remove( ) method,
which removes a specified element from the queue, the
Queue interface defines a no-argument version of
remove( ) that removes and returns the element at
the head of the queue. If the queue is empty, this method throws a
NoSuchElementException.

poll( )

This Queue method removes and returns the element
at the head of the queue, like remove( ) does but
returns null if the queue is empty instead of
throwing an exception.

BlockingQueue defines a timeout version of
poll() that waits up to a specified amount of time
for an element to be added to an empty queue.

take()

This BlockingQueue method removes and returns the
element at the head of the queue. If the queue is empty, it blocks
until some other thread adds an element to the queue.

drainTo( )

This BlockingQueue method removes all available
elements from the queue and adds them to a specified
Collection. It does not block to wait for elements
to be added to the queue. A variant of the method accepts a maximum
number of elements to drain.

• Querying the element at the head, without removing it from the queue

element( )

This Queue method returns the element at the head
of the queue but does not remove that element from the queue. If the
queue is empty, it throws NoSuchElementException.

peek( )

This Queue method is like
element() but returns null if
the queue is empty.

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 Wrappers

The
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 method

5.6.7. Special-Case Collections

In 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 Arrays

Arrays 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 Methods

Just 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 Collections

The

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;
}
}