2

This is the code of HashMap.java (docjar). Hash for key is calculated on line 431. This helps to fetch the index i on line 432. This all the entries at that index should have the same hash. Why is the check for hash equality made again on line 440 ? (if (e.hash == hash )

private void putForCreate(K key, V value) {
  430           int hash = (key == null) ? 0 : hash(key.hashCode());
  431           int i = indexFor(hash, table.length);
  432   
  433           /**
  434            * Look for preexisting entry for key.  This will never happen for
  435            * clone or deserialize.  It will only happen for construction if the
  436            * input Map is a sorted map whose ordering is inconsistent w/ equals.
  437            */
  438           for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  439               Object k;
  440               if (e.hash == hash &&
  441                   ((k = e.key) == key || (key != null && key.equals(k)))) {
  442                   e.value = value;
  443                   return;
  444               }
  445           }
  446   
  447           createEntry(hash, key, value, i);
  448       }
JavaDeveloper
  • 5,320
  • 16
  • 79
  • 132

1 Answers1

4

The same bucket may contain entries whose keys have different hash codes (since the bucket index i is determined by applying modulus table.length on the computed hash, so different hash codes may be mapped to the same bucket), so the comparison in line 440 saves you the need to call equals for the two keys that don't have the same hash code, which would normally be more expensive than comparing two ints.

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
Eran
  • 387,369
  • 54
  • 702
  • 768
  • can a bucket hold 2 different hashcodes ?? – Rahman Dec 06 '15 at 17:08
  • @Rehman yes, it can. Suppose you HashMap has 16 buckets. Then both hashCodes 3 and 19 will be mapped to the same bucket - 3. – Eran Dec 06 '15 at 17:10
  • Are you sure ? I dont think so .Then how a hashcode can determine a bucket ? http://stackoverflow.com/questions/6493605/how-does-a-java-hashmap-handle-different-objects-with-the-same-hash-code "The hash code of the key is 235 -> the pair is stored in bucket number 235". – Rahman Dec 06 '15 at 17:32