CODEWITHSUNDEEP
javahash
Conner Gesbocker
Conner Gesbocker

Reputation: 394

What good is a hash code if it doesn't identify a unique object?

Java API - Class Object

Hash Code:

It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.

What consistency is achieved through hashing if two objects can product distinct integer results? It seems odd that two different objects can return the same hash value.

Upvotes: 3

Views: 215

Answers (2)

that other guy
that other guy

Reputation: 123560

What good is a hash code if it doesn't identify a unique object?

The hash code doesn't let you identify a unique object, but it does let you identify a unique group that the object is in.

You then only have to consider that group to find your object.

For example, a HashMap might have 500 items divided between 1,000 groups. Thanks to the hash code, it'll immediately know which of those 1,000 groups to look at, rejecting the 999 others.

Whether that group has 0, 1 or even 6 elements, it's still a huge time saver compared to looking through all 500.

Upvotes: 1

arshajii
arshajii

Reputation: 129537

There are only 232 integral values a hash code can have (in Java, at least). If you have more possible objects than that, then two different objects having the same hash value is unavoidable. We do our best to avoid these "hash collisions", but often it's just impossible mathematically (see pigeonhole principle).

We typically try to design hash functions such that their outputs are uniformly distributed within their range, thereby making collisions rare.

Upvotes: 4

Related Questions