Why containsKey() of Map only invoke hashCode()?

Question

I read interface Map's JavaDoc and it says this:

Many methods in Collections Framework interfaces are defined in terms of the equals method. For example, the specification for the containsKey(Object key) method says: "returns true if and only if this map contains a mapping for a key k such that (key==null ? k==null : key.equals(k))." This specification should not be construed to imply that invoking Map.containsKey with a non-null argument key will cause key.equals(k) to be invoked for any key k. Implementations are free to implement optimizations whereby the equals invocation is avoided, for example, by first comparing the hash codes of the two keys. (The Object.hashCode() specification guarantees that two objects with unequal hash codes cannot be equal.)

My understanding is when containsKey() is invoked, both hashCode() and equals() wil be called, therefore I wrote my own code to test it.

HappyDay class will be stored as a key in HashMap, I override hashCode() and equals() methods, and add System.out.println("invoking hashCode()" + this.happyHour); and System.out.println("invoking equals()"); to check whether the method is invoked or not.

public class HappyDay {

    private final int happyHour;

    public HappyDay(int hh) {
        this.happyHour = hh;
    }

    public int getHappyHour() {
        return this.happyHour;
    }

    @Override
    public boolean equals(Object o) {
        System.out.println("invoking equals()");
        if (o == null) {return false;}

        if (o == this) {return true;}

        //this is an easy overridden, if happy hour equal, objects will be equal.
        if (o instanceof HappyDay) {
            HappyDay other = (HappyDay) o;
            int otherHappyHour = other.getHappyHour();
            if (this.happyHour == otherHappyHour) {
                return true;
            }
        }
        return false;
    }

    @Override
    public int hashCode() {
        System.out.println("invoking hashCode()" + this.happyHour);
        int hash = 7;
        hash = hash + this.happyHour;
        return hash;
    }
}

public class Main {
    public static void main(String[] args) {
        Map<HappyDay,String> hm = new HashMap<>();

        HappyDay hd1 = new HappyDay(1);
        HappyDay hd2 = new HappyDay(2);

        hm.put(hd1, "hd1");
        hm.put(hd2, "hd2");

        if(hm.containsKey(hd2)){
            System.out.println("found");
        }else{
            System.out.println("not exist");
        }
    }
}

The Main class is to put two HappyDay instances into HashMap, after insertion(put() method), I invoke hm.containsKey(hd2), as I quoted from JavaDoc, it should call hashCode() first and then call equals(), but the output is

invoking hashCode()1 //call put()
invoking hashCode()2 //call put()
invoking hashCode()2 //call containsKey()
found

I am expecting there's another output line should be invoking equals(), can anyone explain this for me why equals() is not called?

Answer 1

Hash map first checks key equality via ==; only if that fails does it carry on to check with equals.

Now, you put hd2 into the map as a key, then you are checking containsKey using the same object as an argument, so the == test passes and equals is never called.

Checking if a map contains a given key comes down to checking if getEntry(key) returns null. Let's look at the source:

360     final Entry<K,V> getEntry(Object key) {
361         int hash = (key == null) ? 0 : hash(key.hashCode());
362         for (Entry<K,V> e = table[indexFor(hash, table.length)];
363              e != null;
364              e = e.next) {
365             Object k;
366             if (e.hash == hash &&
367                 ((k = e.key) == key || (key != null && key.equals(k))))
368                 return e;
369         }
370         return null;
371     }

On line 367, we can see that an == test is performed before a equals test. The short-circuiting of || completely skips the equals test if == passes, which is what is happening here.

This is probably implemented as it is to skip potentially expensive equals methods (e.g. String#equals which has to check each character of the given string). The equals contract also states that o1.equals(o2) should be true if o1 == o2, so this is a valid optimization.

---

Let's do a sanity check by modifying your code slightly:

if (hm.containsKey(new HappyDay(2))) {
    System.out.println("found");
} else {
    System.out.println("not exist");
}

Now the output is:

invoking hashCode()1
invoking hashCode()2
invoking hashCode()2
invoking equals()
found

Notice that equals is invoked. This makes sense because we are invoking containsKey with a new but equal object, so the == test returns false and the equals test is executed.

Answer 2

The source code for HashMap tells what's going on.

The containsKey method calls getEntry:

360     final Entry<K,V> More ...getEntry(Object key) {
361         int hash = (key == null) ? 0 : hash(key.hashCode());
362         for (Entry<K,V> e = table[indexFor(hash, table.length)];
363              e != null;
364              e = e.next) {
365             Object k;
366             if (e.hash == hash &&
367                 ((k = e.key) == key || (key != null && key.equals(k))))
368                 return e;
369         }
370         return null;
371     }

If the hashes match, then the keys are compared with == first. Since you pass in the original hd2 object, the == operator returns true (it's the same object), and the short-circuiting || operator never evaluates the right side, and equals isn't called.

If you were to make another HappyDay, also passing 2, then == would yield false and equals would be called.

As for why == is there first, I would have to guess that it's on average more efficient to do a fast == first, and only fall back on a potentially more costly call to equals if they aren't the same object.