Are Two Java Objects with Same Hashcodes Not Necessarily Equal

Are two Java objects with same hashcodes not necessarily equal?

If two objects have the same hashcode then they are NOT necessarily equal. Otherwise you will have discovered the perfect hash function.

But the opposite is true: if the objects are equal, then they must have the same hashcode.

Why two objects with the same hashcode are not necessarily equals?

That's a simple matter of counting. A hash code is an integer so has 32 bits. Take now a Long for example. Since it is 64 bits long, there are much more values than 2³². Hence there must be a lot of values having the same hash code.

Consequences of different hashcodes but same equals for two java objects

The consequences will be unexpected behavior.

If a.equals(b) == true but a.hashCode()!=b.hashCode(), set.add(a) followed by set.contains(b) will most likely return false (assuming set is a HashSet), even though according to equals it should return true. (the reason it's most likely and not a certainty is that two different hash codes still have a chance of being mapped to the same bucket of the HashSet/HashMap, in which case you can still get true).

Two instances having the same hashcode but not equal

In simple terms hashcode () is a function to generate hash by some formula, so there can be some collisions, two different values can turn out to have same hashcode.

If I simply calculate the hashcode by taking mod by 6, then two different values might be having same hashcode.

Why does Java need equals() if there is hashCode()?

If two objects have the same hashCode then they are NOT necessarily equal. Otherwise you will have discovered the perfect hash function. But the opposite is true - if the objects are equal, then they must have the same hashCode.

How does a Java HashMap handle different objects with the same hash code?

A hashmap works like this (this is a little bit simplified, but it illustrates the basic mechanism):

It has a number of "buckets" which it uses to store key-value pairs in. Each bucket has a unique number - that's what identifies the bucket. When you put a key-value pair into the map, the hashmap will look at the hash code of the key, and store the pair in the bucket of which the identifier is the hash code of the key. For example: The hash code of the key is 235 -> the pair is stored in bucket number 235. (Note that one bucket can store more then one key-value pair).

When you lookup a value in the hashmap, by giving it a key, it will first look at the hash code of the key that you gave. The hashmap will then look into the corresponding bucket, and then it will compare the key that you gave with the keys of all pairs in the bucket, by comparing them with equals().

Now you can see how this is very efficient for looking up key-value pairs in a map: by the hash code of the key the hashmap immediately knows in which bucket to look, so that it only has to test against what's in that bucket.

Looking at the above mechanism, you can also see what requirements are necessary on the hashCode() and equals() methods of keys:

• If two keys are the same (equals() returns true when you compare them), their hashCode() method must return the same number. If keys violate this, then keys that are equal might be stored in different buckets, and the hashmap would not be able to find key-value pairs (because it's going to look in the same bucket).

• If two keys are different, then it doesn't matter if their hash codes are the same or not. They will be stored in the same bucket if their hash codes are the same, and in this case, the hashmap will use equals() to tell them apart.

Equal Objects must have equal hashcodes?

1. Correct, just a small correction - if two unequal objects have the same hashcode.
2. Not exactly, It's better to check it first, as a filter for the non-equal, but if you want to make sure the objects are equal, you should call equals()

Under what Conditions two different objects may have same hashcode() value..?

You can override hashCode in your classes. You would usually override it along with overriding equals, so that if a.equals(b) is true, a.hashCode() == b.hashCode() is also true (even if (a == b) is false).

However, even if a.equals(b) is false, a.hashCode() == b.hashCode() may still be true.

As you can see in the Javadoc of Object class :

• If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must
  produce the same integer result.
• It is not required that if two objects are unequal according to the java.lang.Object.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 hashtables.

if two objects hashcode is a same, why doesnot mean that o1.equals(o2)?

Consider Long. There are 2^64 possible values for this type. hashCode returns an int, which only has 2^32 possible values.

For identity hash code (availble from System.identityHashCode), objects move around in memory on many modern JVM implementations. There is no reasonable way of keeping track of which hash codes are still in use. Even with a (thread-safe) counter, after 2^32 allocations there will need to be some kind of reuse.

---

Related Topics