Why does HashMap.put compare hashes and test equality?

Question

I am analyzing the source code of the HashMap in Java and asking a question about the put method.

The following 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 got confused in if (e.hash == hash && ((k = e.key) == key || key.equals(k)))

Why such a condition?

Since there is a hashCode and equals contract in the Java Object superclass:

If two objects are equal in accordance with the equals (Object) method, then calling the hashCode method for each of the two objects should give the same integer result.

So, from key.equals(k) follows key.hashCode() == k.hashCode() .

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 not a condition like if ((k = e.key) == key || key.equals(k)) ?

Answer 1

He simply avoids calling the method when he can: If the hash (which is not hashCode() , this is the map's own hash) is different from the write hash, he knows that he does not need to call equals at all. Just optimize a bit.

Answer 2

This is just an optimization: comparing two integers is faster than calling equals() .

If the two hash codes are different from each other, then on the basis of the equals and hashCode agreement, the card knows that the existing key is not equal to the specified key and can move faster to the next.

Answer 3

The value of the "hash" variable may differ from the key hash. "hash" is the result of calling the hash method (key.hashCode ()). Therefore, comparing hash values ​​and key equality is required.