Make delicious recipes!

HashCode, Equals and compareTo contract


Base class of all classes - Object has some very interesting methods.
Two of them are:

  1. public int hashCode():
    Used to compute hashCode for insertion/searching in a hash-map.
    By default, Object.hashCode() returns the reference of the object as an integer or does some simple numerical operations on this reference.

  2. public boolean equals(Object other):
    Used for breaking ties when multiple objects have same hash-code.
    By default, Object.equals() just does a reference comparison (pointer comparison).
    So all classes by default consider two objects equal only if they point to the same object.

These two methods are often overridden to provide customized behavior.
However, Java imposes a contract that must be followed if one overrides these methods.

HashCode/Equals Contract

If you override one method, then similar logic should be used to override the other.
In particular, if two objects are considered equal by the the equals() method, then hashCode() for them must be the same.


Example: Primitive wrappers' hashCode() and equals()

A good example of customized hashCode()/equals() methods are wrapper classes like Integer, Double, Character etc.
The equals method of these classes compares the wrapped primitives instead of reference comparison.
So two Integer objects each with same primitive value will be considered equal.
To honor the above contract "Two Integer objects with same primitive value must return the same hashCode", the hashCode() methods of the wrapper classes are also modified accordingly.

Anatomy of a HashMap

Consider the following code:
Class used as a key for HashSet HashSet usage
public class Address
{
    int aptNo;
    String streetName;

    @Override
    public int hashCode() { return aptNo; }

    @Override
    public boolean equals(Object obj)
    {
        Address other = (Address) obj;
        if (aptNo == other.aptNo && streetName.equals(other.streetName))
            return true;
        return false;
    }

    @Override
    public String toString() { return "[" + aptNo + ", " + streetName + "]"; }   

    public Address(int aptNo, String streetName)
    {
        this.aptNo = aptNo;
        this.streetName = streetName;
    }
}

import java.util.Arrays;
import java.util.HashSet;

public class HashCode_EqualsTo_CompareTo
{
    public static void main(String[] args)
    {
        Address addr[] = new Address[5];
        addr[0] = new Address(1, "Hollywood Street");     
        addr[1] = new Address(2, "Baker Avenue");
        addr[2] = new Address(2, "Baker Avenue");
        addr[3] = new Address(4, "Baker Avenue");
        addr[4] = new Address(2, "Paradise St");

        HashSet<Address> set = new HashSet<Address>();
        set.addAll(Arrays.asList(addr));
        log(set.toString());
    }

    static void log(String msg)
    {
        System.out.println(msg);
    }
}



The above code produces the following structure in the debugger:
Structure of the HashSet.

  1. HashMap internally uses an array of HashMap.Entry objects.
    (See the field table in left-side image).

  2. HashMap.Entry has a next field which makes it a linked list.
    So table is actually an array of linked-lists.

  3. hashCode() determines the bucket in which a particular key will fall.

  4. equals() helps to differentiate between objects in the same bucket.

Since our hashCode() simply returns the aptNo, so:

   1, Hollywood Street falls in bucket 1 and 4, Baker Avenue in bucket 4,

   but 2, Paradise St and 2, Baker Avenue both fall in bucket 2

Reverse of the contract is not a necessary requirement.


i.e. if two objects have same hash-code, then they can be considered un-equal by the equals() method. But such a thing will decrease hash-map performance.

Example: if hashCode() returned same value for all objects, then the left-side table will have just one entry and that entry will be a long linked list.
All HashMap searches will then degenerate to O(n) search of a linked-list.


equals() and compareTo() contract

Another method falling in the same bucket as the above is compareTo.
This method is mandatory to implement if a class implements the interface Comparable and is used while sorting the members of a class.
If two objects are considered equal by compareTo() and not by equals() or vice-versa, then TreeSet and TreeMap may produce different output.

For example, the above code is modified by adding a compareTo method as follows:
public class Address implements Comparable<Address>
{
    int aptNo;
    String streetName;

