Necessity to override both equals() and override() methods

[Paari Lenin]

Hi,

I have a doubt about overriding hashcode() and equals().

I understand the need to override hashcode() separately and equals() separately.


But I don't understand the contract that if i override equals() i should also override hashcode(). I understand it like if I don't maintain the contract then I will have a performance hit( or the purpose of hashing becomes useless) but how is that that I wont be able to find the element put into the hashtable if I don't override hashcode() method also.

Can somebody explain me please ?

I am going through Kathy sierra book and I am bit confused about this?

[Anonymous]

Hi Paari,

To understand this concept, you might have already read the bucket example given in K&B book. In that every bucket would have an id and that id is nothing but our hashcode. Now coming to the point of relation between equals and hashCode. Its absolutely not a mandatory to over hashCode if equals is overriden. But, imagine we have equals overriden , but not hashCode. Let the default hashCode be given to all the objects (hashCode implemention in Object class). Then all the objects we create would land into a same bucket. Now the problem comes while searching which is a two step process, that is first find out the right bucket and with in the bucket find the right object. This is one of the optimal solutions for searching. Nothing would stop us to implement our own algorithm.
Then while searching, for every object we search, we would be pointing to the same bucket (Due to same hashcode) and with in that bucket we need to search for the actual object using equals traversing all the un wanted objects. So if we implement hashCode in an optimal fashion such that objects are distributed evenly, then our search time drastically comes down. Hope I made a point here.

[Burkhard Hassel]

Howdy Paari,

welcome to the Ranch!




When hashCode is valuated in the way that equal objects have different hashCodes, it may happen that a Set accepts two equal objects. What it shouldn't do.
Say you have:

class BadHash {
int value1;
int value2;
int value3;
BadHash(int one, int two){
this.value1=one;
this.value2=two;
value3 = (int) (Math.random() * 100);
}
// appropriate equals()
@Override
public boolean equals(Object o){
if(! (o instanceof BadHash) )
return false;
BadHash that = (BadHash) o;
return (that.value1==this.value1 
&& that.value1==this.value1);
}

// bad hash may return different values
// on equal objects.
@Override
public int hashCode() {
return value1 * value2 * value3;
}
 
@Override
public String toString() {
return "BadHash " + value1 + "-" + value2;
}
 
}

You use it in

import java.util.*;
public class BadHashUser {
public static void main(String[] args) {
Set<BadHash> set = new HashSet<BadHash>();
BadHash one = new BadHash(1,2);
BadHash two = new BadHash(1,2);
System.out.print  ("one.equals(two): "); 
System.out.println(one.equals(two));
set.add(one);
set.add(two);
System.out.println(set);
}
}

The set method add() relies on a propper hashCode, the hashCode is different, so the equals test is omitted and as a result you get a set with two equal objects.
Output is
one.equals(two): true
[BadHash 1-2, BadHash 1-2]

So this is really more than just a performance thing.


The same would happen if you don't override hashCode at all, because then Object's hashCode method would return a different hashCode for (almost) every BadHash object.



Yours,
Bu.

[Anonymous]

My update before

Hi Paari,

To understand this concept, you might have already read the bucket example given in K&B book. In that every bucket would have an id and that id is nothing but our hashcode. Now coming to the point of relation between equals and hashCode. Its absolutely not a mandatory to over hashCode if equals is overriden. But, imagine we have equals overriden , but not hashCode. Let the default hashCode be given to all the objects (hashCode implemention in Object class). Then all the objects we create would land into a same bucket. Now the problem comes while searching which is a two step process, that is first find out the right bucket and with in the bucket find the right object. This is one of the optimal solutions for searching. Nothing would stop us to implement our own algorithm.
Then while searching, for every object we search, we would be pointing to the same bucket (Due to same hashcode) and with in that bucket we need to search for the actual object using equals traversing all the un wanted objects. So if we implement hashCode in an optimal fashion such that objects are distributed evenly, then our search time drastically comes down. Hope I made a point here.

the above one is wrong and I'm sorry for the wrong information.

[Paari Lenin]

Hi,

Nice to know that somebody takes the effort to clarify others doubts spending their precious time.

Thanks to Chandra Kota and Burkhard Hassel.


I think, now I have got it right. (corrections always welcome)

Reason 1:
As Burkhard Hassel said, we don�t want SETs to have meaningfully equal objects stored in our collection just because default hashCode says they are different objects.

Reason 2:

We use collections to store data and on a later date retrieve it back.

When (I don't override hashCode()) I store an element in a collection that uses hashing it will generate a unique hash and puts it in relevant bucket. Then when I want to retrieve it back I need to give something and whatever I give as my search criteria, the first thing the collection will do is take the newly generated hashCode(default) (not same as before and go to a different bucket) and then it will search for my object. It will not be found as the hashCode will be different for two different runs for the same object.

If I have overriden the hashCode based on data that is relavant or unique to the object, for different runs then it would still generate the same hashCode.

So it is mandatory to override hashCode for collections that use hashing.

Now after coming to the bucket there may be different objects with the same hashCode. Now to sort the exact match we cannot go with the default which also checks based on reference value. So we have to override the equals method also mandatorily.

Reason 3:

Another reason for maintaining the contract I believe is that, the default hashCode and equal method that comes with the API will be true for two equal objects which must not be changed when we override it in our programs.

Reason 4:
I have stored one object in collection. And in order to retrieve it (during the same execution) I am passing a meaningfully equal object (just as I have overriden my equals method to consider two objects to be equal). Now if I have not followed the contract my hashcode will be different for these two meaningfully equal object. So I will not have a successful search in collections that use hashing.

Rgds,

Paari.

[Ajay Divakaran]

I thought the default hashCode() returns a unique number for each object created?

[Paari Lenin]

Did any of the above explanations made you think otherwise that hashCode doesn't generate a unique code everytime.

[Anonymous]

Until Burkhard explained the way it works, I was also under an impression that hashCode() returns the same unique number for every object as its only the Object's method being called .. But now I believe it would not and we have to provide correct implementation for a better performance.

Thanks to Burkhard

[Paari Lenin]

hi, Burkhard Hassel

Can you please clarify whether default hashcode() returns unique value for each object or is there a possibility for the default hashcode() to give duplicate values. I am confused now...

[Jesper de Jong]

The API documentation for Object.hashCode() says:

As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects. (This is typically implemented by converting the internal address of the object into an integer, but this implementation technique is not required by the JavaTM programming language.)

So: It should return unique numbers for different objects, but there is no guarantee that it does.