Influence of HashMap optimization that caches the hash code associated with each entry to its get method

4
votes

from p.46 "Effective Java" Joshua Bloch. Item 9: ALways override hashCode when you override equals

  • Some class PhoneNumber overrides equals() and doesn't override hashCode()
  • "two instances are involved: one is used for insertion into the HashMap, and a second, equal, instance is used for (attempted) retrieval." ... "... Even if the two instances happen to hash to the same bucket, the get method will almost certainly return null , as HashMap has an optimization that caches the hash code associated with each entry and doesn't bother checking for object equality if the hash codes doesn't match."

The questions is - why 'get' will return 'null' if "the two instances happen to hash to the same bucket"?

  • what is the role (in not getting the right instance) of the HashMap optimization "that cashes..."?

  • Just for the case - "the two instances happen to hash to the same bucket"- what if HashMap bothers about "object equality if the hash codes doesn't match"?

2
javaoverridinghashmapequalshashcode

2 Answers

4
votes

Why 'get' will return 'null' if "the two instances happen to hash to the same bucket"? What is the role (in not getting the right instance) of the HashMap optimization "that cashes..."?

The key sentence is

[...] doesn't bother checking for object equality if the hash codes doesn't match.

So even if the keys hash to the same bucket, .equals may not be invoked (due to the caching optimizations) for the relevant element (since not even the hash-codes matches). Thus, even if the relevant element resides in the same bucket, it may never be compared through .equals, and thus not "found".

Just for the case - "the two instances happen to hash to the same bucket"- what if HashMap bothers about "object equality if the hash codes doesn't match"?

If it didn't have this optimization, and actually did check .equals on all elements in the corresponding bucket and if the two hashes happened to hash to the same bucket, then the get-method would return the correct element. (But this would be pure luck, since if the objects aren't equal, then there is no guarantee that the two hashes will map to the same bucket in the first place.)

1
votes

why 'get' will return 'null' if "the two instances happen to hash to the same bucket"

It will only do that if the hashCodes are unequal. It can do that because by the contract of hashCode(), unequal hashCodes imply unequal objects. (Note that the reverse isn't true: language lawyers please note.)