data structures - Why can hashCode() return the same value for different objects in Java?

Question

A quote from the book I'm reading Head First Java:

The point is that hashcodes can be the same without necessarily guaranteeing that the objects are equal, because the "hashing algorithm" used in the hashCode() method might happen to return the same value for multiple objects.

Why might the hashCode() method return the same value for different objects? Does that not cause problems?

Answer 1

hashing an object means "finding a good, descriptive value (number) that can be reproduced by the very same instance again and again". Because hash codes from Java's Object.hashCode() are of type int, you can only have 2^32 different values. That's why you will have so-called "collisions" depending on the hashing algorithm, when two distinct Objects produce the same hashCode.

Typically, this does not produce any problems, because hashCode() is mostly used together with equals(). For instance, a HashMap will call hashCode() upon its keys, to know whether the keys may already be contained in the HashMap. If the HashMap does not find the hash code, it's obvious the key is not contained in the HashMap yet. But if it does, it will have to double-check all keys having that same hash code using equals().

I.e.

A.hashCode() == B.hashCode() // does not necessarily mean
A.equals(B)

But

A.equals(B) // means
A.hashCode() == B.hashCode()

If equals() and hashCode() are implemented correctly.

For a more precise description of the general hashCode contract, see the Javadoc.