This week's giveaway is in the Android forum.
We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line!
See this thread for details.
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes hashing Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "hashing" Watch "hashing" New topic
Author

hashing

vini singh
Greenhorn

Joined: Dec 04, 2008
Posts: 18
why is it required to override equals or hashCode method for hashing


please explain
Himanshu Gupta
Ranch Hand

Joined: Aug 18, 2008
Posts: 598

Vini please explain that what do you mean by hashing?


My Blog SCJP 5 SCWCD 5
vini singh
Greenhorn

Joined: Dec 04, 2008
Posts: 18

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

Joined: Aug 18, 2008
Posts: 598

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

Joined: Oct 17, 2008
Posts: 165

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

Joined: Jan 06, 2006
Posts: 4
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

Joined: Jun 04, 2007
Posts: 331
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


Blog
Christophe Verré
Sheriff

Joined: Nov 24, 2005
Posts: 14687
    
  16

public int hashcode()

A common source of error is to misspell hashCode() with hashcode() ;)

[My Blog]
All roads lead to JavaRanch
Vishwanath Krishnamurthi
Ranch Hand

Joined: Jun 04, 2007
Posts: 331
Oops! hashCode 'feels' like one word
 
Don't get me started about those stupid light bulbs.
 
subject: hashing
 
Similar Threads
How to write a spell checker?
Encrypt / Decrypt 10 digit Number
Hashing
Encryption/decryption using core java and then insert into database
what is hashing and re-hashing?