|
Java Collections API Change Summary
|
We received many excellent suggestions concerning previous Beta releases of
the collections API. Suggestions came from companies, universities, and
individuals all around the world. The total traffic on the collections-comments mailbox
was about 550 typewritten pages. We're truly thankful for these suggestions,
and we've incorporated many of them into the Beta3 API. This page summarizes
the differences between the Beta2 and Beta3 releases, along with a brief
rationale for each change.
The big news here is that we've added two new core collection interfaces,
SortedMap and
SortedSet.
While we regret upping the interface count from four
to six, we think they pull their weight, for reasons outlined below. For
increased power, these new interfaces contain several methods that weren't in
TreeMap. Other notable changes include the addition of
TreeSet and the deletion
of ArraySet and ArrayMap.
Core Collection Interfaces - Collection
- Added a new form of the
toArray method
that allows the caller to select the type of the returned array.
The original form
always returned an array of Object, which necessitated an extra copy
if a different type was required for further processing.
Core Collection Interfaces - List
- List methods that
take indices throw IndexOutOfBoundsException instead of
ArrayIndexOutOfBoundsException.
This clearly makes a lot more sense, as many List implementations
won't use arrays. Since ArrayIndexOutOfBoundsException inherits from
IndexOutOfBoundsException, the legacy List implementation (Vector) satisfies
the improved interface.
-
List's Hash function
is "initialized" to one instead of zero. An initial sequence of
null elements previously had no effect on the hashCode computation. While we
don't expect such sequences to be common, there's no downside to this change.
Core Collection Interfaces - Map
-
Map.entries()
now returns a Set instead of a Collection.
Previously, there was no guarantee that
m1.entries().equals(m2.entries())
would return true
if and only iff m1.equals(m2)
. This was counterintuitive, and
could lead to bugs, especially since many similar idioms
(e.g., m1.entries().containsAll(m2.entries())
returns true
if and only if m2 is a "sub-map" of m1) may well become common.
Core Collection Interfaces - SortedMap, SortedSet
- Added SortedMap
interface which extends Map to characterize self-ordering Maps like
TreeMap. The absence of an
interface that captured the self-ordering behavior exhibited by TreeMap
reduced its power (by not allowing its "subrange views" to return full-fledged
self-ordering Maps), and complicated its implementation. Further, the
addition of this interfaces enables the construction of useful generic
components that manipulate sorted collections (e.g., dictionary chooser"
widgets). It also enables greatly increased performance of certain
operations, as this interfaces can be used to eliminate unnecessary sorts and
costly linear searches by informing the users of certain collections that they
are already sorted.
- Added SortedSet
interface which extends Set to characterize self-ordering Sets like
TreeSet. (See explanation
above.)
- Added headMap(toKey) and tailMap(fromKey)
methods. With the
subMap(fromKey, toKey)
method, it was not, in general, possible to get a view of the "head" of the
Map (from the beginning up to a given key), nor the "tail" (from a given key
to the end). These new methods provide this useful functionality.
(Analogous methods
are present in SortedSet.)
- Added firstKey and lastKey
methods, which allow quick, easy access to the
first or last key in a sorted Map.
It was not previously possible to efficiently determine the predecessor of a
given key (or element) in a TreeMap. This is now possible with the idiom
predecessor = headMap(k).lastKey();
. (Analogous methods are
present in SortedSet.)
- Added
comparator()
method.
that returns the Comparator used to order the Map. This is required in order
to "clone" (copy-construct) an SortedMap into a different SortedMap type.
(An analogous method
is present in SortedSet.)
- Clarification: it is now specified explicitly that SortedMap (and SortedSet) will not obey the
semantics of Map (and Set) if the specified key (or element) ordering is not
total.
Concrete Implementations
Two concrete implementation that did not pull their weight were
unceremoniously eliminated, and one new one (TreeSet, referred to above), was
added. While not an API change, it is worth noting that serialization
now works for all of general-purpose Collection Implementations.
- Eliminated ArraySet, a Set backed by a growable array.
This class was advertised to be "substantially cheaper than HashSet for
very small Sets", but it wasn't, even when we optimized it as best we could.
Coupled with its disastrous (quadratic) behavior for large Sets, we thought
that it was best forgotten.
- Eliminated ArrayMap, a Map backed
by a growable array, for reasons analogous to those given for ArraySet.
- Added TreeSet, a SortedSet
backed by a Red-Black tree. This was widely requested by customers. It fills
an obvious hole in our implementation matrix, and adds little conceptual
weight.
- Added null-key support to HashMap.
This was done for consistency with TreeMap and the late, unlamented ArrayMap,
and because customers requested it. Now all of our general-purpose collection
implementations accept null keys, values and elements.
- Added public
clone method to TreeMap. This was unintentionally omitted in the
previous release. Also, TreeMap now implements Cloneable, for all that's
worth.
Infrastructure
-
ListIterator's remove method is now legal only if add
has not been called after the last call to next or previous.
Similarly, the set method is legal
only if neither remove nor add have been called after the last call to next or
previous. If any of these conditions are violated, IllegalStateException is
thrown. While these operations were previously legal, their semantics were
confusing, we knew of no uses for them, and they were difficult to implement.
Algorithms and Array Operations
-
Added
Collections.REVERSE_ORDER, a "constant" (public static final)
Comparator that sorts Comparables backwards. This enables idioms like
Arrays.sort(myStringArray, Collections.REVERSE_ORDER);
to sort
an array (or List) of Strings (or any other Comparable type) backwards.
- Modified Arrays.sort(Object[]),
Arrays.sort(Object[], Comparator), Collections.sort(List),
and
Collections.sort(List, Comparator) to use a
stable sort algorithm (one that does not reorder equal
elements). This is especially useful for GUIs that let the user click on a
column header to sort on that column. Users expect that previous sort(s)
won't be lost. For example, sorting your mail by sender when it's already
sorted by date should leave mail from each sender sorted by date. The
algorithm, a merge sort, provides performance on par with quicksort for
randomly ordered arrays, and substantially better performance for partially
sorted arrays. Unlike quicksort, it guarantees n*log(n) time
performance.
- Provided Arrays.equals
methods, which do value based comparisons on arrays of primitives and
Objects (unlike the Object.equals method, which performs identity comparisons
when applied to arrays).
- Provided Arrays.fill methods,
which set each element of an array to the same value. We anticipate that
these methods will soon be implemented as native methods for speed when
applied to large arrays. (This operation is performance-critical in various
areas, including graphics.)