• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

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

 
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?
 
Ranch Hand
Posts: 18944
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 1274
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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:


You use it in

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
Ranch Hand
Posts: 18944
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Greenhorn
Posts: 22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I thought the default hashCode() returns a unique number for each object created?
 
Paari Lenin
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Did any of the above explanations made you think otherwise that hashCode doesn't generate a unique code everytime.
 
Anonymous
Ranch Hand
Posts: 18944
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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...
 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic