hashing

[vini singh]

why is it required to override equals or hashCode method for hashing


please explain

[Himanshu Gupta]

Vini please explain that what do you mean by hashing?

[vini singh]

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]

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]

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]

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]

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?

public int hashcode()
 {
    int strLength=theString.length();
    if(strLength<3)
      {
        return 1; //put in bucket One
      }
    else if(strlength()>=4&&strLength<=8)
     {
        return 2; //put in bucket Two
     }
   else
     {
        return 3; //put in bucket Three
      }
 }

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é]

public int hashcode()

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

[Vishwanath Krishnamurthi]

Oops! hashCode 'feels' like one word