    @Override
    public int hashCode() { return aptNo; }

    @Override
    public boolean equals(Object obj)
    {
        Address other = (Address) obj;
        if (aptNo == other.aptNo && streetName.equals(other.streetName))
            return true;
        return false;
    }

    @Override
    public int compareTo(Address other)
    {
        return (aptNo - other.aptNo);
    }

    @Override
    public String toString() { return "[" + aptNo + ", " + streetName + "]"; }

    public Address(int aptNo, String streetName)
    {
        this.aptNo = aptNo;
        this.streetName = streetName;
    }
}
import java.util.Arrays;
import java.util.HashSet;
import java.util.TreeSet;

public class HashCode_EqualsTo_CompareTo
{
    public static void main(String[] args)
    {
        Address addr[] = new Address[5];
        addr[0] = new Address(1, "Hollywood Street");
        addr[1] = new Address(2, "Baker Avenue");
        addr[2] = new Address(2, "Baker Avenue");
        addr[3] = new Address(4, "Baker Avenue");
        addr[4] = new Address(2, "Paradise St");

        HashSet<Address> set = new HashSet<Address>();
        set.addAll(Arrays.asList(addr));
        log(set.toString());

        TreeSet<Address> treeSet = new TreeSet<Address>();
        treeSet.addAll(Arrays.asList(addr));
        log(treeSet.toString());
    }

    static void log(String msg)
    {
        System.out.println(msg);
    }
}



In the above, two address objects are considered equal by compareTo() if their aptNo is same.
But equals() method takes streetName also into consideration.

Output for this faulty implementation is:
[[1, Hollywood Street], [2, Paradise St], [2, Baker Avenue], [4, Baker Avenue]]    <-- HashSet
[[1, Hollywood Street], [2, Baker Avenue], [4, Baker Avenue]]                      <-- TreeSet
We would expect both of them to be present in the TreeSet, but since duplicate keys are not allowed in a TreeSet, only one of the object is present.
Since one would choose a TreeMap over HashMap only when there is a need to order the map's keys and not to drop some keys, it is advisable to keep the compareTo() method exactly similar to equals().

An interesting corollary from the above analysis is that TreeMap does not use hashCode() or equals() at all!
It solely relies on the compareTo() method and if your equals() does not comply with compareTo(), TreeMap does not care.
This could result in a serious application error where two objects considered equal by equals() return different values from TreeMap.

The TreeMap is so different from HashMap in implementation that its performance is also widely different.
For objects with good hashCode() methods, HashMap is blazing fast with O(1) time for inserts and lookups
While TreeMap cannot be faster than O(log N) even with the best compareTo() methods


Summary: All 3 methods - compareTo, equals and hashCode should be consistent with each other.
When you override/change any one of them, you will very likely need to override/change other methods too.


Experts' Corner
TreeSet/TreeMap is very much unlike a HashMap/HashSet as far as the internal implementation is concerned.
TreeSet internally uses a TreeMap which does not have a table of Map.Entry as found in HashMap.
Rather a TreeSet creates a Red-Black Binary Tree of Map.Entry objects as shown below:


Things to remember

  1. If overriding persistence objects’ hashCode/equals, then be especially careful with lazy loading. Due to lazy loading, most elements of a persistence object are loaded only the appropriate getter method is called. So do not access the fields directly in hashCode/equals. Always use corresponding getter method.

  2. Saving an object in the database may change its state causing hashCode/equals to change. For example: an entity not saved in the DB may have a null ID but as soon as its saved in the DB, it may get a new ID as primary key. So it will no longer remain equal to other in-memory objects.

  3. Eclipse (and most other editors) have a way to generate hashCode and equals methods automatically for a class. Use those.

  4. Apache Commons library has 2 very nice utilities HashCodeBuilder and EqualsBuilder which can be used in the code to help with the overriding of these methods.






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal