11.7 Implementing the equals() , hashCode() , and compareTo() Methods
11.7 Implementing the equals() , hashCode() , and compareTo() MethodsThe 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 sorted maps. Table 11.2 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:
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. The equals() MethodIf 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 11.7 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 11.7 A Simple Class for Version Number 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 TestVersionSimple in Example 11.8 uses objects of the class SimpleVNO . It declares three references that denote three different SimpleVNO objects, as shown at (1), (2), and (3), respectively. It also creates an array of SimpleVNO objects, called versions , as shown at (4). The type of these version objects will change in the subsequent examples, as we successively develop new versions of a class for version numbers. All of the examples will use the test() method defined in Example 11.8. We assume that the integers in the downloads array created at (5), represent the number of downloads for the software versions from the corresponding position in the versions array. Example 11.8 demonstrates that all SimpleVNO objects are unique, because the class SimpleVNO does not override the equals() method to provide any other equivalence relation. The object denoted by the reference latest is compared with the object denoted by the reference inShops and with the object denoted 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 for the object value equality. These references denote distinct objects, although the object denoted by the reference latest and the object denoted by the reference inShops have identical states. Not overriding the equals() method appropriately makes it impossible to search for SimpleVNO 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. Since all SimpleVNO objects are distinct, the equals() method will always return false , regardless of which object is compared with the search key object. As shown by the output from Example 11.8, searching for the version number (9.1.1) in the versions array will always fail. The versions array is converted to a List at (14), denoted by the reference vnoList , and the contains() method is called at (15) to check if the search key is in the list. The contains() method of a List relies on the equals() method provided by its elements. The result is, as expected, false . A HashMap with SimpleVNO objects as keys and Integer objects as values, is created at (17), based on the associative arrays versions and downloads . 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 not overridden either, the implementation in the Object class attempts to return distinct integers as hash codes for the objects. The code attempts to create a sorted set and a sorted map from the list and the map at (22) and (23), respectively. The class SimpleVNO must either implement the compareTo() method of the Comparable interface, or a comparator must be provided, in order to maintain objects in sorted sets or sorted maps (see Section 11.6, p. 452). In this example, the program output shows that an exception is thrown because SimpleVNO objects do not meet this criteria. However, the result is unpredictable when objects that do not meet the criteria are used in sorted sets or sorted maps. We will run the test() method in Example 11.8 on successive versions of a class for version numbers developed in this section. Example 11.8 Implications of Not Overriding the equals() Method import java.util.*; public class TestVersionSimple { public static void main(String[] args) { (new TestVersionSimple()).test(); } protected Object makeVersion(int a, int b, int c) { return new SimpleVNO(a, b, c); } protected void test() { // Three individual version numbers. Object latest = makeVersion(9,1,1); // (1) Object inShops = makeVersion(9,1,1); // (2) Object older = makeVersion(6,6,6); // (3) // An array of version numbers. Object[] versions = { // (4) makeVersion( 3,49, 1), makeVersion( 8,19,81), makeVersion( 2,48,28), makeVersion(10,23,78), makeVersion( 9, 1, 1)}; // An array of downloads. Integer[] downloads = { // (5) new Integer(245), new Integer(786), new Integer(54), new Integer(1010), new Integer(123)}; // Various tests. System.out.println("Test object reference and value equality:"); System.out.println(" latest: " + latest + ", inShops: " + inShops + ", older: " + older); System.out.println(" latest == inShops: " + (latest == inShops)); // (6) System.out.println(" latest.equals(inShops): " + (latest.equals(inShops))); // (7) System.out.println(" latest == older: " + (latest == older)); // (8) System.out.println(" latest.equals(older): " + (latest.equals(older))); // (9) Object searchKey = inShops; System.out.println("Search key: " + searchKey); // (10) System.out.print("Array: "); for (int i = 0; i < versions.length; i++) // (11) System.out.print(versions[i] + " "); boolean found = false; for (int i = 0; i < versions.length && !found; i++) found = searchKey.equals(versions[i]); // (12) System.out.println("\n Search key found in array: " + found); // (13) List vnoList = Arrays.asList(versions); // (14) System.out.println("List: " + vnoList); System.out.println(" Search key contained in list: " + vnoList.contains(searchKey)); // (15) Map versionStatistics = new HashMap(); // (16) for (int i = 0; i < versions.length; i++) // (17) versionStatistics.put(versions[i], downloads[i]); System.out.println("Map: " + versionStatistics); // (18) System.out.println(" Hash code for keys in the map:"); for (int i = 0; i < versions.length; i++) // (19) System.out.println(" " + versions[i] + ": " + versions[i].hashCode()); System.out.println(" Search key " + searchKey + " has hash code: " + searchKey.hashCode()); // (20) System.out.println(" Map contains search key: " + versionStatistics.containsKey(searchKey)); // (21) System.out.println("Sorted list:\n\t" + (new TreeSet(vnoList))); // (22) System.out.println("Sorted map:\n\t" + (new TreeMap(versionStatistics))); // (23) System.out.println("List before sorting: " + vnoList); // (24) Collections.sort(vnoList); System.out.println("List after sorting: " + vnoList); System.out.println("Binary search in list:"); // (25) int resultIndex = Collections.binarySearch(vnoList, searchKey); System.out.println("\tKey: " + searchKey + "\tKey index: " + resultIndex); } } Output from the program: 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 Search key: (9.1.1) Array: (3.49.1) (8.19.81) (2.48.28) (10.23.78) (9.1.1) Search key found in array: false List: [(3.49.1), (8.19.81), (2.48.28), (10.23.78), (9.1.1)] Search key contained in list: false Map: {(9.1.1)=123, (10.23.78)=1010, (8.19.81)=786, (3.49.1)=245, (2.48.28)=54} Hash code for keys in the map: (3.49.1): 13288040 (8.19.81): 27355241 (2.48.28): 30269696 (10.23.78): 24052850 (9.1.1): 26022015 Search key (9.1.1) has hash code: 20392474 Map contains search key: false Exception in thread "main" java.lang.ClassCastException ... An implementation of the equals() method must satisfy the properties of an equivalence relation :
The general contract of the equals() method is defined between objects of arbitrary classes . Understanding its criteria is important for providing a proper implementation. ReflexivityThis 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; SymmetryThe expression x.equals(y) invokes the equals() method on the object denoted by the reference x , whereas the expression y.equals(x) invokes the equals() method on the object denoted 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, but the other classes are not aware of this. Avoiding interoperability with other (non-related) classes when implementing the equals() method is strongly recommended. TransitivityIf 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 leverage on the superclass equals() method for comparing the superclass-specific 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, leveraging on 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. ConsistencyThis 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. null comparisonThis 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 11.9 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 11.9 shows an implementation of the equals() method for version numbers. Next , we provide a checklist for implementing the equals() method. Method overriding signatureThe method prototype 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 denoted 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. Reflexivity testThis is usually the first test performed in the equals() method, avoiding further computation if the test is true . The equals() method in Example 11.9 does this test at (2). Correct argument typeThe equals() method in Example 11.9 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 arisethere 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. Argument castingThe 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 11.9. The argument is cast at (4) to allow for class-specific field comparisons: UsableVNO vno = (UsableVNO) obj; // (4) Field comparisonsEquivalence 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 11.9 have only fields of primitive data types. 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 denotes 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 denoted 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() ). 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, or only including the derived fields might be prudent. Computing the equivalence relation should be deterministic, so the equals() method should not depend on unreliable resources, such as network access. The order in which the comparisons 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 11.9. Above all, an implementation of the equals() method must ensure that the equivalence relation is fulfilled. Example 11.10 is a client that uses the class UsableVNO from Example 11.9. This client runs the same tests as the client in Example 11.8. The difference is that the class UsableVNO overrides the equals() method. Example 11.10 Implications of Overriding the equals() Method public class TestVersionUsable extends TestVersionSimple { public static void main(String[] args) { (new TestVersionUsable()).test(); } protected Object makeVersion(int a, int b, int c) { return new UsableVNO(a, b, c); } } Output from the program: 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 Search key: (9.1.1) Array: (3.49.1) (8.19.81) (2.48.28) (10.23.78) (9.1.1) Search key found in array: true List: [(3.49.1), (8.19.81), (2.48.28), (10.23.78), (9.1.1)] Search key contained in list: true Map: {(10.23.78)=1010, (2.48.28)=54, (3.49.1)=245, (9.1.1)=123, (8.19.81)=786} Hash code for keys in the map: (3.49.1): 27355241 (8.19.81): 30269696 (2.48.28): 24052850 (10.23.78): 26022015 (9.1.1): 3541984 Search key (9.1.1) has hash code: 11352996 Map contains search key: false Exception in thread "main" java.lang.ClassCastException ... 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 an UsableVNO object in an array or a list of UsableVNO objects is now successful, as 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. The hashCode() MethodHashing 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:
Note that no duplicate items are stored. Retrieving an item is based on using a key . The key represents the identify the item. Item retrieval is also a two-step process:
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 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, there exist heuristics for constructing adequate hash functions. A hash table contains key-value entries as items, and the hashing is done only on the keys 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 11.2), the class must provide appropriate implementations of the following methods from the Object class:
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 11.9. Elements of this class are used as keys in Example 11.10. The output from the program shows that a map with the following entries is created: Map: {(10.23.78)=1010, (2.48.28)=54, (3.49.1)=245, (9.1.1)=123, (8.19.81)=786} 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. 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): 27355241 (8.19.81): 30269696 (2.48.28): 24052850 (10.23.78): 26022015 (9.1.1): 3541984 Attempting to find the search key (9.1.1) is in the map is unsuccessful : Search key (9.1.1) has hash code: 11352996 Map contains search key: false The hash values of two objects, which are equal according to the equals() method, are not equal according to the hashCode() method of the Object class. Therefore, the key object (9.1.1) of the entry <9.1.1, 123> in the map has a different hash value than the search key object (9.1.1). These objects hash to different buckets. The lookup for the search key object 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. Only 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 . General Contract of the hashCode() methodThe general contract of the hashCode() method stipulates:
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. Heuristics for implementing the hashCode() methodIn Example 11.11, 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 * 31 3 + release * 31 2 + revision * 31 1 + patch This can be verified by back substitution (see Section G.3, p. 596). 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 11.11 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: 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:
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. 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' * 31 2 + 'b' * 31 1 + 'c' * 31 = 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 11.12 uses objects of the class ReliableVNO in Example 11.11 to create a map and to search for a key in the map. Output from the program shows that the key object (9.1.1) of the entry <9.1.1, 123> in the map has the same hash value as the search key object (9.1.1). The search is successful. These objects hash to the same bucket. Therefore, the search for the key object 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 object (9.1.1) and the key object (9.1.1) of this entry. Example 11.12 Implications of Overriding the hashCode() Method public class TestVersionReliable extends TestVersionSimple { public static void main(String[] args) { (new TestVersionReliable()).test(); } protected Object makeVersion(int a, int b, int c) { return new ReliableVNO(a, b, c); } } Output from the program: ... Map: {(10.23.78)=1010, (2.48.28)=54, (3.49.1)=245, (8.19.81)=786, (9.1.1)=123} 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: true Exception in thread "main" java.lang.ClassCastException ... The compareTo() MethodThe Comparable interface is discussed in Section 11.6 on page 452. In this subsection we discuss how to implement its only method: the compareTo() method. This method defines the natural ordering for the instances of the class that implements the Comparable interface. Objects implementing Comparable can be used in sorted collections and sorted maps. We repeat the general contract for the compareTo() method from Section 11.6 on page 452 : int compareTo(Object 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 order. It throws a ClassCastException if the reference value passed in the argument cannot be cast to the type of the current object. An implementation of the compareTo() method for the objects of a class should meet the following criteria:
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. A compareTo() method is seldom implemented to interoperate with objects of other classes. 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 each other. public boolean equals(Object other) { // ... return compareTo(other) == 0; } An implementation of the compareTo() method for the class of version numbers is shown in Example 11.13. The implementation is also consistent with equals. Following general class design principles, the class is declared final so that it cannot be extended. Example 11.13 Implementing the compareTo() Method of the Comparable Interface public final class VersionNumber implements Comparable { 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 + release; hashValue = 31 * hashValue + revision; hashValue = 31 * hashValue + patch; return hashValue; } public int compareTo(Object obj) { // (7) VersionNumber vno = (VersionNumber) obj; // (8) // Compare the release numbers. (9) if (release < vno.release) return -1; if (release > vno.release) return 1; // Release numbers are equal, (10) // must compare revision numbers. if (revision < vno.revision) return -1; if (revision > vno.revision) return 1; // Release and revision numbers are equal, (11) // must compare patch numbers. if (patch < vno.patch) return -1; if (patch > vno.patch) return 1; // All fields are equal. (12) return 0; } } The compareTo() contract requires that an illegal argument type should result in a ClassCastException , and a null argument should result in a NullPointerException . Both these checks are embodied in the cast at (8) in Example 11.13. 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 is returned. This approach is shown in the implementation of the compareTo() method at (9) through (12) in Example 11.13. Comparison of integer values in fields can be optimized. For example, the code for comparing the release numbers at (9) in Example 11.13: if (release < vno.release) return -1; if (release > vno.release) return 1; // Next field comparison can be replaced by the following code for doing the comparison, which relies on the difference between the values: int releaseDiff = release - vno.release; if (releaseDiff != 0) return releaseDiff; // Next field comparison The above 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 invoke the compareTo() method on them or to use a comparator. Example 11.14 is a client that uses the class VersionNumber from Example 11.13. This client also runs the same tests as the client in Example 11.8. The difference 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. All the tests run as one would expect. Unlike previous attempts, VersionNumber objects can now be maintained in sorted sets and maps. System.out.println("Sorted list:\n\t" + (new TreeSet(vnoList))); // (22) System.out.println("Sorted map:\n\t" + (new TreeMap(versionStatistics))); // (23) By default, the class TreeSet relies on its elements to implement the compareTo() method. The output from the program in Example 11.14 shows that the TreeSet , created at (22), maintains its elements sorted in the natural order dictated by the compareTo() method. Analogously, the output from the program in Example 11.14 shows that the TreeMap , created at (23), maintains its entries sorted on the keys, which are in the natural order dictated by the compareTo() method. Example 11.14 Implications of Implementing the compareTo() Method public class TestVersion extends TestVersionSimple { public static void main(String[] args) { (new TestVersion()).test(); } protected Object makeVersion(int a, int b, int c) { return new VersionNumber(a, b, c); } } Output from the program: ... 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} ... 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 11.8. The following code sorts the elements in the list that was created at (14) in Example 11.14, and denoted by the reference vnoList : System.out.println("List before sorting: " + vnoList); // (24) Collections.sort(vnoList); System.out.println("List after sorting: " + vnoList); The output from executing this code shows that the elements in the list are now sorted: 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), denoted by the reference searchKey in Example 11.14: int resultIndex = Collections.binarySearch(vnoList, searchKey); System.out.println("\tKey: " + searchKey + "\tKey index: " + resultIndex); Executing the code prints the correct index of the search key in the list: Key: (9.1.1) Key index: 3  |
![A Programmer[ap]s Guide to Java Certification](/icons/blank_book.jpg "A Programmer[ap]s Guide to Java Certification"){kind=icon}
EAN: N/A
Pages: 284