Why is there a need to override hashcode if I override the 'equals' method in Java?

Question

I know there is a need to override hashcode whenever the equals method is overridden in Java. That is merely a contract. I am trying to understand the logic behind this. I was reading *Effective Java by Joshua Bloch, and I came across this code (Item 9, page 45):

import java.util.HashMap;
import java.util.Map;

public final class PhoneNumber {
    private final short areaCode;
    private final short prefix;
    private final short lineNumber;

    public PhoneNumber(int areaCode, int prefix, int lineNumber) {
        rangeCheck(areaCode, 999, "area code");
        rangeCheck(prefix, 999, "prefix");
        rangeCheck(lineNumber, 9999, "line number");
        this.areaCode = (short) areaCode;
        this.prefix = (short) prefix;
        this.lineNumber = (short) lineNumber;
    }

    private static void rangeCheck(int arg, int max, String name) {
        if (arg < 0 || arg > max)
            throw new IllegalArgumentException(name + ": " + arg);
    }

    @Override
    public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof PhoneNumber))
            return false;
        PhoneNumber pn = (PhoneNumber) o;
        return pn.lineNumber == lineNumber && pn.prefix == prefix
                && pn.areaCode == areaCode;
    }

    // Broken - no hashCode method!

    // A decent hashCode method - Page 48
    // @Override public int hashCode() {
    // int result = 17;
    // result = 31 * result + areaCode;
    // result = 31 * result + prefix;
    // result = 31 * result + lineNumber;
    // return result;
    // }

    // Lazily initialized, cached hashCode - Page 49
    // private volatile int hashCode; // (See Item 71)
    //
    // @Override public int hashCode() {
    // int result = hashCode;
    // if (result == 0) {
    // result = 17;
    // result = 31 * result + areaCode;
    // result = 31 * result + prefix;
    // result = 31 * result + lineNumber;
    // hashCode = result;
    // }
    // return result;
    // }

    public static void main(String[] args) {
        Map<PhoneNumber, String> m = new HashMap<PhoneNumber, String>();
        m.put(new PhoneNumber(707, 867, 5309), "Jenny");
        System.out.println(m.get(new PhoneNumber(707, 867, 5309)));
    }
}

This is what he mentions in the text, which I am having difficulty understanding.

At this point, you might expect m.get(new PhoneNumber(707, 867, 5309)) to return "Jenny", but it return null. Notice that two PhoneNumber instances are involved: one is used for insertion into the HashMap and a second, equal, instance is used for (attempted) retrieval. The PhoneNumber class's failure to override hashCode causes the two equal instances to have unequal hashcodes, in violation of the hashcode contract. Therefore the get method is likely to look for the phone number in a different hash bucket from the one in which it was stored by the put method

I don't understand what the two PhoneNumber instances he talks about. There is only instance that I create in m.put(new PhoneNumber(707, 867, 5309), "Jenny"). Also I look for this object again, which should return the same hashcode even if it inherits the hashCode method from Object Class. Why does this happen? Some explanation here would help a lot.

Answer 1

I don't understand what the two PhoneNumber instance he talks about.

The first one is the one you used for insertion.

m.put(new PhoneNumber(707, 867, 5309), "Jenny"));

The second instance is the one used for retrieval.

m.get(new PhoneNumber(707, 867, 5309)); // Notice the use of "new"

Also I look for this object again, which should return the same hashcode even if it inherits the hashCode method from Object Class.

That's incorrect. The default implementation of hashCode() in Object class returns distinct integers for distinct objects because it is implemented by converting the internal address of the object into an integer. Hence, the hash code check fails there.

If on the other hand, you had tried to retrieve the PhoneNumber using the same instance

PhoneNumber phoneNum = new PhoneNumber(707, 867, 5309);
m.put(phoneNum, "Jenny"));
m.get(phoneNum); // Not NULL

The hash code check would pass (since, you've used the same object that was inserted before) and the equals() as well. This of course isn't the recommended approach because we're far more likely to use a different key object than the one used for insertion.

The key used would, however, be meaningfully equivalent (like a different String object but whose text is the same) and hence providing a hashCode() implementation is required for the match and retrieval to happen correctly.

Also see: Checking for and Removing elements in Java HashMap