hashcode and equals contract vice versa

Question

I know the contract says "if two objects are equal then they should return the same hash code". That is so that those objects can be place in the same hash bucket and to improve hash code related collection functions know. Then again why it says "if two objects have same hash code those should not always be equals". I mean if it is true in the contract we should say "if two objects are equals they may return same hash code but which is not mandatory"

Two identical apples should cost the same, that is 1 golden coin. However, two items costing 1 golden coin don't have to be identical apples. — Alexis Pigeon, Nov 26 '12 at 17:50

Rohit Jain · Accepted Answer · 2012-11-26T19:00:36.307

6

I mean if it is true in the contract we should say "if two objects are equals they may return same hash code but which is not mandatory"

No, it should not. This is because, whenever an object is searched let's say in a HashMap or a HashSet, then first it is searched on the basis of hashCode(NOTE : - hashCode() is not used for search in case of ArrayList, or LinkedList. They are not hash based collections), and then if the two objects have same hashcodes, it moves to the equals method to compare the objects themselves.

Now suppose if the above statement was true, the first test itself would fail for those objects. That is, if two equal objects are allowed to have different hashcode, then while searching for a particular hashCode, it won't return the correct result, and thus the test will not proceed to equals method, and declare those objects to be unequal even though you expected them to be equal.

Now lets move to the second statement: -

if two objects have same hash code those should not always be equals"

Let's understand like this: - Since hashCode generated for each object is of type int, so you can generate a maximum 2 ^ 32 unique hashcodes. So, imagine what would happen if you want to store more objects than that. In that case, there has to be a collison for two different objects. So, you would have no other way than to assign same hashCodes to two different objects. And hence the above statement is justified.

So, two things are quite clear from the above explanation: -

Two same objects must have same hashCodes.
Two different objects can have same hashCodes.

More details on this topic in the below link (Nothing can give better explanation than this): -

Effective Java - Override hashCode when you override equals

edited Nov 26 '12 at 19:00

answered Nov 26 '12 at 17:52

Rohit Jain

209,639
45
409
525

I have written a sample program to test what you mentioned. I only override the equals method for A but not the hash code. But below return true. Can you explain the how come the out put true retruns because i have never add a3 for the list and as you mentioned those objects have different hash codes and because of a3 hash code not found in list it should return false right? A a1 = new A(); a1.setName("a"); A a2 = new A(); a2.setName("a"); A a3 = new A(); a3.setName("a"); List list = new ArrayList(); list.add(a1); list.add(a2); System.out.println(list.contains(a3)); – FrankD Nov 26 '12 at 18:38
@HarshanaD.. Sorry for not mentioning that, `hashCodes` are not used for searching in case of `Lists`. It is used for Maps - `HashMap`, `LinkedHashMap`, `Hashtable` or, `HashSet`. That's why it worked. I have edited my answer accordingly. - My first part of the answer. – Rohit Jain Nov 26 '12 at 18:45
@HarshanaD.. Try using the same code but with `Set set = new HashSet ();`, instead of `ArrayList`. You would not get the true value for that. – Rohit Jain Nov 26 '12 at 18:49
yes it returns false in that case. So its like the collection set will check whether the hash code for a3 reside in that collection know. since those 3 objects have different hash codes it returns false even though the object state is equals. So if we make the hash code same for those object the set collection will directly go to a3 hash code bucket and check whether we have that object reside right? Is that the algorithm for find elements in the collection. First go to that hash code bucket and if it not found there iterate each element in the collection and check for hash code match? – FrankD Nov 27 '12 at 07:44
so once we override the hash code it return true for contains even though technically the object is not in that collection. But according to the contract of equals this behavior is right because contains needs to be check for similarity of the state of the object rather whether the object is physically something different know? – FrankD Nov 27 '12 at 07:47
@HarshanaD.. Yeah, it's like that only. And don't say `hash code bucket`. You should say, it first calculates the `hashcode` for each object in the Set and compare it with the `hashcode` of the object we want to search, and if the test succeeds, it moves on to `equals` method to compare them. – Rohit Jain Nov 27 '12 at 07:47
@HarshanaD.. Yeah exactly. The objects are technically not same. They are at different location. That is why if we compare them using `==`, we would get false result, as `==` compares the reference, and it returns false if the references point to different objects. But, to compare the contents of two objects, we use `overridden equals and hashcode` methods. – Rohit Jain Nov 27 '12 at 07:49
One point you have to correct this to be the perfect answer is, in hash collection if hash codes are equals then it return true even equals method return false. So the part of your answer "and then if the two objects have same hashcodes, it moves to the equals method to compare the objects themselves." is not correct know? Thank you – FrankD Jan 15 '13 at 09:07

score 5 · Answer 2 · answered Nov 26 '12 at 17:49

Nope. The docs are right, and you're getting mixed up.

Two objects that are equal must have the same hash code.
Two objects that have the same hash code might be unequal.
For the sake of hash table performance, you usually want two objects that are not equal to have different hash codes as often as possible.

For example, the following is always a valid implementation of hashCode():

public int hashCode() { 
  return 0;
  // clearly all equal objects have the same hash code -- 0
  // but it's totally okay that unequal objects also have the same hash code
}

score 2 · Answer 3 · answered Nov 26 '12 at 17:51

A HashMap can store multiple entries per bucket, and which bucket is chosen depends on the hashcode. The HashMap finds entries for a key by using the hashcode() to identify the bucket, and then equals() to find the matching key within that bucket.

Given the above, it should be clear that you can have duplicated hashcodes with little issue (it affects the performance of HashMaps if multiple objects have the same hashcode but everything will still work)

score 0 · Answer 4 · answered Nov 26 '12 at 17:50

If 2 identical hash codes had to come from the same object, than the hash wouldn't be as secure. it would be technically possible to figure what a password was based on the hash. this would undermine the purpose of hash codes(at least in the security sense.)

for non security hashing, if you could have every unique value make a unique hash, than you would have solved an unsolved computing problem.

score 0 · Answer 5 · answered Nov 26 '12 at 17:51

0

hash functions are usually

one way functions

: some input values (objects) may produce the same hashcode.

answered Nov 26 '12 at 17:51

AlexWien

28,470
6
53
83

hashcode and equals contract vice versa

5 Answers5

Linked