Win a copy of Design for the Mind this week in the Design forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

hashing

 
vini singh
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
why is it required to override equals or hashCode method for hashing


please explain
 
Himanshu Gupta
Ranch Hand
Posts: 598
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Vini please explain that what do you mean by hashing?
 
vini singh
Greenhorn
Posts: 18
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

its said that in order to use object as a key in map we must override equals and hashCode method.i think this makes my question clear that why is it so.

 
Himanshu Gupta
Ranch Hand
Posts: 598
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
HashCode is an int. In hashMap this int is used to decide that in which location the Object will be stored. Once you store that Object based on the hashCode of the Key you can retrieve it back whenever you need.

Now when the Object is requested back again then you must specify the same key. The keys hashCode is again used to find the location of the Object. Once the location is determined the Object can be taken from their if it is there.


 
Bindu Lakhanpal
Ranch Hand
Posts: 171
Flex Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hashcode is overridden for HashMap uses the hashcode of objects to store them in buckets . If you don't override hashcode all objects go to different buckets and you won't be able to use HashMap for what it is good for i.e fast retrieval of objects.
Now if you don't override equal,you won't be able to find the object you are looking for cause by default equal returns true if object references are same.
So in order that the key you are using for searching eventually gets equated to the object which is same , you must override Equal.
Remember searching in hashmap is two step process:
1. Hashmap of the key is calculated and the right bucket is got.
2. Each object in bucket is checked with equal method for equality.
 
Brad Howerter
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The book is wrong. You don't have to override hashCode or equals; the default implementations in Object work just fine, so long as you understand that it's the object reference that is being compared when you do a retrieval. The book's own example can be used to demonstrate this, with a slight change. Change Dog to not override hashCode and equals and rerun the code - it prints the output exactly the same way. Line #4, m.get(d1), works because d1 is the original reference.

The books also claims that if you don't override hashCode and equals, you won't be able to find your stuff. This is wrong. If you still have the original key stored somewhere (like the d1 Dog in the example above), you can use it to find your stuff. It is true that you can't create a new object and use it to find your stuff. That's probably what the authors meant.
 
Vishwanath Krishnamurthi
Ranch Hand
Posts: 331
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Vini,

Just to add to what Bindu has said...

Say we have three buckets:

Bucket One: will hold all strings of length<3
Bucket Two: will hold strings of length ranging from 4 to 8
Bucket Three: will hold strings of length >8

Then the hashcode() method be doing?

now a get("hi") would look into bucket one and not bother to check others.

So we have basically created a formula for determining which bucket the object should go to, while Storing;
And while retrieving, this formula is used to check which bucket to search for.
If we hadn't done it ourseleves this way, the default int hashCode() generates a unique number for each object...
String s1=new String("language"); // say goes to 123 -(unique number generated)
and you put it as put(a,"english");
and later try
String s2=new String("language"); // hashes to 345 say -(unique number generated)
and get(s2);
s2 has got some other hashcode (ie 345) now, so would be looking in bucket 345!
It wouldn't find anything there!

So we have to disable the creation of unique number each time and make it use our custom logic.
Thats what overriding hashcode() does.

HTH,
Vishwa
 
Christophe Verré
Sheriff
Posts: 14691
16
Eclipse IDE Ubuntu VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
public int hashcode()

A common source of error is to misspell hashCode() with hashcode() ;)
 
Vishwanath Krishnamurthi
Ranch Hand
Posts: 331
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Oops! hashCode 'feels' like one word
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic