The methods of this class all throw a NullPointerException if the collections or class objects provided to them are null.
The documentation for the polymorphic algorithms contained in this class generally includes a brief description of the implementation. Such descriptions should be regarded as implementation notes, rather than parts of the specification. Implementors should feel free to substitute other algorithms, so long as the specification itself is adhered to. (For example, the algorithm used by sort does not have to be a mergesort, but it does have to be stable.)
The "destructive" algorithms contained in this class, that is, the algorithms that modify the collection on which they operate, are specified to throw UnsupportedOperationException if the collection does not support the appropriate mutation primitive(s), such as the set method. These algorithms may, but are not required to, throw this exception if an invocation would have no effect on the collection. For example, invoking the sort method on an unmodifiable list that is already sorted may or may not throw UnsupportedOperationException.
This class is a member of the Java Collections Framework.
When elements are specified individually, this method provides a convenient way to add a few elements to an existing collection:
Collections.addAll(flavors, "Peaches 'n Plutonium", "Rocky Racoon");
This method runs in log(n) time for a "random access" list (which provides near-constant-time positional access). If the specified list does not implement the RandomAccess interface and is large, this method will do an iterator-based binary search that performs O(n) link traversals and O(log n) element comparisons.
This method runs in log(n) time for a "random access" list (which provides near-constant-time positional access). If the specified list does not implement the RandomAccess interface and is large, this method will do an iterator-based binary search that performs O(n) link traversals and O(log n) element comparisons.
The generics mechanism in the language provides compile-time (static) type checking, but it is possible to defeat this mechanism with unchecked casts. Usually this is not a problem, as the compiler issues warnings on all such unchecked operations. There are, however, times when static type checking alone is not sufficient. For example, suppose a collection is passed to a third-party library and it is imperative that the library code not corrupt the collection by inserting an element of the wrong type.
Another use of dynamically typesafe views is debugging. Suppose a program fails with a ClassCastException, indicating that an incorrectly typed element was put into a parameterized collection. Unfortunately, the exception can occur at any time after the erroneous element is inserted, so it typically provides little or no information as to the real source of the problem. If the problem is reproducible, one can quickly determine its source by temporarily modifying the program to wrap the collection with a dynamically typesafe view. For example, this declaration:
Collection<String> c = new HashSet<String>();
may be replaced temporarily by this one:
Collection<String> c = Collections.checkedCollection(
new HashSet<String>(), String.class);
Running the program again will cause it to fail at the point where
an incorrectly typed element is inserted into the collection, clearly
identifying the source of the problem. Once the problem is fixed, the
modified declaration may be reverted back to the original.
The returned collection does not pass the hashCode and equals operations through to the backing collection, but relies on Object's equals and hashCode methods. This is necessary to preserve the contracts of these operations in the case that the backing collection is a set or a list.
The returned collection will be serializable if the specified collection is serializable.
A discussion of the use of dynamically typesafe views may be found in the documentation for the checkedCollection method.
The returned list will be serializable if the specified list is serializable.
Assuming a map contains no incorrectly typed keys or values prior to the time a dynamically typesafe view is generated, and that all subsequent access to the map takes place through the view (or one of its collection views), it is guaranteed that the map cannot contain an incorrectly typed key or value.
A discussion of the use of dynamically typesafe views may be found in the documentation for the checkedCollection method.
The returned map will be serializable if the specified map is serializable.
A discussion of the use of dynamically typesafe views may be found in the documentation for the checkedCollection method.
The returned set will be serializable if the specified set is serializable.
Assuming a map contains no incorrectly typed keys or values prior to the time a dynamically typesafe view is generated, and that all subsequent access to the map takes place through the view (or one of its collection views), it is guaranteed that the map cannot contain an incorrectly typed key or value.
A discussion of the use of dynamically typesafe views may be found in the documentation for the checkedCollection method.
The returned map will be serializable if the specified map is serializable.
A discussion of the use of dynamically typesafe views may be found in the documentation for the checkedCollection method.
The returned sorted set will be serializable if the specified sorted set is serializable.
This method runs in linear time.
Care must be exercised if this method is used on collections that do not comply with the general contract for Collection. Implementations may elect to iterate over either collection and test for containment in the other collection (or to perform any equivalent computation). If either collection uses a nonstandard equality test (as does a SortedSet whose ordering is not compatible with equals, or the key set of an IdentityHashMap ), both collections must use the same nonstandard equality test, or the result of this method is undefined.
Note that it is permissible to pass the same collection in both parameters, in which case the method will return true if and only if the collection is empty.
This example illustrates the type-safe way to obtain an empty list:
List<String> s = Collections.emptyList();
Implementation note: Implementations of this method need not
create a separate List object for each call. Using this
method is likely to have comparable cost to using the like-named
field. (Unlike this method, the field does not provide type safety.)This example illustrates the type-safe way to obtain an empty set:
Map<String, Date> s = Collections.emptyMap();
Implementation note: Implementations of this method need not
create a separate Map object for each call. Using this
method is likely to have comparable cost to using the like-named
field. (Unlike this method, the field does not provide type safety.)This example illustrates the type-safe way to obtain an empty set:
Set<String> s = Collections.emptySet();
Implementation note: Implementations of this method need not
create a separate Set object for each call. Using this
method is likely to have comparable cost to using the like-named
field. (Unlike this method, the field does not provide type safety.)
The equals method implements an equivalence relation
on non-null object references:
x, x.equals(x) should return
true.
x and y, x.equals(y)
should return true if and only if
y.equals(x) returns true.
x, y, and z, if
x.equals(y) returns true and
y.equals(z) returns true, then
x.equals(z) should return true.
x and y, multiple invocations of
x.equals(y) consistently return true
or consistently return false, provided no
information used in equals comparisons on the
objects is modified.
x,
x.equals(null) should return false.
The equals method for class Object implements
the most discriminating possible equivalence relation on objects;
that is, for any non-null reference values x and
y, this method returns true if and only
if x and y refer to the same object
(x == y has the value true).
Note that it is generally necessary to override the hashCode method whenever this method is overridden, so as to maintain the general contract for the hashCode method, which states that equal objects must have equal hash codes.
This method runs in linear time.
java.util.Hashtable.
The general contract of hashCode is:
hashCode method on each of
the two objects must produce the same integer result.
As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)
This implementation uses the "brute force" technique of scanning over the source list, looking for a match with the target at each location in turn.
This implementation uses the "brute force" technique of iterating over the source list, looking for a match with the target at each location in turn.
This method iterates over the entire collection, hence it requires time proportional to the size of the collection.
This method iterates over the entire collection, hence it requires time proportional to the size of the collection.
This method iterates over the entire collection, hence it requires time proportional to the size of the collection.
This method iterates over the entire collection, hence it requires time proportional to the size of the collection.
wait methods.
The awakened thread will not be able to proceed until the current thread relinquishes the lock on this object. The awakened thread will compete in the usual manner with any other threads that might be actively competing to synchronize on this object; for example, the awakened thread enjoys no reliable privilege or disadvantage in being the next thread to lock this object.
This method should only be called by a thread that is the owner of this object's monitor. A thread becomes the owner of the object's monitor in one of three ways:
synchronized statement
that synchronizes on the object.
Class, by executing a
synchronized static method of that class.
Only one thread at a time can own an object's monitor.
wait methods.
The awakened threads will not be able to proceed until the current thread relinquishes the lock on this object. The awakened threads will compete in the usual manner with any other threads that might be actively competing to synchronize on this object; for example, the awakened threads enjoy no reliable privilege or disadvantage in being the next thread to lock this object.
This method should only be called by a thread that is the owner
of this object's monitor. See the notify method for a
description of the ways in which a thread can become the owner of
a monitor.
This method runs in linear time.
Arrays.sort(a, Collections.reverseOrder());sorts the array in reverse-lexicographic (alphabetical) order.
The returned comparator is serializable.
The returned comparator is serializable (assuming the specified comparator is also serializable or null).
For example, suppose list comprises [t, a, n, k, s]. After invoking Collections.rotate(list, 1) (or Collections.rotate(list, -4)), list will comprise [s, t, a, n, k].
Note that this method can usefully be applied to sublists to move one or more elements within a list while preserving the order of the remaining elements. For example, the following idiom moves the element at index j forward to position k (which must be greater than or equal to j):
Collections.rotate(list.subList(j, k+1), -1);
To make this concrete, suppose list comprises
[a, b, c, d, e]. To move the element at index 1
(b) forward two positions, perform the following invocation:
Collections.rotate(l.subList(1, 4), -1);
The resulting list is [a, c, d, b, e].
To move more than one element forward, increase the absolute value of the rotation distance. To move elements backward, use a positive shift distance.
If the specified list is small or implements the RandomAccess interface, this implementation exchanges the first element into the location it should go, and then repeatedly exchanges the displaced element into the location it should go until a displaced element is swapped into the first element. If necessary, the process is repeated on the second and successive elements, until the rotation is complete. If the specified list is large and doesn't implement the RandomAccess interface, this implementation breaks the list into two sublist views around index -distance mod size. Then the method is invoked on each sublist view, and finally it is invoked on the entire list. For a more complete description of both algorithms, see Section 2.3 of Jon Bentley's Programming Pearls (Addison-Wesley, 1986).
The hedge "approximately" is used in the foregoing description because default source of randomness is only approximately an unbiased source of independently chosen bits. If it were a perfect source of randomly chosen bits, then the algorithm would choose permutations with perfect uniformity.
This implementation traverses the list backwards, from the last element up to the second, repeatedly swapping a randomly selected element into the "current position". Elements are randomly selected from the portion of the list that runs from the first element to the current position, inclusive.
This method runs in linear time. If the specified list does not implement the RandomAccess interface and is large, this implementation dumps the specified list into an array before shuffling it, and dumps the shuffled array back into the list. This avoids the quadratic behavior that would result from shuffling a "sequential access" list in place.
This implementation traverses the list backwards, from the last element up to the second, repeatedly swapping a randomly selected element into the "current position". Elements are randomly selected from the portion of the list that runs from the first element to the current position, inclusive.
This method runs in linear time. If the specified list does not implement the RandomAccess interface and is large, this implementation dumps the specified list into an array before shuffling it, and dumps the shuffled array back into the list. This avoids the quadratic behavior that would result from shuffling a "sequential access" list in place.
This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.
The specified list must be modifiable, but need not be resizable.
The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance. This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place.
This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.
The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance. The specified list must be modifiable, but need not be resizable. This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place.
It is imperative that the user manually synchronize on the returned collection when iterating over it:
Collection c = Collections.synchronizedCollection(myCollection);
...
synchronized(c) {
Iterator i = c.iterator(); // Must be in the synchronized block
while (i.hasNext())
foo(i.next());
}
Failure to follow this advice may result in non-deterministic behavior.
The returned collection does not pass the hashCode and equals operations through to the backing collection, but relies on Object's equals and hashCode methods. This is necessary to preserve the contracts of these operations in the case that the backing collection is a set or a list.
The returned collection will be serializable if the specified collection is serializable.
It is imperative that the user manually synchronize on the returned list when iterating over it:
List list = Collections.synchronizedList(new ArrayList());
...
synchronized(list) {
Iterator i = list.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());
}
Failure to follow this advice may result in non-deterministic behavior.
The returned list will be serializable if the specified list is serializable.
It is imperative that the user manually synchronize on the returned map when iterating over any of its collection views:
Map m = Collections.synchronizedMap(new HashMap());
...
Set s = m.keySet(); // Needn't be in synchronized block
...
synchronized(m) { // Synchronizing on m, not s!
Iterator i = s.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());
}
Failure to follow this advice may result in non-deterministic behavior.
The returned map will be serializable if the specified map is serializable.
It is imperative that the user manually synchronize on the returned set when iterating over it:
Set s = Collections.synchronizedSet(new HashSet());
...
synchronized(s) {
Iterator i = s.iterator(); // Must be in the synchronized block
while (i.hasNext())
foo(i.next());
}
Failure to follow this advice may result in non-deterministic behavior.
The returned set will be serializable if the specified set is serializable.
It is imperative that the user manually synchronize on the returned sorted map when iterating over any of its collection views, or the collections views of any of its subMap, headMap or tailMap views.
SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap());
...
Set s = m.keySet(); // Needn't be in synchronized block
...
synchronized(m) { // Synchronizing on m, not s!
Iterator i = s.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());
}
or:
SortedMap m = Collections.synchronizedSortedMap(new HashSortedMap());
SortedMap m2 = m.subMap(foo, bar);
...
Set s2 = m2.keySet(); // Needn't be in synchronized block
...
synchronized(m) { // Synchronizing on m, not m2 or s2!
Iterator i = s.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());
}
Failure to follow this advice may result in non-deterministic behavior.
The returned sorted map will be serializable if the specified sorted map is serializable.
It is imperative that the user manually synchronize on the returned sorted set when iterating over it or any of its subSet, headSet, or tailSet views.
SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet());
...
synchronized(s) {
Iterator i = s.iterator(); // Must be in the synchronized block
while (i.hasNext())
foo(i.next());
}
or:
SortedSet s = Collections.synchronizedSortedSet(new HashSortedSet());
SortedSet s2 = s.headSet(foo);
...
synchronized(s) { // Note: s, not s2!!!
Iterator i = s2.iterator(); // Must be in the synchronized block
while (i.hasNext())
foo(i.next());
}
Failure to follow this advice may result in non-deterministic behavior.
The returned sorted set will be serializable if the specified sorted set is serializable.
toString method returns a string that
"textually represents" this object. The result should
be a concise but informative representation that is easy for a
person to read.
It is recommended that all subclasses override this method.
The toString method for class Object
returns a string consisting of the name of the class of which the
object is an instance, the at-sign character `@', and
the unsigned hexadecimal representation of the hash code of the
object. In other words, this method returns a string equal to the
value of:
getClass().getName() + '@' + Integer.toHexString(hashCode())
The returned collection does not pass the hashCode and equals operations through to the backing collection, but relies on Object's equals and hashCode methods. This is necessary to preserve the contracts of these operations in the case that the backing collection is a set or a list.
The returned collection will be serializable if the specified collection is serializable.
The returned list will be serializable if the specified list is serializable. Similarly, the returned list will implement RandomAccess if the specified list does.
The returned map will be serializable if the specified map is serializable.
The returned set will be serializable if the specified set is serializable.
The returned sorted map will be serializable if the specified sorted map is serializable.
The returned sorted set will be serializable if the specified sorted set is serializable.
The current thread must own this object's monitor. The thread
releases ownership of this monitor and waits until another thread
notifies threads waiting on this object's monitor to wake up
either through a call to the notify method or the
notifyAll method. The thread then waits until it can
re-obtain ownership of the monitor and resumes execution.
As in the one argument version, interrupts and spurious wakeups are possible, and this method should always be used in a loop:
synchronized (obj) {
while (<condition does not hold>)
obj.wait();
... // Perform action appropriate to condition
}
This method should only be called by a thread that is the owner
of this object's monitor. See the notify method for a
description of the ways in which a thread can become the owner of
a monitor.The current thread must own this object's monitor.
This method causes the current thread (call it T) to place itself in the wait set for this object and then to relinquish any and all synchronization claims on this object. Thread T becomes disabled for thread scheduling purposes and lies dormant until one of four things happens:
A thread can also wake up without being notified, interrupted, or timing out, a so-called spurious wakeup. While this will rarely occur in practice, applications must guard against it by testing for the condition that should have caused the thread to be awakened, and continuing to wait if the condition is not satisfied. In other words, waits should always occur in loops, like this one:
synchronized (obj) {
while (<condition does not hold>)
obj.wait(timeout);
... // Perform action appropriate to condition
}
(For more information on this topic, see Section 3.2.3 in Doug Lea's
"Concurrent Programming in Java (Second Edition)" (Addison-Wesley,
2000), or Item 50 in Joshua Bloch's "Effective Java Programming
Language Guide" (Addison-Wesley, 2001).
If the current thread is interrupted by another thread while it is waiting, then an InterruptedException is thrown. This exception is not thrown until the lock status of this object has been restored as described above.
Note that the wait method, as it places the current thread into the wait set for this object, unlocks only this object; any other objects on which the current thread may be synchronized remain locked while the thread waits.
This method should only be called by a thread that is the owner
of this object's monitor. See the notify method for a
description of the ways in which a thread can become the owner of
a monitor.
This method is similar to the wait method of one
argument, but it allows finer control over the amount of time to
wait for a notification before giving up. The amount of real time,
measured in nanoseconds, is given by:
1000000*timeout+nanos
In all other respects, this method does the same thing as the method of one argument. In particular, wait(0, 0) means the same thing as wait(0).
The current thread must own this object's monitor. The thread releases ownership of this monitor and waits until either of the following two conditions has occurred:
notify method
or the notifyAll method.
timeout
milliseconds plus nanos nanoseconds arguments, has
elapsed.
The thread then waits until it can re-obtain ownership of the monitor and resumes execution.
As in the one argument version, interrupts and spurious wakeups are possible, and this method should always be used in a loop:
synchronized (obj) {
while (<condition does not hold>)
obj.wait(timeout, nanos);
... // Perform action appropriate to condition
}
This method should only be called by a thread that is the owner
of this object's monitor. See the notify method for a
description of the ways in which a thread can become the owner of
a monitor.