The majority of the non-final
methods of the Object
class are meant to be overridden. They provide general contracts for objects, which the classes overriding the methods should honor.
It is important to understand how and why a class should override the equals()
and hashCode()
methods. Implementation of the compareTo()
method of the Comparable
interface is closely related to the other two methods.
Objects of a class that override the equals()
method can be used as elements in a collection. If they override the hashCode()
method, they can also be used as elements in a HashSet
and as keys in a HashMap
. Implementing the Comparable
interface allows them to be used as elements in sorted collections and as keys in sorted maps. Table 15.2 on p. 782 summarizes the methods that objects should provide if the objects are to be maintained in collections and maps.
As a running example, we will implement different versions of a class for version numbers. A version number (VNO) for a software product comprises three pieces of information:
• a release number
• a revision number
• a patch number
The idea is that releases do not happen very often. Revisions take place more frequently than releases, but less frequently than code patches are issued. We can say that the release number is most significant. The revision number is less significant than the release number, and the patch number is the least significant of the three fields. This ranking would also be employed when ordering version numbers chronologically.
We will develop different implementations of the version number in this section and test them using the test()
method declared at (1) in the TestCaseVNO
class (Example 15.1). This static method is a generic method, with type parameter N
representing a version number class.
The test()
method in Example 15.1 is passed three references (latest
, inShops
, older
) that denote three different objects of a version number class, as shown at (2a), (2b), and (2c), respectively. It is also passed an array of version numbers, named versions
, as shown at (3). The last parameter, shown at (4), is an array of Integer
s, named downloads
, whose elements represent the number of downloads for the version numbers from the corresponding position in the versions
array. The method prints the name of the version number class at (5) from one of the version numbers passed as parameter. The method then performs various tests on the version numbers and tries to use them in different ways. This is explained in more detail below.
Example 15.1 A Test Case for Version Numbers
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.TreeSet;
import static java.lang.System.out;
public class TestCaseVNO {
/** Type parameter N represents a class
implementing a version number. */
public static <N> void test( // (1)
N latest, // (2a)
N inShops, // (2b)
N older, // (2c)
N[] versions, // (3)
Integer[] downloads) { // (4)
// Print the class name.
out.println(latest.getClass()); // (5)
// Various tests.
out.println("Test object reference and value equality:");
out.printf (" latest: %s, inShops: %s, older: %s%n" ,
latest, inShops, older);
out.println(" latest == inShops: " + (latest == inShops)); // (6)
out.println(" latest.equals(inShops): " +
(latest.equals(inShops))); // (7)
out.println(" latest == older: " + (latest == older)); // (8)
out.println(" latest.equals(older): " + latest.equals(older));// (9)
N searchKey = inShops; // (10)
boolean found = false;
for (N version : versions) {
found = searchKey.equals(version); // (11)
if (found) break;
}
out.println("Array: " + Arrays.toString(versions)); // (12)
out.println(" Search key " + searchKey + " found in array: " +
found); // (13)
List<N> vnoList = Arrays.asList(versions); // (14)
out.println("List: " + vnoList);
out.println(" Search key " + searchKey + " contained in list: " +
vnoList.contains(searchKey)); // (15)
Map<N, Integer> versionStatistics = new
HashMap<N, Integer>(); // (16)
for (int i = 0; i < versions.length; i++) // (17)
versionStatistics.put(versions[i], downloads[i]);
out.println("Map: " + versionStatistics); // (18)
out.println(" Hash code for keys in the map:");
for (N version : versions) // (19)
out.printf(" %10s: %s%n", version, version.hashCode());
out.println(" Search key " + searchKey + " has hash code: " +
searchKey.hashCode()); // (20)
out.println(" Map contains search key " + searchKey + ": " +
versionStatistics.containsKey(searchKey)); // (21)
out.println("Sorted set:
" + (new TreeSet<N>(vnoList))); // (22)
out.println("Sorted map:
" +
(new TreeMap<N, Integer>(versionStatistics))); // (23)
out.println("List before sorting: " + vnoList);
Collections.sort(vnoList, null); // (24)
out.println("List after sorting: " + vnoList);
int resultIndex = Collections.binarySearch(vnoList, searchKey, null);// (25)
out.println("Binary search in list found key " + searchKey +
" at index: " + resultIndex);
}
}
Output from running the program in Example 15.9, p. 769, that uses the TestCaseVNO
class:
class VersionNumber
Test object reference and value equality:
latest: (9.1.1), inShops: (9.1.1), older: (6.6.6)
latest == inShops: false
latest.equals(inShops): true
latest == older: false
latest.equals(older): false
Array: [(3.49.1), (8.19.81), (2.48.28), (10.23.78), (9.1.1)]
Search key (9.1.1) found in array: true
List: [(3.49.1), (8.19.81), (2.48.28), (10.23.78), (9.1.1)]
Search key (9.1.1) contained in list: true
Map: {(9.1.1)=123, (2.48.28)=54, (8.19.81)=786, (3.49.1)=245, (10.23.78)=1010}
Hash code for keys in the map:
(3.49.1): 332104
(8.19.81): 336059
(2.48.28): 331139
(10.23.78): 338102
(9.1.1): 336382
Search key (9.1.1) has hash code: 336382
Map contains search key (9.1.1): true
Sorted set:
[(2.48.28), (3.49.1), (8.19.81), (9.1.1), (10.23.78)]
Sorted map:
{(2.48.28)=54, (3.49.1)=245, (8.19.81)=786, (9.1.1)=123, (10.23.78)=1010}
List before sorting: [(3.49.1), (8.19.81), (2.48.28),
(10.23.78), (9.1.1)]
List after sorting: [(2.48.28), (3.49.1), (8.19.81),
(9.1.1), (10.23.78)]
Binary search in list found key (9.1.1) at index: 3
The workings of the test()
method in Example 15.1 are best understood in terms of what it prints. The output shown in Example 15.1 corresponds to running the program in Example 15.9, p. 769. This program calls the test()
method with objects of the VersionNumber
class from Example 15.8. The VersionNumber
class overrides the equals()
and the hashCode()
methods, and implements the Comparable
interface.
The version numbers are tested for both object reference and object value equality. The object referenced by the reference latest
is compared with the object referenced by the reference inShops
and with the object referenced by the reference older
, as shown at (6), (7), (8), and (9). The output from the program shows that the result is false
for object reference equality and the result for object value equality is true
if the objects have the same state.
Overriding the equals()
method appropriately makes it possible to search for objects in arrays, collections, or maps. Searching involves specifying a copy object, called the search key, which can be compared with objects in the collection. Searching in an array is illustrated by the code from (10) to (13). As can be seen from the output, searching for the version number (9.1.1)
in the versions
array is successful.
The versions
array is converted to a List
at (14), referenced by the reference vnoList
, and the contains()
method is called at (15) to determine whether the search key is in this list. The contains()
method of a List
relies on the equals()
method provided by its elements. The result is, as expected, true
.
An empty HashMap
is created at (16) and populated at (17) with version numbers as keys and Integer
objects as values, based on the associative arrays versions
and downloads
. The versionStatistics
map is printed at (18). Hash codes for all the map keys are printed at (19), and the hash code for the search key is printed at (20). Since the hashCode()
method is overridden by the version number class, the attempt to determine whether the search key is in the map is successful.
A sorted set and a sorted map are created from the vnoList
list and the versionStatistics
map at (22) and (23), respectively. The program output shows that the version numbers in the TreeSet
and the TreeMap
are sorted in natural ordering.
The unsorted vnoList
is sorted successfully at (24). Finally, a binary search for the key in the sorted list at (25) is also reported to be successful.
At (24) and (25), the null
value is passed as a comparator. The method called then assumes natural ordering. This was necessary to avoid compile time errors with some of the implementations of the version number discussed in this section.
If every object is to be considered unique, then it is not necessary to override the equals()
method in the Object
class. This method implements object reference equality. It implements the most discriminating equivalence relation possible on objects. Each instance of the class is only equal to itself.
The class SimpleVNO
in Example 15.2 does not override the equals()
method in the Object
class. It only overrides the toString()
method to generate a meaningful textual representation for a version number.
Example 15.2 Not Overriding the equals()
and the hashCode()
Methods
public class SimpleVNO {
// Does not override equals() or hashCode().
private int release;
private int revision;
private int patch;
public SimpleVNO(int release, int revision, int patch) {
this.release = release;
this.revision = revision;
this.patch = patch;
}
public String toString() {
return "(" + release + "." + revision + "." + patch + ")";
}
}
The class TestSimpleVNO
in Example 15.3 creates objects of the class SimpleVNO
to test with the test()
method of the TestCaseVNO
class in Example 15.1, passing the relevant objects to this method as explained earlier. Successive implementations of the version number will also be tested in the same way.
Example 15.3 Testing the equals()
and the hashCode()
Methods
public class TestSimpleVNO {
public static void main(String[] args) {
// Three individual version numbers.
SimpleVNO latest = new SimpleVNO(9,1,1); // (1)
SimpleVNO inShops = new SimpleVNO(9,1,1); // (2)
SimpleVNO older = new SimpleVNO(6,6,6); // (3)
// An array of version numbers.
SimpleVNO[] versions = new SimpleVNO[] { // (4)
new SimpleVNO( 3,49, 1), new SimpleVNO( 8,19,81),
new SimpleVNO( 2,48,28), new SimpleVNO(10,23,78),
new SimpleVNO( 9, 1, 1)};
// An array with number of downloads.
Integer[] downloads = {245, 786, 54,1010, 123}; // (5)
TestCaseVNO.test(latest, inShops, older, versions, downloads); // (6)
}
}
Output from the program:
class SimpleVNO
Test object reference and value equality:
latest: (9.1.1), inShops: (9.1.1), older: (6.6.6)
latest == inShops: false
latest.equals(inShops): false
latest == older: false
latest.equals(older): false
Array: [(3.49.1), (8.19.81), (2.48.28), (10.23.78), (9.1.1)]
Search key (9.1.1) found in array: false
List: [(3.49.1), (8.19.81), (2.48.28), (10.23.78), (9.1.1)]
Search key (9.1.1) contained in list: false
Map: {(9.1.1)=123, (2.48.28)=54, (8.19.81)=786, (3.49.1)=245, (10.23.78)=1010}
Hash code for keys in the map:
(3.49.1): 8451275
(8.19.81): 4669910
(2.48.28): 3374351
(10.23.78): 5737707
(9.1.1): 31771588
Search key (9.1.1) has hash code: 31393597
Map contains search key (9.1.1): false
Exception in thread "main" java.lang.ClassCastException:
SimpleVNO cannot be cast
to java.lang.Comparable
...
at TestCaseVNO.test(TestCaseVNO.java:57)
at TestSimpleVNO.main(TestSimpleVNO.java:15)
The output in Example 15.3 demonstrates that all SimpleVNO
objects are unique, because the class SimpleVNO
does not override the equals()
method to provide any other equivalence relation. The result is false
for object reference equality and for object value equality. The references refer to distinct objects, although the objects referenced by two of the references have identical states.
Not overriding the equals()
method appropriately makes it impossible to search for SimpleVNO
objects in arrays, collections, or maps. Since all SimpleVNO
objects are distinct, the equals()
method in the Object
class will always return false
, regardless of which object is compared with the search key. As shown by the output from Example 15.3, searching for the version number (9.1.1)
in the versions
array will always fail. Not surprisingly, the result is the same when searching for a key in a list of SimpleVNO
objects. The contains()
method of the list relies on the equals()
method.
It is possible to create a HashMap
with SimpleVNO
objects as keys and Integer
objects as values, based on the associative arrays versions
and downloads.
Since the hashCode()
method is not overridden either, the method implementation in the Object
class attempts to return distinct integers as hash codes for the objects. Hash codes for all the keys in the map and the search key are all distinct, as the output shows. Searching for a SimpleVNO
object in a hash map using hash codes is not successful.
An attempt to create a sorted set results in a ClassCastException
. The class SimpleVNO
must either implement the compareTo()
method of the Comparable
interface, or a comparator must be provided, in order for its objects to be maintained in sorted sets or sorted maps (see Section 15.5, p. 802, and Section 15.10, p. 828). However, the result is unpredictable when objects that do not meet the criteria are used in these collections.
An implementation of the equals()
method must satisfy the properties of an equivalence relation:
• Reflexive: For any reference self
, self.equals(self)
is always true
.
• Symmetric: For any references x
and y
, x.equals(y)
is true
if and only if y.equals(x)
is true
.
• Transitive: For any references x
, y
, and z
, if both x.equals(y)
and y.equals(z)
are true
, then x.equals(z)
is true
.
• Consistent: For any references x
and y
, multiple invocations of x.equals(y)
will always return the same result, provided the objects referenced by these references have not been modified to affect the equals comparison.
• null
comparison: For any non-null
reference obj
, the call obj.equals(null)
always returns false
.
The general contract of the equals()
method is defined between objects of arbitrary classes. Understanding its criteria is important for providing a proper implementation.
This rule simply states that an object is equal to itself, regardless of how it is modified. It is easy to satisfy: the object passed as argument and the current object are compared for object reference equality (==
):
if (this == argumentObj)
return true;
The expression x.equals(y)
invokes the equals()
method on the object referenced by the reference x
, whereas the expression y.equals(x)
invokes the equals()
method on the object referenced by the reference y
. Both invocations must return the same result.
If the equals()
methods invoked are in different classes, the classes must bilaterally agree whether their objects are equal or not. In other words, symmetry can be violated if the equals()
method of a class makes unilateral decisions about which classes it will interoperate with, while the other classes are not aware of this. Avoiding interoperability with other (non-related) classes when implementing the equals()
method is strongly recommended.
If two classes, A
and B
, have a bilateral agreement on their objects being equal, then this rule guarantees that one of them, say B
, does not enter into an agreement with a third class C
on its own. All classes involved must multilaterally abide by the terms of the contract.
A typical pitfall resulting in broken transitivity is when the equals()
method in a subclass calls the equals()
method of its superclass, as part of its equals comparison. The equals()
method in the subclass usually has code equivalent to the following line:
return super.equals(argumentObj) && compareSubclassSpecificAspects();
The idea is to compare only the subclass-specific aspects in the subclass equals()
method and to use the superclass equals()
method for comparing the superclassspecific aspects. However, this approach should be used with extreme caution. The problem lies in getting the equivalence contract fulfilled bilaterally between the superclass and the subclass equals()
methods. If the subclass equals()
method does not interoperate with superclass objects, symmetry is easily broken. If the subclass equals()
method does interoperate with superclass objects, transitivity is easily broken.
If the superclass is abstract, using the superclass equals()
method works well. There are no superclass objects for the subclass equals()
method to consider. In addition, the superclass equals()
method cannot be called directly by any other clients than subclasses. The subclass equals()
method then has control of how the superclass equals()
method is called. It can safely call the superclass equals()
method to compare the superclass-specific aspects of subclass objects.
This rule enforces that two objects that are equal (or non-equal) remain equal (or non-equal) as long as they are not modified. For mutable objects, the result of the equals comparison can change if one (or both) are modified between method invocations. However, for immutable objects, the result must always be the same. The equals()
method should take into consideration whether the class implements immutable objects, and ensure that the consistency rule is not violated.
This rule states that no object is equal to null
. The contract calls for the equals()
method to return false
. The method must not throw an exception; that would be violating the contract. A check for this rule is necessary in the implementation. Typically, the reference value passed as argument is explicitly compared with the null
value:
if (argumentObj == null)
return false;
In many cases, it is preferable to use the instanceof
operator. It always returns false
if its left operand is null
:
if (!(argumentObj instanceof MyRefType))
return false;
This test has the added advantage that if the condition fails, the argument reference can be safely downcast.
Example 15.4 Implementing the equals()
Method
public class UsableVNO {
// Overrides equals(), but not hashCode().
private int release;
private int revision;
private int patch;
public UsableVNO(int release, int revision, int patch) {
this.release = release;
this.revision = revision;
this.patch = patch;
}
public String toString() {
return "(" + release + "." + revision + "." + patch
+ ")";
}
public boolean equals(Object obj) { // (1)
if (obj == this) // (2)
return true;
if (!(obj instanceof UsableVNO)) // (3)
return false;
UsableVNO vno = (UsableVNO) obj; // (4)
return vno.patch == this.patch && // (5)
vno.revision == this.revision &&
vno.release == this.release;
}
}
Example 15.4 shows an implementation of the equals()
method for version numbers. Next, we provide a checklist for implementing the equals()
method.
The method header is
public boolean equals(Object obj) // (1)
The signature of the method requires that the argument passed is of the type Object
. The following header will overload the method, not override it:
public boolean equals(MyRefType obj) // Overloaded.
The compiler will not complain. Calls to overloaded methods are resolved at compile time, depending on the type of the argument. Calls to overridden methods are resolved at runtime, depending on the type of the actual object referenced by the argument. Comparing the objects of the class MyRefType
that overloads the equals()
method for equivalence, can give inconsistent results:
MyRefType ref1 = new MyRefType();
MyRefType ref2 = new MyRefType();
Object ref3 = ref2;
boolean b1 = ref1.equals(ref2); // True. Calls equals() in MyRefType.
boolean b2 = ref1.equals(ref3); // Always false. Calls equals() in Object.
However, if the equals()
method is overridden correctly, only the overriding method in MyRefType
is called. A class can provide both implementations, but the equals()
methods must be consistent.
This is usually the first test performed in the equals()
method, avoiding further computation if the test is true
. The equals()
method in Example 15.4 does this test at (2).
The equals()
method in Example 15.4 checks the type of the argument object at (3), using the instanceof
operator:
if (!(obj instanceof UsableVNO)) // (3)
return false;
This code also does the null
comparison correctly, returning false
if the argument obj
has the value null
.
The instanceof
operator will also return true
if the argument obj
denotes a subclass object of the class UsableVNO
. If the class is final
, this issue does not arise—there are no subclass objects. The test at (3) can also be replaced by the following code in order to exclude all other objects, including subclass objects:
if ((obj == null) || (obj.getClass() != this.getClass())) // (3a)
return false;
The test in (3a) first performs the null
comparison explicitly. The expression (obj.getClass() != this.getClass())
determines whether the classes of the two objects have the same runtime object representing them. If this is the case, the objects are instances of the same class.
The argument is only cast after checking that the cast will be successful. The instanceof
operator ensures the validity of the cast, as done in Example 15.4. The argument is cast at (4) to allow for class-specific field comparisons:
UsableVNO vno = (UsableVNO) obj; // (4)
Equivalence comparison involves comparing certain fields from both objects to determine if their logical states match. For fields that are of primitive data types, their primitive values can be compared. Instances of the class UsableVNO
in Example 15.4 have fields of primitive data types only. Values of corresponding fields are compared to test for equality between two UsableVNO
objects:
return vno.patch == this.patch && // (5)
vno.revision == this.revision &&
vno.release == this.release;
If all field comparisons evaluate to true
, the equals()
method returns true
.
For fields that are references, the objects referenced by the references can be compared. For example, if the UsableVNO
class declares a field called productInfo
, which is a reference, the following code could be used:
(vno.productInfo == this.productInfo ||
(this.productInfo != null && this.productInfo.equals
(vno.productInfo)))
The expression vno.productInfo == this.productInfo
checks for the possibility that the two objects being compared have a common object referenced by both productInfo
references. In order to avoid a NullPointerException
being thrown, the equals()
method is not invoked if the this.productInfo
reference is null
.
Exact comparison of floating-point values should not be done directly on the values, but on the integer values obtained from their bit patterns (see static methods Float.floatToIntBits()
and Double.doubleToLongBits()
in the Java Standard Library). This technique eliminates certain anomalies in floating-point comparisons that involve a NaN value or a negative zero (see also the equals()
method in Float
and Double
classes).
Only fields that have significance for the equivalence relation should be considered. Derived fields, whose computation is dependent on other field values in the object, might be redundant to include, including only the derived fields may be prudent. Computing the equivalence relation should be deterministic, therefore, the equals()
method should not depend on unreliable resources, such as network access.
The order in which the comparisons of the significant fields are carried out can influence the performance of the equals comparison. Fields that are most likely to differ should be compared as early as possible in order to short-circuit the computation. In our example, patch numbers evolve faster than revision numbers, which, in turn, evolve faster than release numbers. This order is reflected in the return
statement at (5) in Example 15.4.
Above all, an implementation of the equals()
method must ensure that the equivalence relation is fulfilled.
Example 15.5 is a client that uses the class UsableVNO
from Example 15.4. This client runs the same tests as the client in Example 15.3. The difference is that the class UsableVNO
overrides the equals()
method.
Example 15.5 Implications of Overriding the equals()
Method
public class TestUsableVNO {
public static void main(String[] args) {
// Three individual version numbers.
UsableVNO latest = new UsableVNO(9,1,1); // (1)
UsableVNO inShops = new UsableVNO(9,1,1); // (2)
UsableVNO older = new UsableVNO(6,6,6); // (3)
// An array of version numbers.
UsableVNO[] versions = new UsableVNO[] { // (4)
new UsableVNO( 3,49, 1), new UsableVNO( 8,19,81),
new UsableVNO( 2,48,28), new UsableVNO(10,23,78),
new UsableVNO( 9, 1, 1)};
// An array with number of downloads.
Integer[] downloads = {245, 786, 54,1010, 123}; // (5)
TestCaseVNO.test(latest, inShops, older, versions, downloads); // (6)
}
}
Output from the program:
class UsableVNO
Test object reference and value equality:
latest: (9.1.1), inShops: (9.1.1), older: (6.6.6)
latest == inShops: false
latest.equals(inShops): true
latest == older: false
latest.equals(older): false
Array: [(3.49.1), (8.19.81), (2.48.28), (10.23.78), (9.1.1)]
Search key (9.1.1) found in array: true
List: [(3.49.1), (8.19.81), (2.48.28), (10.23.78), (9.1.1)]
Search key (9.1.1) contained in list: true
Map: {(9.1.1)=123, (2.48.28)=54, (8.19.81)=786, (3.49.1)=245, (10.23.78)=1010}
Hash code for keys in the map:
(3.49.1): 8451275
(8.19.81): 4669910
(2.48.28): 3374351
(10.23.78): 5737707
(9.1.1): 31771588
Search key (9.1.1) has hash code: 31393597
Map contains search key (9.1.1): false
Exception in thread "main" java.lang.
ClassCastException: UsableVNO cannot be cast
to java.lang.Comparable
...
at TestCaseVNO.test(TestCaseVNO.java:59)
at TestUsableVNO.main(TestUsableVNO.java:18)
The output from the program shows that object value equality is compared correctly. Object value equality is now based on identical states, as defined by the equals()
method.
The search for a UsableVNO
object in an array or a list of UsableVNO
objects is now successful, since the equals comparison is based on the states of the objects and not on their reference values.
However, searching in a map or creating sorted collections is still not feasible. For searching in a HashMap
, we have to look at the relationship between the equals()
and the hashCode()
methods. For creating sorted collections or sorted maps, we will provide an implementation of the compareTo()
method.
Hashing is an efficient technique for storing and retrieving data. A common hashing scheme uses an array where each element is a list of items. The array elements are called buckets. Operations in a hashing scheme involve computing an array index from an item. Converting an item to its array index is done by a hash function. The array index returned by the hash function is called the hash value of the item. The hash value identifies a particular bucket.
Storing an item involves the following steps:
1. Hashing the item to determine the bucket.
2. If the item does not match one already in the bucket, it is stored in the bucket.
Note that no duplicate items are stored. Retrieving an item is based on using a key. The key represents the identity of the item. Item retrieval is also a two-step process:
1. Hashing the key to determine the bucket.
2. If the key matches an item in the bucket, this item is retrieved from the bucket.
Different items can hash to the same bucket, meaning that the hash function returns the same hash value for these items. This condition is called a collision. The list maintained by a bucket contains the items that hash to the bucket.
The hash value only identifies the bucket. Finding an item in the bucket entails a search and requires an equality function to compare items. The items maintained in a hash-based storage scheme must, therefore, provide two essential functions: a hash function and an equality function.
The performance of a hashing scheme is largely affected by how well the hash function distributes a collection of items over the available buckets. A hash function should not be biased toward any particular hash values. An ideal hash function produces a uniform distribution of hash values for a collection of items across all possible hash values. Such a hash function is not an easy task to design. Fortunately, heuristics exist for constructing adequate hash functions.
A hash table contains key-value entries as items and the hashing is done on the keys only to provide efficient lookup of values. Matching a given key with a key in an entry, determines the value.
If objects of a class are to be maintained in hash-based collections and maps of the java.util
package (see Table 15.2), the class must provide appropriate implementations of the following methods from the Object
class:
• a hashCode()
method that produces hash values for the objects
• an equals()
method that tests objects for equality
As a general rule for implementing these methods, a class that overrides the equals()
method must override the hashCode()
method. Consequences of not doing so are illustrated by the class UsableVNO
in Example 15.4. Elements of this class are used as keys in Example 15.5. The output from the program shows that a map with the following entries is created:
Map: {(9.1.1)=123, (2.48.28)=54, (8.19.81)=786, (3.49.1)=245, (10.23.78)=1010}
The hashCode()
method from the Object
class is not overridden by the UsableVNO
class and is, therefore, used to compute the hash values of the key objects. This method returns the memory address of the object as the default hash value. The output from the program shows the hash values assigned by this method to the keys in the map:
Hash code for keys in the map:
(3.49.1): 8451275
(8.19.81): 4669910
(2.48.28): 3374351
(10.23.78): 5737707
(9.1.1): 31771588
The attempt to find the search key (9.1.1) in the map is unsuccessful:
Search key (9.1.1) has hash code: 31393597
Map contains search key (9.1.1): false
The hash values of two objects, which are equal according to the equals()
method of the class UsableVNO
, are not equal according to the hashCode()
method of the Object
class. Therefore, the key (9.1.1) of the entry (9.1.1)=123 in the map has a different hash value than the search key (9.1.1). These objects hash to different buckets. The lookup for the search key is done in one bucket and does not find the entry (9.1.1)=123, which is to be found in a completely different bucket. Just overriding the equals()
method is not enough. The class UsableVNO
violates the key tenet of the hashCode()
contract: equal objects must produce equal hash codes.
The general contract of the hashCode()
method stipulates:
• Consistency during execution: Multiple invocations of the hashCode()
method on an object must consistently return the same hash code during the execution of an application, provided the object is not modified to affect the result returned by the equals()
method. The hash code need not remain consistent across different executions of the application. This means that using a pseudorandom number generator to produce hash values is not a valid strategy.
• Object value equality implies hash value equality: If two objects are equal according to the equals()
method, then the hashCode()
method must produce the same hash code for these objects. This tenet ties in with the general contract of the equals()
method.
• Object value inequality places no restrictions on the hash value: If two objects are unequal according to the equals()
method, then the hashCode()
method need not produce distinct hash codes for these objects. It is strongly recommended that the hashCode()
method produce unequal hash codes for unequal objects.
Note that the hash contract does not imply that objects with equal hash codes are equal. Not producing unequal hash codes for unequal objects can have an adverse effect on performance, as unequal objects will hash to the same bucket.
In Example 15.6, the computation of the hash value in the hashCode()
method of the ReliableVNO
class embodies heuristics that can produce fairly reasonable hash functions. The hash value is computed according to the following formula:
hashValue = 11 * 313 + release * 312 + revision * 311 + patch
This can be verified by back substitution (see Section G.3, p. 1008). Each significant field is included in the computation. Only the fields that have bearing on the equals()
method are included. This ensures that objects that are equal according to the equals()
method, also have equal hash values according to the hashCode()
method.
Example 15.6 Implementing the hashCode()
Method
public class ReliableVNO {
// Overrides both equals() and hashCode().
private int release;
private int revision;
private int patch;
public ReliableVNO(int release, int revision, int patch) {
this.release = release;
this.revision = revision;
this.patch = patch;
}
public String toString() {
return "(" + release + "." + revision + "." + patch
+ ")";
}
public boolean equals(Object obj) { // (1)
if (obj == this) // (2)
return true;
if (!(obj instanceof ReliableVNO)) // (3)
return false;
ReliableVNO vno = (ReliableVNO) obj; // (4)
return vno.patch == this.patch && // (5)
vno.revision == this.revision &&
vno.release == this.release;
}
public int hashCode() { // (6)
int hashValue = 11;
hashValue = 31 * hashValue + release;
hashValue = 31 * hashValue + revision;
hashValue = 31 * hashValue + patch;
return hashValue;
}
}
The basic idea is to compute an int
hash value sfVal
for each significant field sf
, and include an assignment of the form shown at (1) in the computation below:
public int hashCode() {
int sfVal;
int hashValue = 11;
...
sfVal = ... // Compute hash value for
each significant field sf.
hashValue = 31 * hashValue + sfVal; // (1)
...
return hashValue;
}
This setup ensures that the result from incorporating a field value is used to calculate the contribution from the next field value.
Calculating the hash value sfVal
for a significant field sf
depends on the type of the field:
• Field sf
is boolean
:
sfVal = sf ? 0 : 1;
• Field sf
is byte, char, short, or int
:
sfVal = (int)sf;
• Field sf
is long
:
sfVal = (int) (sf ^ (sf >>> 32));
• Field sf
is float
:
sfVal = Float.floatToInt(sf);
• Field sf
is double
:
long sfValTemp = Double.doubleToLong(sf);
sfVal = (int) (sfValTemp ^ (sfValTemp >>> 32));
• Field sf
is a reference that denotes an object. Typically, the hashCode()
method is invoked recursively if the equals()
method is invoked recursively:
sfVal = (sf == null ? 0 : sf.hashCode());
• Field sf
is an array. Contribution from each element is calculated similarly to a field.
The order in which the fields are incorporated into the hash code computation will influence the hash value. Fields whose values are derived from other fields can be excluded. There is no point in feeding the hash function with redundant information, since this is unlikely to improve the value distribution. Fields that are not significant for the equals()
method must be excluded; otherwise, the hashCode()
method might end up contradicting the equals()
method. As with the equals()
method, data from unreliable resources (e.g., network access) should not be used, and inclusion of transient fields should be avoided.
A legal or correct hash function does not necessarily mean it is appropriate or efficient. The classical example of a legal but inefficient hash function is
public int hashCode() {
return 1949;
}
All objects using this method are assigned to the same bucket. The hash table is then no better than a list. For the sake of efficiency, a hash function should strive to produce unequal hash codes for unequal objects.
For numeric wrapper types, the hashCode()
implementation returns an int
representation of the primitive value, converting the primitive value to an int
, if necessary. The Boolean
objects for the boolean
literals true
and false
have specific hash values, which are returned by the hashCode()
method.
The hashCode()
method of the String
class returns a hash value that is the value of a polynomial whose variable has the value 31, the coefficients are the characters in the string, and the degree is the string length minus one. For example, the hash value of the string "abc"
is computed as follows:
hashValue = 'a' * 312 + 'b' * 311 + 'c' * 310 = 97 * 31 *
31 + 98 * 31 + 99 = 96354
For immutable objects, the hash code can be cached, that is, calculated once and returned whenever the hashCode()
method is called.
The client in Example 15.7 creates objects of the class ReliableVNO
in Example 15.6 and tests them by calling the test()
method of class TestCaseVNO
in Example 15.1. Output from the program shows that the key (9.1.1) of the entry (9.1.1)= 123 in the map has the same hash value as the search key (9.1.1). The search is successful. These objects hash to the same bucket. Therefore, the search for the key takes place in the right bucket. It finds the entry (9.1.1)= 123 using the equals()
method by successfully checking for equality between the search key (9.1.1) and the key (9.1.1) of this entry. However, we still cannot use objects of the class ReliableVNO
in sorted sets and maps.
Example 15.7 Implications of Overriding the hashCode()
Method
public class TestReliableVNO {
public static void main(String[] args) {
// Three individual version numbers.
ReliableVNO latest = new ReliableVNO(9,1,1); // (1)
ReliableVNO inShops = new ReliableVNO(9,1,1); // (2)
ReliableVNO older = new ReliableVNO(6,6,6); // (3)
// An array of version numbers.
ReliableVNO[] versions = new ReliableVNO[] { // (4)
new ReliableVNO( 3,49, 1), new ReliableVNO( 8,19,81),
new ReliableVNO( 2,48,28), new ReliableVNO(10,23,78),
new ReliableVNO( 9, 1, 1)};
// An array with number of downloads.
Integer[] downloads = {245, 786, 54,1010, 123}; // (5)
TestCaseVNO.test(latest, inShops, older, versions, downloads); // (6)
}
}
Output from the program:
class ReliableVNO
...
Map: {(9.1.1)=123, (2.48.28)=54, (8.19.81)=786, (3.49.1)=245, (10.23.78)=1010}
Hash code for keys in the map:
(3.49.1): 332104
(8.19.81): 336059
(2.48.28): 331139
(10.23.78): 338102
(9.1.1): 336382
Search key (9.1.1) has hash code: 336382
Map contains search key (9.1.1): true
Exception in thread "main" java.lang.
ClassCastException: ReliableVNO cannot be
cast to java.lang.Comparable
...
The natural ordering of objects is specified by implementing the generic Comparable
interface. A total ordering of objects can be specified by implementing a comparator that implements the generic Comparator
interface.
We will look at the two generic interfaces Comparable
and Comparator
in turn.
The general contract for the Comparable
interface is defined by its only method:
int compareTo(E o)
It returns a negative integer, zero, or a positive integer if the current object is less than, equal to, or greater than the specified object, based on the natural ordering. It throws a ClassCastException
if the reference value passed in the argument cannot be compared to the current object.
Many of the standard classes in the Java API, such as the primitive wrapper classes, String
, Date
, and File
, implement the Comparable
interface. Objects implementing this interface can be used as
• elements in a sorted set
• keys in a sorted map
• elements in lists that are sorted manually using the Collections.sort()
method
The natural ordering for String
objects (and Character
objects) is lexicographical ordering, i.e., their comparison is based on the Unicode value of each character in the strings (see Section 10.4, p. 445). Objects of the String
and Character
classes will be lexicographically maintained as elements in a sorted set, or as keys in a sorted map that uses their natural ordering.
The natural ordering for objects of a numerical wrapper class is in ascending order of the values of the corresponding numerical primitive type (see Section 10.3, p. 428). As elements in a sorted set or as keys in a sorted map that uses their natural ordering, the objects will be maintained in ascending order.
According to the natural ordering for objects of the Boolean
class, a Boolean
object representing the value false
is less than a Boolean
object representing the value true
.
An implementation of the compareTo()
method for the objects of a class should meet the following criteria:
• For any two objects of the class, if the first object is less than, equal to, or greater than the second object, then the second object must be greater than, equal to, or less than the first object, respectively, i.e., the comparison is anti-symmetric.
• All three comparison relations (less than, equal to, greater than) embodied in the compareTo()
method must be transitive. For example, if obj1.compareTo(obj2) > 0
and obj2.compareTo(obj3) > 0
, then obj1.compareTo(obj3) > 0
.
• For any two objects of the class, which compare as equal, the compareTo()
method must return the same result if these two objects are compared with any other object, i.e., the comparison is congruent.
• The compareTo()
method must be consistent with equals, that is, (obj1.compareTo(obj2) == 0) == (obj1.equals(obj2))
. This is recommended if the objects will be maintained in sorted sets or sorted maps.
The magnitude of non-zero values returned by the method is immaterial; the sign indicates the result of the comparison. The general contract of the compareTo()
method augments the general contract of the equals()
method, providing a natural ordering of the compared objects. The equality test of the compareTo()
method has the same provisions as that of the equals()
method.
Implementing the compareTo()
method is not much different from implementing the equals()
method. In fact, given that the functionality of the equals()
method is a subset of the functionality of the compareTo()
method, the equals()
implementation can call the compareTo()
method. This guarantees that the two methods are always consistent with one another.
public boolean equals(Object other) {
// ...
return compareTo(other) == 0;
}
Example 15.8 Implementing the compareTo()
Method of the Comparable
Interface
public final class VersionNumber implements Comparable
<VersionNumber> {
private final int release;
private final int revision;
private final int patch;
public VersionNumber(int release, int revision, int patch) {
this.release = release;
this.revision = revision;
this.patch = patch;
}
public String toString() {
return "(" + release + "." + revision + "." + patch + ")";
}
public boolean equals(Object obj) { // (1)
if (obj == this) // (2)
return true;
if (!(obj instanceof VersionNumber)) // (3)
return false;
VersionNumber vno = (VersionNumber) obj; // (4)
return vno.patch == this.patch && // (5)
vno.revision == this.revision &&
vno.release == this.release;
}
public int hashCode() { // (6)
int hashValue = 11;
hashValue = 31 * hashValue + this.release;
hashValue = 31 * hashValue + this.revision;
hashValue = 31 * hashValue + this.patch;
return hashValue;
}
public int compareTo(VersionNumber vno) { // (7)
// Compare the release numbers. (8)
if (this.release != vno.release)
return new Integer(release).compareTo(vno.release);
// Release numbers are equal, (9)
// must compare revision numbers.
if (this.revision != vno.revision)
return new Integer(revision).compareTo(vno.revision);
// Release and revision numbers are equal, (10)
// patch numbers determine the ordering.
return new Integer(patch).compareTo(vno.patch);
}
}
A compareTo()
method is seldom implemented to interoperate with objects of other classes. For example, this is the case for primitive wrapper classes and the String
class. The calls to the compareTo()
method in the three assert
statements below all result in a compile time error.
Integer iRef = 10;
Double dRef = 3.14;
String str = "ten";
StringBuilder sb = new StringBuilder("ten");
assert iRef.compareTo(str) == 0; // compareTo(Integer) not applicable to
// arguments (String).
assert dRef.compareTo(iRef) > 0; // compareTo(Double) not applicable to
// arguments (Integer).
assert sb.compareTo(str) == 0; // No such method in StringBuilder.
An implementation of the compareTo()
method for version numbers is shown in Example 15.8. Note the specification of the implements
clause in the class header. By parameterizing the Comparable
interface with the VersionNumber
type, the class declaration explicitly excludes comparison with objects of other types. Only VersionNumber
s can be compared.
public final class VersionNumber implements Comparable
<VersionNumber> {
...
public int compareTo(VersionNumber vno) { // (7)
...
}
...
}
The signature of the compareTo()
method is compareTo(VersionNumber)
. In order to maintain backward compatibility with non-generic code, the compiler inserts the following bridge method with the signature compareTo(Object)
into the class.
public int compareTo(Object obj) { // NOT A GOOD IDEA TO RELY ON THIS METHOD!
return this.compareTo((VersionNumber) obj);
}
In an implementation of the compareTo()
method, the fields are compared with the most significant field first and the least significant field last. In the case of the version numbers, the release numbers are compared first, followed by the revision numbers, with the patch numbers being compared last. Note that the next least significant fields are only compared if the comparison of the previous higher significant fields yielded equality. Inequality between corresponding significant fields short-circuits the computation. If all significant fields are equal, a zero will be returned. This approach is shown in the implementation of the compareTo()
method at (7) through (10) in Example 15.8.
Comparison of integer values in fields can be optimized. In the code for comparing the release numbers at (8) in Example 15.8, we have used the compareTo()
method implemented by the Integer
class and relied on autoboxing of the vno.release
value:
if (this.release != vno.release)
return new Integer(release).compareTo(vno.release);
// Next field comparison
The code above can be replaced by the following code for doing the comparison, which relies on the difference between int
values:
int releaseDiff = release vno.release;
if (releaseDiff != 0)
return releaseDiff;
// Next field comparison
However, this code can break if the difference is a value not in the range of the int
type.
Significant fields with non-boolean
primitive values are normally compared using the relational operators <
and >
. For comparing significant fields denoting constituent objects, the main options are to either invoke the compareTo()
method on them or use a comparator.
Example 15.9 is a client that uses the class VersionNumber
from Example 15.8. This client also runs the same tests as the clients in Example 15.7, Example 15.5, and Example 15.3. What is different about this implementation is that the class VersionNumber
overrides both the equals()
and hashCode()
methods, and implements the compareTo()
method. In addition, the compareTo()
method is consistent with equals. Following general class design principles, the class has been declared final
so that it cannot be extended. We have already seen the program output in Example 15.1 confirming that all the tests on objects of the VersionNumber
class run as expected.
Example 15.9 Implications of Implementing the compareTo()
Method
public class TestVersionNumber {
public static void main(String[] args) {
// Three individual version numbers.
VersionNumber latest = new VersionNumber(9,1,1); // (1)
VersionNumber inShops = new VersionNumber(9,1,1); // (2)
VersionNumber older = new VersionNumber(6,6,6); // (3)
// An array of version numbers.
VersionNumber[] versions = new VersionNumber[] { // (4)
new VersionNumber( 3,49, 1), new VersionNumber( 8,19,81),
new VersionNumber( 2,48,28), new VersionNumber(10,23,78),
new VersionNumber( 9, 1, 1)};
// An array with number of downloads.
Integer[] downloads = {245, 786, 54,1010, 123}; // (5)
TestCaseVNO.test(latest, inShops, older, versions, downloads); // (6)
}
}
Unlike previous attempts, the following code from Example 15.9 demonstrates that VersionNumber
objects can now be maintained in sorted sets and maps:
out.println("Sorted set:
" + (new TreeSet<N>(vnoList))); // (22)
out.println("Sorted map:
" +
(new TreeMap<N, Integer>(versionStatistics))); // (23)
The output from executing this code shows that the elements in the set and the map are sorted in the natural ordering for version numbers:
Sorted list:
[(2.48.28), (3.49.1), (8.19.81), (9.1.1), (10.23.78)]
Sorted map:
{(2.48.28)=54, (3.49.1)=245, (8.19.81)=786, (9.1.1)=123, (10.23.78)=1010}
By default, the class TreeSet
relies on its elements to implement the compareTo()
method. The output from the program in Example 15.9 shows that the TreeSet
, created at (22), maintains its elements sorted in the natural ordering dictated by the compareTo()
method. Analogously, the output from the program in Example 15.9 shows that the TreeMap
, created at (23), maintains its entries sorted on the keys, which are in the natural ordering dictated by the compareTo()
method.
We can run generic algorithms on collections of version numbers. Utility methods provided by the Collections
and Arrays
classes in the java.util
package are discussed in Section 15.11, “15.11 Working with Collections.” The following code sorts the elements in the list that was created at (14) in Example 15.1, and referenced by the reference vnoList
:
out.println("List before sorting: " + vnoList);
Collections.sort(vnoList, null); // (24)
out.println("List after sorting: " + vnoList);
Since the comparator value is null
, natural ordering is used. The output from executing this code shows that the elements in the list are indeed sorted in ascending order:
List before sorting: [(3.49.1), (8.19.81), (2.48.28), (10.23.78),
(9.1.1)]
List after sorting: [(2.48.28), (3.49.1), (8.19.81), (9.1.1),
(10.23.78)]
A binary search can be run on this sorted list to find the index of the version number (9.1.1), referenced by the reference searchKey
in Example 15.9:
int resultIndex = Collections.binarySearch(vnoList, searchKey, null);// (25)
out.println("Binary search in list found key " + searchKey +
" at index: " + resultIndex);
Since the comparator value is null
, natural ordering is assumed for the elements in the list. Executing the code prints the correct index of the search key in the sorted list:
Binary search in list found key (9.1.1) at index: 3
Specifying the comparator with the null
value in the test()
method in Example 15.9 was necessary to avoid compile time errors. We can readily use VersionNumber
objects with the overloaded sort()
and binarySearch()
methods in the Collections
class whose signature explicitly requires that the elements implement the Comparable
interface:
VersionNumber[] versions = new VersionNumber[] {
new VersionNumber( 3,49, 1), new VersionNumber( 8,19,81),
new VersionNumber( 2,48,28), new VersionNumber(10,23,78),
new VersionNumber( 9, 1, 1)};
List<VersionNumber> vnList = Arrays.asList(versions);
Collections.sort(vnList); // [(2.48.28), (3.49.1), (8.19.81), (9.1.1),
(10.23.78)]
int index1 = Collections.binarySearch(vnList, new VersionNumber(9, 1, 1)); // 3
Precise control of ordering can be achieved by creating a customized comparator that imposes a specific total ordering on the elements. All comparators implement the Comparator
interface, which has the following single method:
int compare(E o1, E o2)
The compare()
method returns a negative integer, zero, or a positive integer if the first object is less than, equal to, or greater than the second object, according to the total ordering, i.e., it’s contract is equivalent to that of the compareTo()
method of the Comparable
interface. Since this method tests for equality, it is strongly recommended that its implementation does not contradict the semantics of the equals()
method.
An alternative ordering to the default natural ordering can be specified by passing a Comparator
to the constructor when the sorted set or map is created. The Collections
and Arrays
classes provide utility methods for sorting, which also take a Comparator
(see subsection Ordering Elements in Lists, p. 838, and subsection Sorting Arrays, p. 842).
Example 15.10 demonstrates the use of different comparators for strings. The program creates an empty sorted set using the TreeSet
class. Each program argument is added to the sorted set in the loop at (2). A textual representation of the sorted set is then printed at (3). The output shows the sort ordering in which the elements are maintained in the set. The set is traversed according to the sort ordering.
The String
class implements the Comparable
interface, providing an implementation of the compareTo()
method. The compareTo()
method defines the natural ordering for strings, which is lexicographical. The natural ordering is used to maintain the program arguments sorted lexicographically when the sorted set at (1a) is used. If we wish to maintain the strings in a different ordering, we need to provide a customized comparator.
The String
class provides a static field (CASE_INSENSITIVE_ORDER
) that denotes a comparator object with a compare()
method that ignores the case when comparing strings lexicographically. This particular total ordering is used to maintain the program arguments sorted when the sorted set at (1b) is used. The comparator is passed as argument to the set constructor. The output shows how the elements are maintained sorted in the set by this total ordering, which is a case-insensitive ordering.
We can create a string comparator that enforces rhyming ordering on the strings. In rhyming ordering, two strings are compared by examining their corresponding characters at each position in the two strings, starting with the characters in the last position. First the characters in the last position are compared, then those in the last but one position, and so on. For example, given the two strings "report"
and "court"
, the last two characters in both the strings are the same. Continuing backward in the two strings, the character 'o'
in the first string is less than the character 'u'
in the second string. According to the rhyming ordering, the string "report"
is less than the string "court"
.
Comparing two strings according to the rhyming ordering is equivalent to reversing the strings and comparing the reversed strings lexicographically. If we reverse the two strings, "report"
and "court"
, the reversed string "troper"
is lexicographically less than the reversed string "truoc"
.
A rhyming ordering comparator is implemented by the RhymingStringComparator
class in Example 15.10. The compare()
method at (4) first creates reversed versions of the strings passed as arguments. A reversed version of a string is created using a string builder, which is first reversed and then converted back to a string, as shown at (5). The compare()
method then calls the compareTo()
method at (6) to compare the reversed strings, as the lexicographical ordering for the reversed strings is equivalent to the rhyming ordering for the original strings. This particular total ordering is used to maintain the program arguments sorted when the sorted set at (1c) is used. The comparator is again passed as argument to the set constructor. The output shows how the elements are maintained sorted in the set by this total ordering, which is rhyming ordering.
Example 15.10 Natural Ordering and Total Ordering
import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;
public class ComparatorUsage {
public static void main(String[] args) {
// Choice of comparator.
// Set<String> strSet = new TreeSet<String>(); // (1a)
// Set<String> strSet =
// new TreeSet<String>(String.CASE_INSENSITIVE_ORDER); // (1b)
Set<String> strSet =
new TreeSet<String>(new RhymingStringComparator()); // (1c)
// Add each command line argument to the set.
for (String argument : args) { // (2)
strSet.add(argument);
}
System.out.println(strSet); // (3)
}
}
class RhymingStringComparator implements Comparator
<String> {
public int compare(String obj1, String obj2) { // (4)
// (5) Create reversed versions of the strings:
String reverseStr1 = new StringBuilder(obj1).reverse().toString();
String reverseStr2 = new StringBuilder(obj2).reverse().toString();
// Compare the reversed strings lexicographically.
return reverseStr1.compareTo(reverseStr2); // (6)
}
}
The program is run with the following program arguments on the command line:
>java ComparatorUsage court Stuart report Resort
assort support transport distort
Output from the program using the natural ordering (1a):
[Resort, Stuart, assort, court, distort, report,
support, transport]
Output from the program using the case insensitive ordering (1b):
[assort, court, distort, report, Resort, Stuart,
support, transport]
Output from the program using the rhyming ordering (1c):
[Stuart, report, support, transport, Resort, assort,
distort, court]
Example 15.11 illustrates using a comparator that orders version numbers (Example 15.8) according to their reverse natural ordering. Such a comparator is implemented as an anonymous class by the method reverseComparatorVNO()
at (1). The comparator leverages on the compareTo()
method implemented by the VersionNumber
class.
A list of version numbers is created at (3), that is backed by the array created at (2). This list is sorted using the comparator at (4). A binary search is done in this list at (5). We have used the same comparator for the search as we did for the sorting in order to obtain predictable results.
Example 15.11 Using a Comparator for Version Numbers
import static java.lang.System.out;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class UsingVersionNumberComparator {
/** Comparator for reverse natural ordering of natural
numbers. */
public static Comparator<VersionNumber>
reverseComparatorVNO() { // (1)
return new Comparator<VersionNumber>() {
public int compare(VersionNumber vno1, VersionNumber vno2) {
return vno2.compareTo(vno1); // Comparing vno2 with vno1.
}
};
}
public static void main(String[] args) {
VersionNumber[] versions = new VersionNumber[] { // (2)
new VersionNumber(3, 49, 1), new VersionNumber(8, 19, 81),
new VersionNumber(2, 48, 28), new VersionNumber(10, 23, 78),
new VersionNumber(9, 1, 1) };
List<VersionNumber> vnList = Arrays.asList(versions); // (3)
out.println("List before sorting:
" + vnList);
Collections.sort(vnList, reverseComparatorVNO()); // (4)
out.println("List after sorting according to " +
"reverse natural ordering:
" + vnList);
VersionNumber searchKey = new VersionNumber(9, 1, 1);
int resultIndex = Collections.binarySearch(vnList, searchKey,
reverseComparatorVNO()); // (5)
out.println("Binary search in list using reverse natural ordering" +
" found key " + searchKey + " at index:
" + resultIndex);
}
}
Program output:
List before sorting:
[(3.49.1), (8.19.81), (2.48.28), (10.23.78), (9.1.1)]
List after sorting according to reverse natural ordering:
[(10.23.78), (9.1.1), (8.19.81), (3.49.1), (2.48.28)]
Binary search in list using reverse natural ordering found
key (9.1.1) at index: 1
15.1 Which statements about the hashCode()
and equals()
methods are true?
Select the two correct answers.
(a) Two objects that are different according to the equals()
method, must have different hash values.
(b) Two objects that are equal according to the equals()
method, must have the same hash value.
(c) Two objects that have the same hash value, must be equal according to the equals()
method.
(d) Two objects that have different hash values, must be unequal according to the equals()
method.
15.2 Given that the objects referenced by the parameters override the equals()
and the hashCode()
methods appropriately, which return values are possible from the following method?
String func(Object x, Object y) {
return (x == y) + " " + x.equals(y) + " " + (x.hashCode() == y.hashCode());
}
Select the four correct answers.
(a) "false false false"
(b) "false false true"
(c) "false true false"
(d) "false true true"
(e) "true false false"
(f) "true false true"
(g) "true true false"
(h) "true true true"
15.3 Which code, when inserted at (1), in the equalsImpl()
method will provide a correct implementation of the equals()
method?
public class Pair {
int a, b;
public Pair(int a, int b) {
this.a = a;
this.b = b;
}
public boolean equals(Object o) {
return (this == o) || (o instanceof Pair) && equalsImpl((Pair) o);
}
private boolean equalsImpl(Pair o) {
// (1) INSERT CODE HERE ...
}
}
Select the three correct answers.
(a) return a == o.a || b == o.b;
(b) return false;
(c) return a >= o.a;
(d) return a == o.a;
(e) return a == o.a && b == o.b;
15.4 Which code, when inserted at (1), will provide a correct implementation of the hashCode()
method in the following program?
import java.util.*;
public class Measurement {
int count;
int accumulated;
public Measurement() {}
public void record(int v) {
count++;
accumulated += v;
}
public int average() {
return accumulated/count;
}
public boolean equals(Object other) {
if (this == other)
return true;
if (!(other instanceof Measurement))
return false;
Measurement o = (Measurement) other;
if (count != 0 && o.count != 0)
return average() == o.average();
return count == o.count;
}
public int hashCode() {
// (1) INSERT CODE HERE ...
}
}
Select the two correct answers.
(a) return 31337;
(b) return accumulated / count;
(c) return (count << 16) ^ accumulated;
(d) return ~accumulated;
(e) return count == 0 ? 0 : average();
15.5 What will be the result of compiling and running the following program?
import java.util.Comparator;
class Person implements Comparable<Person> {
String name;
int age;
Person(String name, int age) { this.name = name; this.age = age; }
public int compareTo(Person p2) {
Comparator<String> strCmp = Person.cmp();
int status = strCmp.compare(this.name, p2.name);
if (status == 0) {
Comparator<Integer> intCmp = Person.cmp();
status = intCmp.compare(this.age, p2.age);
}
return status;
}
public static <E extends Comparable<E>> Comparator<E> cmp() {
return new Comparator<E>() {
public int compare(E s1, E s2) { return s2.compareTo(s1); }
};
}
public static void main(String[] args) {
Person p1 = new Person("Tom", 20);
Person p2 = new Person("Dick", 30);
Person p3 = new Person("Tom", 40);
System.out.println((p1.compareTo(p2) < 0) + " " + (p1.compareTo(p3) < 0));
}
}
Select the one correct answer.
(a) The program will fail to compile.
(b) The program will compile but throw an exception when run.
(c) The program will compile and print true false
, when run.
(d) The program will compile and print true true
, when run.
(e) The program will compile and print false false
, when run.
(f) The program will compile and print false true
, when run.
A collection allows a group of objects to be treated as a single unit. Objects can be stored, retrieved, and manipulated as elements of a collection. Arrays are an example of one kind of collection.
Program design often requires the handling of collections of objects. The Java Collections Framework provides a set of standard utility classes for managing various kinds of collections. The core framework is provided in the java.util
package and comprises three main parts:
• The core interfaces that allow collections to be manipulated independently of their implementation (see Figure 15.1 and Table 15.1). These generic interfaces define the common functionality exhibited by collections and facilitate data exchange between collections.
• A set of implementations (i.e., concrete classes, listed in Table 15.1) that are specific implementations of the core interfaces, providing data structures that a program can readily use.
• An assortment of static utility methods found in the Collections
and Arrays
classes that can be used to perform various operations on collections and arrays, such as sorting and searching, or creating customized collections (see Section 15.11, “15.11 Working with Collections”).
The generic Collection
interface is a generalized interface for maintaining collections and is the root of the interface inheritance hierarchy for collections shown in Figure 15.1a. These subinterfaces are summarized in Table 15.1. The Collection
interface extends the Iterable
interface that specifies an iterator to sequentially access the elements of an Iterable
object (see subsection Iterators, p. 785).
The elements in a Set
must be unique, that is, no two elements in the set can be equal. The order of elements in a List
is positional, and individual elements can be accessed according to their position in the list.
Queues and deques, represented respectively by the Queue
and the Deque
interfaces, define collections whose elements can be processed according to various strategies.
As can be seen from Figure 15.1b, the Map
interface does not extend the Collection
interface because conceptually, a map is not a collection. A map does not contain elements. It contains mappings (also called entries) from a set of key objects to a set of value objects. A key can, at most, be associated with one value, i.e., it must be unique. As the name implies, the SortedMap
interface extends the Map
interface to maintain its mappings sorted in key order. It is superseded by the NavigableMap
interface which should be the preferred choice in new code.
The java.util
package provides implementations of a selection of well-known abstract data types, based on the core interfaces. Figures 15.2 and 15.3 show the inheritance relationship between the core interfaces and the corresponding implementations. None of the concrete implementations inherit directly from the Collection
interface. The abstract classes that provide the basis on which concrete classes are implemented, are not shown in Figures 15.2 and 15.3.
By convention, each of the collection implementation classes provides a constructor for creating a collection based on the elements of another Collection
object passed as argument. This allows the implementation of a collection to be changed by merely passing the collection to the constructor of the desired implementation. This interchangeability is also true between Map
implementations. But collections and maps are not interchangeable. Note that a collection (or a map) only stores reference values of objects, and not the actual objects.
The collections framework is interface-based, meaning that collections are manipulated according to their interface types, rather than by the implementation types. By using these interfaces wherever collections of objects are used, various implementations can be used interchangeably.
All the concrete classes shown in Figures 15.2 and 15.3 implement the Serializable
and the Cloneable
interfaces; therefore, the objects of these classes can be serialized and also cloned.
A summary of collection and map implementations is given in Table 15.2. The contents of this table will be the focus as each core interface and its corresponding implementations are discussed in the subsequent sections.
From Table 15.2, we see that elements in a LinkedHashSet
are ordered, in a TreeSet
they are sorted, and in a HashSet
they have no order (that is, are unordered). Sorting implies ordering the elements in a collection according to some ranking criteria, usually based on the values of the elements. However, elements is an ArrayList
are maintained in the order they are inserted in the list, known as the insertion order. The elements in such a list are thus ordered, but they are not sorted, as it is not the values of the elements that determine their ranking in the list. Thus, ordering does not necessarily imply sorting. In a HashSet
, the elements are unordered. No ranking of elements is implied in such a set. Whether a collection is sorted, ordered or unordered also has implications when traversing the collection (see subsection Iterators, p. 785).
The collection and map implementations discussed in this chapter, except for Vector
and Hashtable
, are not thread-safe, that is, their integrity can be jeopardized by concurrent access. The Java Collections Framework provides a plethora of collections and maps for use in single-threaded and concurrent applications; much more than what is covered in this book.
The Collection
interface specifies the contract that all collections should implement. Some of the operations in the interface are optional, meaning that a collection may choose to provide a stub implementation of such an operation that throws an UnsupportedOperationException
when invoked. The implementations of collections from the java.util
package support all the optional operations in the Collection
interface (see Figure 15.2 and Table 15.2).
Many of the methods return a boolean
value to indicate whether the collection was modified as a result of the operation.
The basic operations are used to query a collection about its contents and allow elements to be added to and removed from a collection. Many examples in this chapter make use of these operations.
int size()
boolean isEmpty()
boolean contains(Object element)
boolean add(E element)
Optionalboolean remove(Object element)
Optional
The add()
and remove()
methods return true
if the collection was modified as a result of the operation.
By returning the value false
, the add()
method indicates that the collection excludes duplicates and that the collection already contains an object equal to the argument object.
The contains()
method checks for membership of the argument object in the collection, using object value equality.
Note that we can only add an object of a specific type (E
). However, a collection allows us to determine whether it has an element equal to any arbitrary object, or remove an element that is equal to any arbitrary object.
These operations perform on a collection as a single unit. See Section 15.4 for an example.
boolean containsAll(Collection<?> c)
boolean addAll(Collection<? extends E> c)
Optionalboolean removeAll(Collection<?> c)
Optionalboolean retainAll(Collection<?> c)
Optionalvoid clear()
Optional
These bulk operations can be used to perform the equivalent of set logic on arbitrary collections (i.e., also lists and not just sets). The containsAll()
method returns true
if all elements of the specified collection are also contained in the current collection.
The addAll()
, removeAll()
, and retainAll()
methods are destructive in the sense that the collection on which they are invoked can be modified. The operations performed by these methods are visualized by Venn diagrams in Figure 15.4.
The addAll()
requires that the element type of the other collection is the same as, or a subtype of, the element type of the current collection. The removeAll()
and retainAll()
operations can be performed with collections of any type.
A collection provides an iterator which allows sequential access to the elements of a collection. An iterator can be obtained by calling the following method of the Collection
interface:
The generic interface Iterator
is defined as follows:
boolean hasNext()
Returns true
if the underlying collection still has elements left to return. A future call to the next()
method will return the next element from the collection.
E next()
Moves the iterator to the next element in the underlying collection, and returns the current element. If there are no more elements left to return, it throws a NoSuchElementException
.
void remove()
Optional
Removes the element that was returned by the last call to the next()
method from the underlying collection. Invoking this method results in an IllegalStateException
if the next()
method has not yet been called or when the remove()
method has already been called after the last call to the next()
method. This method is optional for an iterator, i.e., it throws an UnsupportedOperationException
if the remove operation is not supported.
After obtaining the iterator for a collection, the methods provided by the Iterator
interface can be used to systematically traverse the elements of the underlying collection one by one. Example 15.12 illustrates the use of an iterator.
Example 15.12 Using an Iterator
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
public class IteratorUsage {
public static void main(String[] args) {
// (1) Create a list of Integers.
Collection<Integer> intList = new ArrayList<Integer>();
int[] values = { 9, 11, -4, 1, 13, 99, 1, 0 };
for (int i : values) {
intList.add(i);
}
System.out.println("Before: " + intList); // (2)
Iterator<Integer> iterator = intList.iterator(); // (3) Get an iterator.
while (iterator.hasNext()) { // (4) Loop
int value = iterator.next(); // (5) The next element
if (value < 1 || value > 10) // (6) Remove the element if
iterator.remove(); // its value is not
// between 1 and 10.
}
System.out.println("After: " + intList); // (7)
}
}
Output from the program:
Before: [9, 11, -4, 1, 13, 99, 1, 0]
After: [9, 1, 1]
Example 15.12 creates a list of integers and then removes from the list all integers that are not between 1 and 10, inclusive. The example uses an ArrayList
for the list of integers. First an empty ArrayList
is created and elements of an int
array are added to the list using a for(:)
loop.
In Example 15.12, an iterator is obtained at (3) and used in the loop at (4) to traverse all the elements in the integer list. At (5) the current element is retrieved by the iterator from the list. No casts are necessary, as the compiler guarantees that the iterator will return an Integer
object from the underlying list. Its value is automatically unboxed and assigned to an int
variable. The call to the remove()
method removes the current element from the underlying list if the criteria in the if
statement at (6) is satisfied.
Note that the methods are invoked on the iterator, not the underlying collection. The three methods of the iterator should be used in step inside a loop, as shown in Example 15.12.
In Example 15.12, we used an iterator in a while
loop at (4) for traversing the collection. It is quite common to use an iterator in a for(;;)
loop for this purpose, where the iterator is obtained in the initialization part, and the increment part is left empty:
for (Iterator<Integer> iterator = intList.iterator(); iterator.hasNext(); /* */) {
int value = iterator.next();
if (value < 1 || value > 10)
iterator.remove();
}
The majority of the iterators provided in the java.util
package are said to be failfast. When an iterator has already been obtained, structurally modifying the underlying collection by other means will invalidate the iterator. Subsequent use of this iterator will throw a ConcurrentModificationException
, as the iterator checks to see if the collection has been structurally modified every time it accesses the collection. The remove()
method of an iterator is the only recommended way to delete elements from the underlying collection during traversal with an iterator.
The order in which the iterator will return the elements from an underlying collection depends on the traversal order supported by the collection. For example, an iterator for a list will traverse the elements in the sequential order they have in the list, whereas the traversal order for the elements in an ordinary set is not predetermined. An iterator for a sorted collection will make the elements available in a given sorted order. Traversal order will be discussed together with the individual concrete classes.
The concrete collection classes override the toString()
method to provide a textual representation of their contents. The standard textual representation generated by the toString()
method for a collection is
[element1, element2 , ..., elementn]
where each elementi is the textual representation generated by the toString()
method of the individual elements in the collection. In Example 15.12 the toString()
method of the collection class is used implicitly at (2) and at (7) to generate a textual representation for the collection.
In Section 6.3, p. 220, we showed how to traverse an array using a for(:)
loop. A for(:)
loop can also be used to traverse any data structure that implements the java.lang.Iterable
interface:
interface Iterable<E> {
Iterator<E> iterator();
}
The iterator()
method returns an iterator that implements the Iterator
interface we have seen earlier in this subsection. The Iterable
interface implies that if a collection implements an iterator, we can traverse the collection with a for(:)
loop.
In the loop construct
for (
type variable :
expression)
statement
the value of expression can be a reference value that refers to a collection that implements the Iterable
interface. From Figure 15.2 we see that the Collection
interface extends the Iterable
interface, therefore all collections that implement the Collection
interface can be traversed using the for(:)
loop. A collection that implements the Collection
interface and thereby the Iterable
interface, has the element type E
. This element type E
must be assignable to the type of the variable in the for(:)
loop. The variable is assigned the reference value of a new element in the collection each time the body of the loop is executed.
The semantics of the for(:)
loop discussed in Section 6.3, p. 220, also apply when traversing a collection. In particular, any structural change to the collection (adding or removing elements) in the for(:)
loop will result in a ConcurrentModificationException
.
Example 15.13 illustrates using a for(:)
loop to traverse a collection. An empty collection of string builders is created at (1) and populated at (2) using a for(:)
loop that traverses over an array of string builders. The collection is traversed in the for(:)
loop at (3), reversing and printing the contents of each string builder in the collection. The output verifies that the state of each element in the collection was changed.
Behind the scenes, however, an appropriate iterator is used to traverse the collection, but the for(:)
loop simplifies traversing a collection in the source code.
Note that if the collection is ordered or sorted, the iterator will traverse the collection in the ordering used to maintain the elements in the collection. For example, in the case of an ArrayList
, the iterator will yield the elements in the same order as the insertion order. In the case of a TreeSet
, the iterator will yield the elements in the sort ordering used to maintain the elements in the set. If the collection is unordered, the order in which the iterator will yield the elements is not predictable. Thus, we cannot be sure in which order a Hashset
will be traversed.
Example 15.13 Using a for(:)
Loop to Iterate Over a Collection
import java.util.ArrayList;
import java.util.Collection;
public class IterateOverCollection {
public static void main(String[] args) {
// Create an empty collection of StringBuilders.
Collection<StringBuilder> words = new ArrayList
<StringBuilder>(); // (1)
// An array of StringBuilders
StringBuilder[] strArray = {
new StringBuilder("t'noD"), new StringBuilder("etareti"),
new StringBuilder("!em")
};
// Add StringBuilders from the array to the collection
for (StringBuilder str : strArray) { // (2)
words.add(str);
}
System.out.println("Before: " + words);
// Iterate over a collection of StringBuilders.
// Expression type is Collection<StringBuilder>,
// and element type is StringBuilder.
for (StringBuilder word : words) { // (3)
System.out.print(word.reverse() + " ");
}
System.out.println();
System.out.println("After: " + words);
}
}
Output from the program:
Before: [t'noD, etareti, !em]
Don't iterate me!
After: [Don't, iterate, me!]
These operations convert collections to arrays.
Object[] toArray()
<T> T[] toArray(T[] a)
The first toArray()
method returns an array of type Object
filled with all the elements of the collection. The second method is a generic method that stores the elements of a collection in an array of type T
.
If the given array is big enough, the elements are stored in this array. If there is room to spare in the array, that is, the length of the array is greater than the number of elements in the collection, the spare room is filled with null
values before the array is returned. If the array is too small, a new array of type T
and appropriate size is created. If T
is not a supertype of the runtime type of every element in the collection, an ArrayStoreException
is thrown.
Example 15.13 illustrates converting collections to arrays. At (1) the call to the toArray()
method returns an array of type Object
. Since an array of type Object
is not a subtype of an array of type String
, the compiler reports an error at (2).
At (3), the call to the toArray()
method returns an array of size 3, array type Object[]
, and element type String
, when the method was passed a zero-length array of type Object
. In other words, the method created a suitable-size array of type Object
since the array passed in the argument was too small. This array was filled with the elements of the set, which are strings. Although the array returned is of type Object
, the objects stored in it are of type String
. The output from the program confirms these observations.
At (4), the call to the toArray()
method returns an array of size 3, array type String[]
, and element type String
, when the method was passed a zero-length array of type String
. Now the method creates a new suitable-size array of type String
and fills it with the elements of the set, which are strings. The output from the program shows that the array passed in the argument is not the same as the array returned by the method call.
At (5), the call to the toArray()
method returns the same array it was passed in the argument, since it is of appropriate size and type. In other words, the array passed in the argument is filled with the elements of the list and returned. This is corroborated by the output from the program.
Lastly, the program throws an ArrayStoreException
at (6), because String
objects cannot be stored in an array of type Integer
.
Example 15.14 Converting Collections to Arrays
import java.util.Collection;
import java.util.HashSet;
public class CollectionToArray {
public static void main(String[] args) {
Collection<String> strSet = new HashSet<String>();
strSet.add("2008"); strSet.add("2009"); strSet.add("2010");
int n = strSet.size();
Object[] objects = strSet.toArray(); // (1)
// String[] string = strList.toArray(); // (2) Compile-time error!
Object[] objArray = strSet.toArray(new Object[0]); // (3)
System.out.println("Array size: " + objArray.length);
System.out.println("Array type: " + objArray.getClass().getName());
System.out.println("Actual element type: " +
objArray[0].getClass().getName());
String[] strArray1 = new String[0];
String[] strArray2 = strSet.toArray(strArray1); // (4)
System.out.println("strArray1 == strArray2: " + (strArray1 == strArray2));
String[] strArray3 = new String[n];
String[] strArray4 = strSet.toArray(strArray3); // (5)
System.out.println("strArray3 == strArray4: " + (strArray3 == strArray4));
Integer[] intArray = strSet.toArray(new Integer[n]); // (6) Runtime error!
}
}
Output from the program:
Array size: 3
Array type: [Ljava.lang.Object;
Actual element type: java.lang.String
strArray1 == strArray2: false
strArray3 == strArray4: true
Exception in thread "main" java.lang.ArrayStoreException
at java.lang.System.arraycopy(Native Method)
at java.util.ArrayList.toArray(Unknown Source)
at CollectionToArray.main(CollectionToArray.java:28)
15.6 Which of these are core interfaces in the collections framework?
Select the three correct answers.
(a) Set<E>
(b) Bag<E>
(c) LinkedList<E>
(d) Collection<E>
(e) Map<K,V>
15.7 Which of these implementations are provided by the java.util
package?
Select the two correct answers.
(a) HashList<E>
(b) HashMap<K,V>
(c) ArraySet<E>
(d) ArrayMap<K,V>
(e) TreeMap<K,V>
15.8 What is the name of the interface used to represent collections that maintain nonunique elements in order?
Select the one correct answer.
(a) Collection<E>
(b) Set<E>
(c) SortedSet<E>
(d) List<E>
(e) Sequence<E>
15.9 Which methods are specified by the Iterator<E>
interface?
Select the three correct answers.
(a) hasNext()
(b) hasMore()
(c) remove()
(d) delete()
(e) more()
(f) next()
15.10 Which identifiers, when inserted in appropriate places in the program, will result in the output 911
?
Collection<________> myItems = new ArrayList<__________>();
myItems.add(9); myItems.add(1); myItems.add(1);
Iterator<_________> iterator = _____________.iterator();
while (______________.___________()) {
System.out.print(_____________._________());
}
Select the five correct answers.
(a) hasNext
(b) myItems
(c) next
(d) Integer
(e) int
(f) Collection
(g) iterator
15.11 What will the program print when it is compiled and run?
import java.util.ArrayList;
import java.util.Collection;
public class RQ400_100 {
public static void main(String[] args) {
int sum = 0;
for (int i : makeCollection())
sum += i;
System.out.println(sum);
}
static Collection<Integer> makeCollection() {
System.out.println("A collection coming up.");
Collection<Integer> collection = new ArrayList<Integer>();
collection.add(10); collection.add(20); collection.add(30);
return collection;
}
}
Select the one correct answer.
(a) A collection coming up.
60
(b) A collection coming up.
A collection coming up.
A collection coming up.
60
(c) The program does not compile.
(d) None of the above.
15.12 Which statements are true about the for(:)
loop:
for (type variable : expression) statement
Select the three correct answers.
(a) The variable
is only visible in the for(:)
loop body.
(b) The expression
is only evaluated once.
(c) The type of the expression must be java.lang.Iterable
or an array type.
(d) Changing the value of the variable
in the loop body affects the data structure represented by the expression
.
(e) The loop runs backwards if the expression
is negated as follows: !
expression
.
(f) We can iterate over several data structures simultaneously in a for(:)
loop.
15.13 What will the program print when compiled and run?
import java.util.ArrayList;
import java.util.Collection;
public class IterateOverCollection2 {
public static void main(String[] args) {
Collection<String> words = new ArrayList<String>();
words.add("Don't"); words.add("change"); words.add("me!");
System.out.println("Before: " + words);
for (String word : words) {
System.out.print(word.toUpperCase() + "_");
}
System.out.println();
System.out.println("After: " + words);
}
}
Select the one correct answer.
(a) Before: [Don't, change, me!]
DON'T_CHANGE_ME!_
After: [DON'T, CHANGE, ME!]
(b) Before: [Don't, change, me!]
DON'T_CHANGE_ME!_
After: [Don't, change, me!]
(c) The program will throw a java.util.ConcurrentModificationException
, when run.
(d) The program fails to compile.
15.14 Which code, when inserted at (1), will result in the following output:
Before: [Apple, Orange, Apple]
After: [Orange]
from the program when compiled and run?
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
class Fruity {
private String fName;
Fruity(String fName) { this.fName = fName; }
public void setName(String newName) { this.fName = newName; }
public String toString() { return fName; }
public boolean equals(Object other) {
if (this == other) return true;
if (!(other instanceof Fruity)) return false;
return fName.equalsIgnoreCase(((Fruity)other).fName);
}
}
public class RQ400_50 {
public static void main(String[] args) {
Fruity apple = new Fruity("Apple");
Fruity orange = new Fruity("Orange");
List<Fruity> list = new ArrayList<Fruity>();
list.add(apple); list.add(orange); list.add(apple);
System.out.println("Before: " + list);
// (1) INSERT CODE HERE ...
System.out.println("After: " + list);
}
}
Select the two correct answers.
(a) for (Fruity f : list) {
if (f.equals(apple))
list.remove(f);
}
(b) int i = 0;
for (Fruity f : list) {
if (f.equals(apple))
list.remove(i);
i++;
}
(c) for (int j = 0; j < list.size(); j++) {
Fruity f = list.get(j);
if (f.equals(apple))
list.remove(j);
}
(d) Iterator<Fruity> itr = list.iterator();
while (itr.hasNext()) {
Fruity f = itr.next();
if (f.equals(apple))
itr.remove();
}
15.15 Which statement, when inserted independently at (1), will cause either a compiletime or a runtime error?
import java.util.ArrayList;
import java.util.Collection;
public class RQ400_200 {
public static void main(String[] args) {
Collection<Integer> intList = new ArrayList<Integer>();
intList.add(2008); intList.add(2009); intList.add(2010);
// (1) INSERT STATEMENT HERE!
}
}
Select the four correct answers.
(a) Object[] objArray1 = intList.toArray();
(b) Integer[] intArray1 = intList.toArray();
(c) Number[] numArray1 = intList.toArray();
(d) Object[] objArray2 = intList.toArray(new Object[0]);
(e) Integer[] intArray2 = intList.toArray(new Integer[0]);
(f) Integer[] intArray3 = intList.toArray(new Number[0]);
(g) Number[] numArray2 = intList.toArray(new Number[0]);
(h) Number[] numArray3 = intList.toArray(new Integer[0]);
(i) Number[] numArray4 = intList.toArray(new Long[0]);
Unlike other implementations of the Collection
interface, implementations of the Set
interface do not allow duplicate elements. This also means that a set can contain at most one null
value. The Set
interface does not define any new methods, and its add()
and addAll()
methods will not store duplicates. If an element is not currently in the set, two consecutive calls to the add()
method to insert the element will first return true
, then false
. A Set
models a mathematical set (see Table 15.3), that is, it is an unordered collection of distinct objects.
Multisets (also called bags) that allow duplicate elements cannot be implemented using the Set
interface, since this interface requires that elements are unique in the collection.
The HashSet
class implements the Set
interface .
Since this implementation uses a hash table, it offers near constant-time performance for most operations. A HashSet
does not guarantee any ordering of the elements. However, the LinkedHashSet
subclass of HashSet
guarantees insertion-order. It is also the implementation of choice if frequent traversal over the set is necessary. The sorted counterpart is TreeSet
, which implements the SortedSet
and the NavigableSet
interfaces and has logarithmic time complexity (see Section 15.5, p. 800).
A HashSet
relies on the implementation of the hashCode()
and equals()
methods of its elements (see Section 15.1, p. 748). The hashCode()
method is used for hashing the elements (p. 760), and the equals()
method is needed for comparing elements. In fact, the equality and the hash codes of HashSet
s are defined in terms of the equality and the hash codes of their elements.
HashSet()
Constructs a new, empty set.
Constructs a new set containing the elements in the specified collection. The new set will not contain any duplicates. This offers a convenient way to remove duplicates from a collection.
HashSet(int initialCapacity)
Constructs a new, empty set with the specified initial capacity.
HashSet(int initialCapacity, float loadFactor)
Constructs a new, empty set with the specified initial capacity and the specified load factor.
As mentioned earlier, the LinkedHashSet
implementation is a subclass of the HashSet
class. It works similarly to a HashSet
except for one important detail. Unlike a HashSet
, a LinkedHashSet
guarantees that the iterator will access the elements in insertion order, that is, in the order in which they were inserted into the LinkedHashSet
.
The LinkedHashSet
class offers constructors analogous to the ones in the HashSet
class. The initial capacity (i.e., the number of buckets in the hash table) and its load factor (i.e., the ratio of number of elements stored to its current capacity) can be tuned when the set is created. The default values for these parameters will under most circumstances provide acceptable performance.
Example 15.15 demonstrates traversing a HashSet
(see (1)) and a LinkedHashSet
(see (2)). Regardless of the order in which elements are inserted into a HashSet
, we cannot depend on the order the for(:)
loop will traverse the elements in the set, as is evident from the program output. A LinkedHashSet
, on the other hand, is always traversed in insertion order (i.e., the last element inserted, is the first element retrieved) by the for(:)
loop. The program output confirms this behavior, as the meal that was inserted last into the LinkedHashSet
, is served first. The same behavior will be exhibited if an iterator is used explicitly.
Example 15.15 Traversing Over Sets
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
public class TraverseHashSetAndLinkedHashSet {
public static void main(String[] args) {
HashSet<String> set1 = new HashSet<String>(); // (1)
set1.add("breakfast"); set1.add("lunch"); set1.add("dinner");
System.out.println("Serving meals from a HashSet (order can vary):");
for (String meal : set1)
System.out.println(meal);
Set<String> set2 = new LinkedHashSet<String>(); // (2)
set2.add("breakfast"); set2.add("lunch"); set2.add("dinner");
System.out.println("Serving meals from a LinkedHashSet" +
" (always insertion order):");
for (String meal : set2)
System.out.println(meal);
}
}
Program output:
Serving meals from a HashSet (order can vary):
dinner
breakfast
lunch
Serving meals from a LinkedHashSet (always insertion order):
breakfast
lunch
dinner
Example 15.16 demonstrates set operations. It determines the following relationships between two sets of characters:
• whether they are disjunct, that is, have no elements in common
• whether they have the same elements, that is, are equivalent
• whether one is a subset of the other
• whether one is a superset of the other
• whether they have a common subset
Given a list of words as program arguments, each argument is turned into a set of characters. This character set is compared with the set of all characters encountered so far in previous arguments.
The set encountered
created at (1) accumulates characters as each argument is processed. For each argument, an empty set of characters is created at (2). This characters
set is populated with the characters of the current argument at (3). The program first determines if there is a common subset between the two sets at (4), i.e., whether the current argument has any characters that were in previous arguments:
// Determine whether a common subset exists. (4)
Set<Character> commonSubset = new HashSet<Character>(encountered);
commonSubset.retainAll(characters);
boolean areDisjunct = commonSubset.size()==0;
Note that the retainAll()
operation is destructive. The code at (4) does not affect the encountered
and the characters
sets. If the size of the common subset is zero, the sets are disjunct; otherwise, the relationship must be narrowed down. The subset and superset relations are determined at (5) using the containsAll()
method.
// Determine superset and subset relations. (5)
boolean isSubset = encountered.containsAll(characters);
boolean isSuperset = characters.containsAll(encountered);
The sets are equivalent if both the previous relations are true
. If the relations are both false
, that is, no subset or superset relationship exists, the sets only have the subset computed at (4) in common. The encountered
set is updated with the contents of the characters
set to accumulate all characters encountered so far. The addAll()
method is used for this purpose at (6):
encountered.addAll(characters); // (6)
As we can see from the output, the program prints the contents of the sets in the standard textual representation for collections.
Example 15.16 Using Sets
import java.util.HashSet;
import java.util.Set;
public class CharacterSets {
public static void main(String[] args) {
int numArgs = args.length;
// A set keeping track of all characters previously
encountered.
Set<Character> encountered = new HashSet<Character>(); // (1)
// For each program argument in the command line ...
for (String argument : args) {
// Convert the current argument to a set of characters.
Set<Character> characters = new HashSet<Character>(); // (2)
int size = argument.length();
// For each character in the argument...
for (int j=0; j<size; j++)
// add character to the characters set.
characters.add(argument.charAt(j)); // (3)
// Determine whether a common subset exists. (4)
Set<Character> commonSubset = new HashSet<Character>(encountered);
commonSubset.retainAll(characters);
boolean areDisjunct = commonSubset.size()==0;
if (areDisjunct) {
System.out.println(characters + " and " + encountered + " are disjunct.");
} else {
// Determine superset and subset relations. (5)
boolean isSubset = encountered.containsAll(characters);
boolean isSuperset = characters.containsAll(encountered);
if (isSubset && isSuperset)
System.out.println(characters + " is equivalent to " + encountered);
else if (isSubset)
System.out.println(characters + " is a subset of " + encountered);
else if (isSuperset)
System.out.println(characters + " is a superset of " + encountered);
else
System.out.println(characters + " and " + encountered + " have " +
commonSubset + " in common.");
}
// Update the set of characters encountered so far.
encountered.addAll(characters); // (6)
}
}
}
Running the program with the following arguments:
>java CharacterSets i said i am maids
results in the following output:
[i] and [] are disjunct.
[d, a, s, i] is a superset of [i]
[i] is a subset of [d, a, s, i]
[a, m] and [d, a, s, i] have [a] in common.
[d, a, s, m, i] is equivalent to [d, a, s, m, i]
Before reading this subsection, it is a good idea to review the subsection The Comparable<E>
Interface, p. 765, on specifying the natural ordering for objects, and the subsection The Comparator<E>
Interface, p. 771, on specifying a particular total ordering for objects.
The SortedSet
interface extends the Set
interface to provide the functionality for handling sorted sets. Since the elements are sorted, traversing the set either using the for(:)
loop or an iterator will access the elements according to the ordering used by the set.
// First-last elements
E first()
E last()
The first()
method returns the first element currently in this sorted set, and the last()
method returns the last element currently in this sorted set. The elements are chosen based on the ordering used by the sorted set. Both throw a NoSuchElementException
if the sorted set is empty.
// Range-view operations
SortedSet<E> headSet(<E> toElement)
SortedSet<E> tailSet(<E> fromElement)
SortedSet<E> subSet(<E> fromElement, <E> toElement)
The headSet()
method returns a view of a portion of this sorted set, whose elements are strictly less than the specified element. Similarly, the tailSet()
method returns a view of the portion of this sorted set, whose elements are greater than or equal to the specified element. The subSet()
method returns a view of the portion of this sorted set, whose elements range from fromElement
, inclusive, to toElement
, exclusive (also called half-open interval). It throws an IllegalArgumentException
if the fromElement
is greater than the toElement
.
Note that the views present the elements sorted in the same order as the underlying sorted set. Note that changes made through views are also reflected in the underlying sorted set, and vice versa.
// Comparator access
Comparator<? super E> comparator()
This method returns the comparator associated with this sorted set, or null
if it uses the natural ordering of its elements. This comparator, if defined, is used by default when a sorted set is constructed and also used when copying elements into new sorted sets.
The NavigableSet
interface extends the SortedSet
interface with navigation methods to find the closest matches for specific search targets. By navigation, we mean operations that require searching for elements in the navigable set. In the absence of elements, these operations return null
rather than throw a NoSuchElementException
.
The NavigableSet
interface replaces the SortedSet
interface and is the preferred choice when a sorted set is required. In addition to the methods of the SortedSet
interface, the NavigableSet
interface adds the following new methods:
// First-last elements
E pollFirst()
E pollLast()
The pollFirst()
method removes and returns the first element and the pollLast()
method removes and returns the last element currently in this navigable set. The element is determined according to some policy employed by the set—for example, queue policy. Both return null
if the sorted set is empty.
// Range-view operations
NavigableSet<E> headSet(<E> toElement, boolean inclusive)
NavigableSet<E> tailSet(<E> fromElement, boolean inclusive)
NavigableSet<E> subSet(<E> fromElement, boolean fromInclusive,
<E> toElement, boolean toInclusive)
These operations are analogous to the ones in the SortedSet
interface (p. 765), returning different views of the underlying navigable set, depending on the bound elements. However, the bound elements can be excluded or included by the operation, depending on the value of the boolean
argument inclusive
.
The method ceiling()
returns the least element in the navigable set greater than or equal to argument e
. The method floor()
returns the greatest element in the navigable set less than or equal to argument e
. The method higher()
returns the least element in the navigable set strictly greater than argument e
. The method lower()
returns the greatest element in the navigable set strictly less than argument e
. All methods return null
if the required element is not found.
// Reverse order
Iterator<E> descendingIterator()
NavigableSet<E> descendingSet()
The first method returns a reverse-order view of the elements in the navigable set. The second method returns a reverse-order iterator for the navigable set.
The TreeSet
class implements the NavigableSet
interface and thereby the SortedSet interface. By default, operations on a sorted set rely on the natural ordering of the elements. However, a total ordering can be specified by passing a customized comparator to the constructor.
The TreeSet
implementation uses balanced trees, which deliver excellent (logarithmic) performance for all operations. However, searching in a HashSet
can be faster than in a TreeSet
because hashing algorithms usually offer better performance than the search algorithms for balanced trees. The TreeSet
class is preferred if elements are to be maintained in sorted order and fast insertion and retrieval of individual elements is desired.
The TreeSet
class provides four constructors:
TreeSet()
The default constructor creates a new empty sorted set, according to the natural ordering of the elements.
TreeSet(Comparator<? super E> comparator)
A constructor that takes an explicit comparator for specific total ordering of the elements.
TreeSet(Collection<? extends E> collection)
A constructor that creates a sorted set based on a collection, according to the natural ordering of the elements.
A constructor that creates a new set containing the same elements as the specified sorted set, with the same ordering.
Example 15.17 illustrates some selected navigation operations on a TreeSet
. The set is created at (1) and populated by calling the Collections.addAll()
method at (2). The elements are maintained according to the natural ordering for String
s, i.e., the one defined by the compareTo()
method of the Comparable
interface implemented by the String
class. The subset-view operations at (3) show how the bounds can be inclusive or exclusive. Note also how the closest-match methods at (4) behave. A sorted set with the reverse order corresponding to the natural ordering is created at (5). The methods pollFirst()
and pollLast()
remove the element that is retrieved, i.e., they change the set structurally.
The following code shows how we can create a sorted set with a specific total ordering by supplying a comparator in the constructor call:
NavigableSet<String> strSetB =
new TreeSet<String>(String.CASE_INSENSITIVE_ORDER);
Collections.addAll(strSetB, "strictly", "dancing", "Java", "Ballroom");
System.out.println(strSetB); // [Ballroom, dancing, Java, strictly]
Example 15.17 Using Navigable Sets
import java.util.Collections;
import java.util.NavigableSet;
import java.util.TreeSet;
import static java.lang.System.out;
public class SetNavigation {
public static void main(String[] args) {
NavigableSet<String> strSetA = new TreeSet<String>(); // (1)
Collections.addAll(strSetA, "Strictly", "Java", "dancing", "ballroom"); //
(2)
out.println("Before: " + strSetA); // [Java, Strictly, ballroom,
dancing]
out.println("
Subset-views:"); // (3)
out.println(strSetA.headSet("ballroom", true)); // [Java, Strictly, ballroom]
out.println(strSetA.headSet("ballroom", false)); // [Java, Strictly]
out.println(strSetA.tailSet("Strictly", true)); // [Strictly, ballroom,
// dancing]
out.println(strSetA.tailSet("Strictly", false)); // [ballroom, dancing]
out.println(strSetA.subSet("A", false, "Z", false )); // [Java, Strictly]
out.println(strSetA.subSet("a", false, "z", false )); // [ballroom, dancing]
out.println("
Closest-matches:"); // (4)
out.println(strSetA.ceiling("ball")); // ballroom
out.println(strSetA.floor("ball")); // Strictly
out.println(strSetA.higher("ballroom")); // dancing
out.println(strSetA.lower("ballroom")); // Strictly
out.println("
Reverse order:"); // (5)
out.println(strSetA.descendingSet()); // [dancing, ballroom, Strictly, Java]
out.println("
First-last elements:"); // (6)
out.println(strSetA.pollFirst()); // Java
out.println(strSetA.pollLast()); // dancing
out.println("
After: " + strSetA); // [Strictly, ballroom]
}
}
Program output:
Before: [Java, Strictly, ballroom, dancing]
Subset-views:
[Java, Strictly, ballroom]
[Java, Strictly]
[Strictly, ballroom, dancing]
[ballroom, dancing]
[Java, Strictly]
[ballroom, dancing]
Closest-matches:
ballroom
Strictly
dancing
Strictly
Reverse order:
[dancing, ballroom, Strictly, Java]
First-last elements:
Java
dancing
After: [Strictly, ballroom]
Lists are collections that maintain their elements in order and can contain duplicates. The elements in a list are ordered. Each element, therefore, has a position in the list. A zero-based index can be used to access the element at the position designated by the index value. The position of an element can change as elements are inserted or deleted from the list, i.e., as the list is changed structurally.
In addition to the operations inherited from the Collection
interface, the List
interface also defines operations that work specifically on lists: position-based access of the list elements, searching in a list, operations on parts of a list (called open range-view operations), and creation of customized iterators. This additional functionality is provided by the following methods in the List
interface:
// Positional Index
E get(int index)
Returns the element at the specified index.
E set(int index, E element)
Optional
Replaces the element at the specified index with the specified element. It returns the previous element at the specified index.
void add(int index, E element)
Optional
boolean addAll(int index, Collection<? extends E> c)
Optional
The first method inserts the specified element at the specified index. If necessary, it shifts the element previously at this index and any subsequent elements one position toward the end of the list. The inherited method add(E)
from the Collection
interface will append the specified element to the end of the list.
The second method inserts the elements from the specified collection at the specified index, using an iterator of the specified collection, i.e. the method splices the elements of the specified collection into the list at the specified index. The method returns true
if any elements were added.
E remove(int index)
Optional
Deletes and returns the element at the specified index, contracting the list accordingly. The inherited method remove(E)
from the Collection
interface will remove the first occurrence of the element from the list.
In a non-empty list, the first element is at index 0
and the last element is at size()-1
. As might be expected, all methods throw an IndexOutOfBoundsException
if an illegal index is specified.
// Element Search
int indexOf(Object o)
int lastIndexOf(Object o)
These methods return the index of the first and the last occurrence of the element that is the same as the specified argument, respectively, if such an element exists in the list; otherwise, the value –1 is returned.
// Open Range-View
List<E> subList(int fromIndex, int toIndex)
This method returns a view of the list, which consists of the sublist of the elements from the index fromIndex
to the index toIndex-1
, i.e. a half-open interval. A view allows the range it represents in the underlying list to be manipulated. Any changes in the view are reflected in the underlying list, and vice versa. Views can be used to perform operations on specific ranges of a list.
The iterator from the first method traverses the elements consecutively, starting with the first element of the list, whereas the iterator from the second method starts traversing the list from the element indicated by the specified index.
interface ListIterator<E> extends Iterator<E> {
boolean hasNext();
boolean hasPrevious();
E next(); // Element after the cursor
E previous(); // Element before the cursor
int nextIndex(); // Index of element after the cursor
int previousIndex(); // Index of element before the cursor
void remove(); // Optional
void set(E o); // Optional
void add(E o); // Optional
}
The ListIterator
interface is a bidirectional iterator for lists. It extends the Iterator
interface and allows the list to be traversed in either direction. When traversing lists, it can be helpful to imagine a cursor moving forward or backward between the elements when calls are made to the next()
and the previous()
methods, respectively. The element that the cursor passes over is returned. When the remove()
method is called, the element last passed over is removed from the list.
Three implementations of the List
interface are provided in the java.util
package: ArrayList
, LinkedList
, and Vector
.
The ArrayList
class implements the List
interface. The Vector
class is a legacy class that has been retrofitted to implement the List
interface, and will not be discussed in detail. The Vector
and ArrayList
classes are implemented using dynamically resizable arrays, providing fast random access (i.e., position-based access) and fast list traversal—very much like using an ordinary array. Unlike the ArrayList
class, the Vector
class is thread-safe, meaning that concurrent calls to the vector will not compromise its integrity. The LinkedList
implementation uses a doubly-linked list. Insertions and deletions in a doubly-linked list are very efficient.
The ArrayList
and Vector
classes offer comparable performance, but Vector
s suffer a slight performance penalty due to synchronization. Position-based access has constant-time performance for the ArrayList
and Vector
classes. However, positionbased access is in linear time for a LinkedList
owing to traversal in a doubly-linked list. When frequent insertions and deletions occur inside a list, a LinkedList
can be worth considering. In most cases, the ArrayList
implementation is the overall best choice for implementing lists.
In addition to the List
interface, the LinkedList
class also implements two other interfaces that allow it to be used for stacks and different kinds of queues (see Section 15.7, p. 809).
The ArrayList
class provides the following constructors:
ArrayList()
ArrayList(Collection<? extends E> c)
The default constructor creates a new, empty ArrayList
.
The second constructor creates a new ArrayList
containing the elements in the specified collection. The new ArrayList
will retain any duplicates. The ordering in the ArrayList
will be determined by the traversal order of the iterator for the collection passed as argument.
The LinkedList
class provides constructors that are analogous to these two ArrayList
constructors.
ArrayList(int initialCapacity)
The third constructor creates a new, empty ArrayList
with the specified initial capacity.
Example 15.18 illustrates some basic operations on lists. The user gets one shot at guessing a five-digit code. The solution is hard-wired in the example as a list of five Integer
objects. The secretSolution
list is created at (1) and populated using the add()
method. The guess specified at the command line is placed in a separate list, called guess
, at (2).
The number of digits that are correctly guessed is determined at (3). The solution is first duplicated and each digit in the guess is removed from the duplicated solution. The number of deletions corresponds to the number of correct digits in the guess
list. A digit at a particular index in the guess list is returned by the get()
method. The remove()
method returns true
if the duplicate list was modified, that is, the digit from the guess was found and removed from the duplicated solution. Of course, one could use the retainAll()
method, as shown below, but the idea in Example 15.18 is to use positional access on the guess
list.
// Find the number of digits that were correctly included. (3)
List<Integer> duplicate = new ArrayList<Integer>(secretSolution);
duplicate.retainAll(guess);
numOfDigitsIncluded = duplicate.size();
Finding the number of digits that are correctly placed is achieved by using two list iterators at (4), which allow digits in the same position in the guess
and the secretSolution
lists to be compared.
Example 15.18 Using Lists
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
public class TakeAGuess {
final static int NUM_DIGITS = 5;
public static void main(String[] args) {
// Sanity check on the given data.
try {
if (args.length != 1 || args[0].length() != NUM_DIGITS)
throw new IllegalArgumentException();
Integer.parseInt(args[0]);
} catch(IllegalArgumentException nfe) {
System.err.println("Guess should be " + NUM_DIGITS + " digits.");
return;
}
String guessStr = args[0];
System.out.println("Guess: " + guessStr);
/* Initialize the solution list. This program has a
fixed solution. */
List<Integer> secretSolution = new ArrayList<Integer>(); // (1)
secretSolution.add(5); secretSolution.add(3);
secretSolution.add(2); secretSolution.add(7);
secretSolution.add(2);
// Convert the guess from string to a list of Integers. (2)
List<Integer> guess = new ArrayList<Integer>();
for (int i = 0; i < guessStr.length(); i++)
guess.add(Character.getNumericValue(guessStr.charAt(i)));
// Find the number of digits that were correctly
included. (3)
List<Integer> duplicate = new ArrayList<Integer>(secretSolution);
int numOfDigitsIncluded = 0;
for (int i=0; i<NUM_DIGITS; i++)
if (duplicate.remove(guess.get(i))) numOfDigitsIncluded++;
/* Find the number of digits correctly placed by
comparing the two
lists, element by element, counting each correct
placement. */
// Need two iterators to traverse through the guess and
solution lists. (4)
ListIterator<Integer> correct = secretSolution.listIterator();
ListIterator<Integer> attempt = guess.listIterator();
int numOfDigitsPlaced = 0;
while (correct.hasNext())
if (correct.next().equals(attempt.next())) numOfDigitsPlaced++;
// Print the results.
System.out.println(numOfDigitsIncluded + " digit(s) correctly included.");
System.out.println(numOfDigitsPlaced + " digit(s) correctly placed.");
}
}
Running the program with the following arguments:
>java TakeAGuess 32227
gives the following output:
Guess: 32227
4 digit(s) correctly included.
1 digit(s) correctly placed.
In this section we look at the different types of queues provided by the Java collections framework.
The Queue
interface extends the Collection
interface to specify a general contract for queues. A queue is a collection that maintains elements in processing order. An implementation of the Queue
interface provides the queue policy for yielding the next element for processing. A head position in the queue specifies where the next element for processing can be obtained. A basic queue usually maintains its elements in First-In-First-Out (FIFO) ordering, but other orderings are also quite common: Last-In-first-Out (LIFO) ordering (also called stacks) or priority ordering (also called priority queues). The order in which elements of a queue can be retrieved for processing is dictated either by the natural ordering of the elements or by a comparator.
The Queue
interface extends the Collection
interface with the following methods:
// Insert
boolean add(E element)
boolean offer(E element)
Both methods insert the specified element in the queue. The return value indicates the success or failure of the operation. The add()
method inherited from the Collection
interface throws an IllegalStateException
if the queue is full, but the offer()
method does not.
// Remove
E poll()
E remove()
Both methods retrieve the head element and remove it from the queue. If the queue is empty, the poll()
method returns null
, but the remove()
method throws a NoSuchElementException
.
Both methods retrieve the head element, but do not remove it from the queue. If the queue is empty, the peek()
method returns null
, but the element()
method throws a NoSuchElementException
.
Both the PriorityQueue
and LinkedList
classes implement the Queue
interface. Unless bi-directional traversal is necessary, other queue implementations should be considered, and not the LinkedList
class. (The LinkedList
class is also eclipsed by the introduction of the ArrayDeque
class when it comes to implementing deques, as we will see shortly.)
As the name suggests, the PriorityQueue
class is the obvious implementation for a queue with priority ordering. The implementation is based on a priority heap, a tree-like structure that yields an element at the head of the queue according to the priority ordering, which is defined either by the natural ordering of its elements or by a comparator. In the case of several elements having the same priority, one of them is chosen arbitrarily.
Elements of a PriorityQueue are not sorted. The queue only guarantees that elements can be removed in priority order, and any traversal using an iterator does not guarantee to abide by the priority order.
The PriorityQueue
class provides the following constructors:
PriorityQueue()
PriorityQueue(Collection<? extends E> c)
The default constructor creates a new, empty PriorityQueue
with default initial capacity and natural ordering. The second constructor creates a new PriorityQueue
containing the elements in the specified collection. It will have natural ordering of its elements, unless the specified collection is either a SortedSet
or another PriorityQueue
, in which case, the collection’s ordering will be used.
PriorityQueue(int initialCapacity)
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
The first constructor creates a new, empty PriorityQueue
with the specified initial capacity and natural ordering. The second constructor creates a new, empty PriorityQueue
with the specified initial capacity, but the ordering is defined by the specified comparator.
PriorityQueue(PriorityQueue<? extends E> pq)
PriorityQueue(SortedSet<? extends E> set)
The constructors create a new PriorityQueue
with the ordering and the elements from the specified priority queue or sorted set, respectively.
Example 15.19 illustrates using priority queues. The example shows how two priority queues maintain objects of the class Task
. The equality of objects in this class is based on the task number (Integer
), as is the natural ordering of the objects. The natural ordering implemented by the class Task
will result in the priority queue yielding its elements in ascending order of the task numbers, i.e., tasks with smaller task numbers will have higher priority. The class Task
also defines two comparators at (1) and (2). The first one defines a total ordering of tasks based on descending order of the task name (String
), and the second one takes both task number and task name into consideration.
The main()
method in the class TaskExecutor
creates an array with some tasks at (3). Tasks from this array will be loaded into a priority queue. The method testPQ()
at (5) uses the priority queue it receives as argument. It loads the queue at (6) from the array, which is also passed as argument. It calls the offer()
method to insert a task in the priority queue.
The testPQ()
method calls the peek()
method at (7) to examine the task at the head of the queue. The tasks are executed by removing them one by one at (8) by calling the poll()
method.
The priority queue pq1
at (3) has its priority ordering defined by the natural ordering of the tasks. Note that the textual representation of the queue in the output
Queue before executing tasks: [100@breakfast, 200@lunch,
300@dinner, 200@tea]
does not show the tasks in priority order. It just shows what task there are in the queue. The textual representation of the queue is generated by the print method running an iterator over the queue. The iterator is under no obligation to take the priority order into consideration. The output also shows that the task with the highest priority (i.e., the smallest task number) is at the head of the queue:
Task at the head: 100@breakfast
The call to the poll()
method in the while
loop at (8) removes tasks in priority order, as verified by the output:
Doing tasks: 100@breakfast 200@tea 200@lunch 300@dinner
Since two of the tasks have the same priority, the queue chooses which one should be chosen first. The queue is empty when the peek()
method returns null
.
We leave it to the reader to verify that the output also conforms to the priority ordering of the pq2
priority queue at (4) that uses the supplied comparator to implement its priority ordering.
Example 15.19 Using Priority Queues
import java.util.Comparator;
/** Represents a task. */
public class Task implements Comparable<Task> {
private Integer taskNumber;
private String taskName;
public Task(Integer tp, String tn) {
taskNumber = tp;
taskName = tn;
}
public boolean equals(Object obj) { // Equality based on the task number.
if (obj instanceof Task)
return this.taskNumber.equals(((Task)obj).taskNumber);
return false;
}
public int compareTo(Task task2) { // Natural ordering based on the task number.
return this.taskNumber.compareTo(task2.taskNumber);
}
public int hashCode() { // Hash code based on the task number.
return this.taskNumber.hashCode();
}
public String toString() {
return taskNumber + "@" + taskName;
}
public String getTaskName() {
return taskName;
}
// A total ordering based on *descending* order of task
names (String). (1)
public static Comparator<Task> comparatorA() {
return new Comparator<Task>() {
public int compare(Task task1, Task task2) {
return task2.getTaskName().compareTo(task1.getTaskName());
}
};
}
// A total ordering based on task numbers (Integer) and
task names (String). (2)
public static Comparator<Task> comparatorB() {
return new Comparator<Task>() {
public int compare(Task task1, Task task2) {
if (!task1.taskNumber.equals(task2.taskNumber))
return task1.taskNumber.compareTo(task2.taskNumber);
if (!task1.taskName.equals(task2.taskName))
return task1.getTaskName().compareTo(task2.getTaskName());
return 0;
}
};
}
}
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
/** Executes tasks. */
public class TaskExecutor {
public static void main(String[] args) {
// Array with some tasks. (2)
Task[] taskArray = {
new Task(200, "lunch"), new Task(200, "tea"),
new Task(300, "dinner"), new Task(100, "breakfast"),
};
System.out.println("Array of tasks: " + Arrays.toString(taskArray));
// Priority queue using natural ordering (3)
PriorityQueue<Task> pq1 = new PriorityQueue<Task>();
testPQ(taskArray, pq1);
// Priority queue using a total ordering (4)
Comparator<Task> compA = Task.comparatorB();
int initCap = 5;
PriorityQueue<Task> pq2 = new PriorityQueue<Task>(initCap, compA);
testPQ(taskArray, pq2);
}
static void testPQ(Task[] taskArray, PriorityQueue<Task> pq) { // (5)
// Load the tasks: (6)
for (Task task : taskArray)
pq.offer(task);
System.out.println("Queue before executing tasks: " + pq);
// Peek at the head: (7)
System.out.println("Task at the head: " + pq.peek());
// Do the tasks: (8)
System.out.print("Doing tasks: ");
while (!pq.isEmpty()) {
Task task = pq.poll();
System.out.print(task + " ");
}
}
}
Program output:
Array of tasks: [200@lunch, 200@tea, 300@dinner, 100@breakfast]
Queue before executing tasks: [100@breakfast, 200@lunch,
300@dinner, 200@tea]
Task at the head: 100@breakfast
Doing tasks: 100@breakfast 200@tea 200@lunch 300@dinner
Queue after executing tasks: []
Queue before executing tasks: [100@breakfast, 200@lunch,
300@dinner, 200@tea]
Task at the head: 100@breakfast
Doing tasks: 100@breakfast 200@lunch 200@tea 300@dinner
The Queue
interface defines the contract for queues where the head element is always removed according to a processing order. The processing order is always defined by the natural ordering or a total ordering of the elements maintained by the queue. The Deque
interface extends the Queue
interface to allow double-ended queues. Such a queue is called a deque. It allows operations not just at its head, but also at its tail. It is a linear unbounded structure in which elements can be inserted at or removed from either end. Various synonyms are used in the literature for the head and tail of a deque: front and back, first and last, start and end.
A deque can be used as FIFO queue, where elements added at the tail are presented at the head for inspection or removal in the same order, thus implementing FIFO order. A deque can also be used as a stack, where elements are added to and removed from the same end, thus implementing LIFO ordering.
The Deque
interface defines symmetrical operations at its head and tail. Which end is in question is made evident by the method name. Below, equivalent methods from the Queue
are also identified. The push()
and pop()
methods are convenient for implementing stacks.
// Insert
boolean offerFirst(E element)
boolean offerLast(E element)
Queue equivalent: offer()
void push(E element)
Synonym: addFirst()
void addFirst(E element)
void addLast(E element)
Queue equivalent: add()
These methods insert the specified element in the deque. They all throw a NullPointerException
if the specified element is null
. The addFirst()
and addLast()
methods throw an IllegalStateException
if the element cannot be added, but the offerFirst()
and offerLast()
methods do not.
// Remove
E pollFirst()
Queue equivalent: poll()
E pollLast()
E pop()
Synonym: removeFirst()
E removeFirst()
Queue equivalent: remove()
E removeLast()
boolean removeFirstOccurence(Object obj)
boolean removeLastOccurence(Object obj)
These methods remove an element from the deque. The pollFirst()
and pollLast()
methods return null
if the deque is empty. The removeFirst()
and removeLast()
methods throw a NoSuchElementException
if the deque is empty.
// Examine
E peekFirst()
Queue equivalent: peek()
E peekLast()
E getFirst()
Queue equivalent: element()
E getLast()
These methods retrieve an element from the deque, but do not remove it from the deque. The peekFirst()
and peekLast()
methods return null
if the deque is empty. The getFirst()
and getLast()
methods throw a NoSuchElementException
if the deque is empty.
Returns an iterator to traverse the deque in reverse order, i.e., from the tail to the head.
The ArrayDeque
and LinkedList
classes implement the Deque
interface. The ArrayDeque
class provides better performance than the LinkedList
class for implementing FIFO queues, and is also a better choice than the java.util.Stack
class for implementing stacks.
An ArrayDeque
is also Iterable
, and traversal is always from the head to the tail. The class provides the descendingIterator()
method for iterating in reverse order. Since deques are not lists, positional access is not possible, nor can they be sorted.
Example 15.20 illustrates using an ArrayDeque
both as a stack and as a FIFO queue. Elements from an array are pushed on to the stack at (3), and then popped from the stack at (5). The call to the isEmpty()
method in the while
loop at (4) determines whether the stack is empty. The output shows that the elements were popped in the reverse order to the order in which they were inserted, i.e., LIFO ordering.
Similarly, elements from an array are inserted at the tail of a FIFO queue at (8), and then removed from the head of the FIFO queue at (10). The call to the isEmpty()
method in the while
loop at (4) determines whether the FIFO queue is empty. The output shows that the elements were removed in the same order as they were inserted, i.e., FIFO ordering.
Note that in Example 15.20 the stack grows at the head of the deque, but the FIFO queue grows at the tail of the deque.
Example 15.20 Using Deques as a Stack and as a FIFO Queue
import java.util.ArrayDeque;
import java.util.Arrays;
/** Executes tasks. */
public class TaskExecutor2 {
public static void main(String[] args) {
String[] elementArray = {"sway", "and", "twist", "stacks",
"tall"}; // (1)
System.out.println("Array of elements: " + Arrays.toString(elementArray));
// Using ArrayDeque as a stack: (2)
ArrayDeque<String> stack = new ArrayDeque<String>();
for (String string : elementArray)
stack.push(string); // (3) Push elements.
System.out.println("Stack before: TOP->" + stack + "<-BOTTOM");
System.out.print("Popping stack: ");
while (!stack.isEmpty()) { // (4)
System.out.print(stack.pop() + " "); // (5) Pop elements.
}
System.out.println("
");
// Using ArrayDeque as a FIFO queue: (6)
elementArray = new String[] {"Waiting", "in", "queues", "is", "boring"}; // (7)
System.out.println("Array of elements: " + Arrays.toString(elementArray));
ArrayDeque<String> fifoQueue = new ArrayDeque<String>();
for (String string : elementArray)
fifoQueue.offerLast(string); // (8) Insert at tail.
System.out.println("Queue before: HEAD->" + fifoQueue + "<-TAIL");
System.out.print("Polling queue: ");
while (!fifoQueue.isEmpty()) { // (9)
String string = fifoQueue.pollFirst(); // (10) Remove from head.
System.out.print(string.toUpperCase() + " ");
}
System.out.println();
}
}
Program output:
Array of elements: [sway, and, twist, stacks, tall]
Stack before: TOP->[tall, stacks, twist, and, sway]<-BOTTOM
Popping stack: tall stacks twist and sway
Array of elements: [Waiting, in, queues, is, boring]
Queue before: HEAD->[Waiting, in, queues, is, boring]<-TAIL
Polling queue: WAITING IN QUEUES IS BORING