Why does HashMap.put both compare hashes and test equality?

Question

I analyse the HashMap source code in Java and get a question about the put method.

Below is the put method in JDK1.6:

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

I get confused about the if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

Why is the condition like this?

Because in Java super class Object, there is a contract of hashCode and equals:

If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.

So the key.equals(k) implies key.hashCode() == k.hashCode().

The hash() is below:

 static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

thus key.hashCode() == k.hashCode() implies e.hash == hash.

So why isn't the condition like if ((k = e.key) == key || key.equals(k))?

Answer 1

It's just an optimization: comparing two integers is faster than calling equals().

If the two hashcodes differ, then, based on the contract of equals and hashCode, the map knows that the existing key isn't equal to the given key, and can go faster to the next one.

Answer 2

It's just avoiding a method call when it can: If the hash (which isn't hashCode(), it's the map's own hashing) is different from the entry's hash, it knows it doesn't have to call equals at all. Just optimizing a bit.