Java important methods— equals(), hashCode() and compareTo()
Today, I am just writing up on three very important methods that are often used together for sorting and comparison on different Java collections.
equals()
This is used in most collections to determine if a collection contains a given element. For instance:
List<MyClass> list = new ArrayList<MyClass>();MyClass c1 = new MyClass( .. ); // Some parameters are passed
MyClass c2 = new MyClass( .. ); // Some parameters are passedlist.add(c1);...boolean hasObject = list.contains(c2);
As shown, in operations like contains(), remove(), etc., the ArrayList iterates through the whole list and performs element.equals(someObject) to determine if the element is equal to the parameter object. If matched, it performs the relevant action like assert presence (for contains()), remove element (for remove()), etc.
According to the equals() Javadoc, the method must conform to the following rules:
The equals() method implements an equivalence relation:
- It is reflexive: For any reference value x,
x.equals(x)should return true - It is symmetric: For any reference values x and y,
x.equals(y)should return true if and only ify.equals(x)returns true - It is transitive: For any reference values x, y, and z, if
x.equals(y)returns true andy.equals(z)returns true, thenx.equals(z)should return true - It is consistent: For any reference values x and y, multiple invocations of
x.equals(y)consistently return true or consistently return false, provided no information used in equals comparisons on the object is modified - For any non-null reference value x,
x.equals(null)should return false
Joshua Bloch offers a five-step recipe for writing an effectiveequals() method. Here's the recipe in code form:
public class EffectiveEquals {
private int valueA;
private int valueB;
. . .
public boolean equals( Object o ) {
if(this == o) { // Step 1: Perform an == test
return true;
}
if(!(o instanceof EffectiveEquals)) { // Step
2: Instance of check
return false;
}
EffectiveEquals ee = (EffectiveEquals) o; //
Step 3: Cast argument
// Step 4: For each important field, check to
see if they are equal
// For primitives use ==
// For objects use equals() but be sure to also
// handle the null case first
return ee.valueA == valueA &&
ee.valueB == valueB;
}
. . .
}Note: You need not perform a null check since null instanceof EffectiveEqualswill evaluate to false.
Finally, for Step 5, go back to equals()'s contract and ask yourself if the equals()method is reflexive, symmetric, and transitive. If not, change it.
Now an important point to discuss in this context is the difference between reference equality and object equality. Check the below code :
int a = 4; int b = 4;System.out.println(a==b);
Integer a1 = new Integer(2);Integer b1 = new Integer(2);System.out.println(a1==b1);String a2 = "as";String b2 = "as";System.out.println(a2==b2);System.out.println(a2.equals(b2));String a3 = new String("as");String b3 = new String("as");System.out.println(a3==b3);System.out.println(a3.equals(b3));// Output:
true
false
true
true
false
true
In the above example, the first output is a Java primitive type reference comparison between primitive types using ‘==’, compares their values. The second case, the comparison is happening between two addresses in memory (reference equality) and hence it returns false, even though the values are same. Now for third and fourth case, the string references are equal because their values are equal. JVM does not create a separate holder, but reuses the holder having same value from the String-pool. For the last two cases, we create separate String objects and hence the reference equality fails. Hence, we should always use equals() for value comparison.
hashCode()
The hashCode() method of objects is used when you insert them into a HashTable, HashMap or HashSet.
A slightly more in-depth explanation will help in understanding HashTable’s mechanism for storage and retrieval. A HashTable internally contains buckets in which it stores the key/value pairs. The HashTable uses the key’s hashcode to determine to which bucket the key/value pair should map.
Above image shows a HashTable and its buckets. When you pass a key/value to the HashTable, it queries the key’s hashcode. The HashTable uses that code to determine the bucket in which to place the key/value. So, for example, if the hashcode equals zero, the HashTable places the value into Bucket 0. Likewise, if the hashcode is two, the HashTable places the value into Bucket 2. (This is a simplistic example; the HashTable will massage the hashcode first so the HashTable doesn’t try to insert the value outside the bucket.)
By using the hashcode this way, the HashTable can also quickly determine in which bucket it has placed the value when you try to retrieve it.
Hashcodes, however, represent only half the picture. The hashcode only tells the HashTable into which bucket to drop the key/value. Sometimes, however, multiple objects may map to the same bucket, an event known as a collision. In Java, the HashTable responds to a collision by placing multiple values into the same bucket (other implementations may handle collisions differently). Below is shown what a HashTable might look like after a few collisions.
Now imagine that you call get() with a key that maps to Bucket 0. The HashTable will now need to perform a sequential search through the key/value pairs in Bucket 0 to find your requested value. To perform this lookup, the HashTable executes the following steps:
- Query the key’s hashcode
- Retrieve the list of key/values residing in the bucket given by the hashcode
- Scan through each entry sequentially until a key that equals the key passed into get() is found
A long answer to a short question I know, but it gets worse. Properly overriding equals() and hashCode() is a nontrivial exercise. You must take extreme care to guarantee both methods' contracts.
According to the hashCode() Javadoc, the method must conform to the following rules:
- Whenever it is invoked on the same object more than once during an execution of a Java application, the
hashCode()method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application. - If two objects are equal according to the
equals(Object)method, then calling thehashCode()method on each of the two objects must produce the same integer result. - It is not required that if two objects are unequal according to the method
equals(Object), then calling thehashCode()method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hashtables.
Creating a hashCode()
Creating a properly working hashCode() method proves difficult; it becomes even more difficult if the object in question is not immutable. You can calculate a hashcode for a given object in many ways. The most effective method bases the number upon the object's fields. Moreover, you can combine these values in various ways. Here are two popular approaches:
- You can turn the object’s fields into a string, concatenate the strings, and return the resulting hashcode
- You can add each field’s hashcode and return the result
While other, more thorough, approaches exist, the two aforementioned approaches prove the easiest to understand and implement.
compareTo()
This stands in the same league of equals() and hashcode() and used to implement natural order of object. compareTo() method is defined in interface java.lang.Comparable and it is used to implement natural sorting on Java classes. Natural sorting means the the sort order which naturally applies on object e.g. lexical order for String, numeric order for Integer or Sorting Employee by there ID etc. most of the java core classes including String and Integer implements CompareTo() method and provide natural sorting.
The need
Sorting is an essential part of application development, which you often required to implement in your system. in Java sorting is implemented using Comparator and Comparable in Java. Since we store java objects in Collection there are also certain Set and Map which provides automating sorting when you insert element on that e.g. TreeSet and TreeMap. to implement sorting you need to override either compareTo(Object o) method or Comparable class or compare(Object o1, Object o2) method of Comparator class. Most of the classes implement Comparable to implement natural order. for example if you are writing Employee object you probably want to implement Comparable interface and override compareTo() method to compare current employee with other employee based on ID. So essentially you need to override compareTo() because you need to sort elements in ArrayList or any other Collection.
Implementing Comparable allows:
- calling Collections.sort and Collections.binarySearch
- calling Arrays.sort and Arrays.binarySearch
- using objects as keys in a TreeMap
- using objects as elements in a TreeSet
How to
The compareTo method needs to satisfy the following conditions. These conditions have the goal of allowing objects to be fully sorted, much like the sorting of a database result set on all fields.
- anticommutation : x.compareTo(y) is the opposite sign of y.compareTo(x)
- exception symmetry : x.compareTo(y) throws exactly the same exceptions as y.compareTo(x)
- transitivity : if x.compareTo(y)>0 and y.compareTo(z)>0, then x.compareTo(z)>0 (and same for less than)
- if x.compareTo(y)==0, then x.compareTo(z) has the same sign as y.compareTo(z)
- consistency with equals is highly recommended, but not required : x.compareTo(y)==0, if and only if x.equals(y) ; consistency with equals is required for ensuring sorted collections (such asTreeSet) are well-behaved.
One can greatly increase the performance of compareTo by comparing first on items which are most likely to differ. Also, unless required, always implement Comparable interface instead of extending Comparable class.
Compare the various types of fields as follows:
- numeric primitive : use < and >. There is an exception to this rule: float and double primitives should be compared using Float.compare(float, float) and Double.compare(double, double). This avoids problems associated with special border values.
- boolean primitive : use tests of the form (x && !y)
- Object : use compareTo. (Note that possibly-null fields present a problem : while x.equals(null) returns false, x.compareTo(null) will always throw a NullPointerException)
- type-safe enumeration : use compareTo, like any Object
- collection or array : Comparable does not seem to be intended for these kinds of fields. For example, List, Map and Set do not implement Comparable. As well, some collections have no definite order of iteration, so doing an element-by-element comparison cannot be meaningful in those cases.
An example:
import java.util.*;
import java.io.*;public final class Account implements Comparable<Account> {
enum AccountType {CASH, MARGIN, RRSP};
public Account (
String aFirstName,
String aLastName,
int aAccountNumber,
int aBalance,
boolean aIsNewAccount,
AccountType aAccountType
) {
//..parameter validations elided
fFirstName = aFirstName;
fLastName = aLastName;
fAccountNumber = aAccountNumber;
fBalance = aBalance;
fIsNewAccount = aIsNewAccount;
fAccountType = aAccountType;
}
/**
* @param aThat is a non-null Account.
*
* @throws NullPointerException if aThat is null.
*/
@Override public int compareTo(Account aThat) {
final int BEFORE = -1;
final int EQUAL = 0;
final int AFTER = 1;
//this optimization is usually worthwhile, and can
//always be added
if (this == aThat) return EQUAL;
//primitive numbers follow this form
if (this.fAccountNumber < aThat.fAccountNumber) return BEFORE;
if (this.fAccountNumber > aThat.fAccountNumber) return AFTER;
//booleans follow this form
if (!this.fIsNewAccount && aThat.fIsNewAccount) return BEFORE;
if (this.fIsNewAccount && !aThat.fIsNewAccount) return AFTER;
//objects, including type-safe enums, follow this form
//note that null objects will throw an exception here
int comparison = this.fAccountType.compareTo(aThat.fAccountType);
if (comparison != EQUAL) return comparison;
comparison = this.fLastName.compareTo(aThat.fLastName);
if (comparison != EQUAL) return comparison;
comparison = this.fFirstName.compareTo(aThat.fFirstName);
if (comparison != EQUAL) return comparison;
if (this.fBalance < aThat.fBalance) return BEFORE;
if (this.fBalance > aThat.fBalance) return AFTER;
//all comparisons have yielded equality
//verify that compareTo is consistent with equals (optional)
assert this.equals(aThat) : "compareTo inconsistent with equals.";
return EQUAL;
}
/**
* Define equality of state.
*/
@Override public boolean equals(Object aThat) {
if (this == aThat) return true;
if (!(aThat instanceof Account)) return false;
Account that = (Account)aThat;
return
( this.fAccountNumber == that.fAccountNumber ) &&
( this.fAccountType == that.fAccountType ) &&
( this.fBalance == that.fBalance ) &&
( this.fIsNewAccount == that.fIsNewAccount ) &&
( this.fFirstName.equals(that.fFirstName) ) &&
( this.fLastName.equals(that.fLastName) )
;
}
/**
* A class that overrides equals must also override hashCode.
*/
@Override public int hashCode() {
int result = HashCodeUtil.SEED;
result = HashCodeUtil.hash( result, fAccountNumber );
result = HashCodeUtil.hash( result, fAccountType );
result = HashCodeUtil.hash( result, fBalance );
result = HashCodeUtil.hash( result, fIsNewAccount );
result = HashCodeUtil.hash( result, fFirstName );
result = HashCodeUtil.hash( result, fLastName );
return result;
}
//PRIVATE
private String fFirstName; //non-null
private String fLastName; //non-null
private int fAccountNumber;
private int fBalance;
private boolean fIsNewAccount;
/**
* Type of the account, expressed as a type-safe enumeration (non-null).
*/
private AccountType fAccountType;
/**
* Exercise compareTo.
*/
public static void main (String[] aArguments) {
//Note the difference in behaviour in equals and compareTo, for nulls:
String text = "blah";
Integer number = new Integer(10);
//x.equals(null) always returns false:
System.out.println("false: " + text.equals(null));
System.out.println("false: " + number.equals(null) );
//x.compareTo(null) always throws NullPointerException:
//System.out.println( text.compareTo(null) );
//System.out.println( number.compareTo(null) );
Account flaubert = new Account(
"Gustave", "Flaubert", 1003, 0,true, AccountType.MARGIN
);
//all of these other versions of "flaubert" differ from the
//original in only one field
Account flaubert2 = new Account(
"Guy", "Flaubert", 1003, 0, true, AccountType.MARGIN
);
Account flaubert3 = new Account(
"Gustave", "de Maupassant", 1003, 0, true, AccountType.MARGIN
);
Account flaubert4 = new Account(
"Gustave", "Flaubert", 2004, 0, true, AccountType.MARGIN
);
Account flaubert5 = new Account(
"Gustave", "Flaubert", 1003, 1, true, AccountType.MARGIN
);
Account flaubert6 = new Account(
"Gustave", "Flaubert", 1003, 0, false, AccountType.MARGIN
);
Account flaubert7 = new Account(
"Gustave", "Flaubert", 1003, 0, true, AccountType.CASH
);
System.out.println( "0: " + flaubert.compareTo(flaubert) );
System.out.println( "first name +: " + flaubert2.compareTo(flaubert) );
//Note capital letters precede small letters
System.out.println( "last name +: " + flaubert3.compareTo(flaubert) );
System.out.println( "acct number +: " + flaubert4.compareTo(flaubert) );
System.out.println( "balance +: " + flaubert5.compareTo(flaubert) );
System.out.println( "is new -: " + flaubert6.compareTo(flaubert) );
System.out.println( "account type -: " + flaubert7.compareTo(flaubert) );
}
}
// ================================// A sample run of this class gives:
>java -cp . Account
false: false
false: false
0: 0
first name +: 6
last name +: 30
acct number +: 1
balance +: 1
is new -: -1
account type -: -1
The behaviour of the above program varies for older JDK 1.4.
Thanks.
