hashtable working & overriding equals

[rajaraman navaneethan]

hi friends,
thanx for the tremendous response for clearing my earlier doubt in string-pool.expecting similar responses from u all,i m posting yet another question and its regarding hashtable working.

we know that hashtable stores values as key/value pairs,where both key and value should b an object.

considering this code,

class car
{
int vehnum;
int yearofmake;

public static void main(String args[])
{
car ob1=new car();
car ob2=new car();

Hashtable hs=new Hashtable();

hs.put(ob1,"Raja");
hs.put(ob2,"Alps");
hs.put(ob1,"Rahi");

String s=(String)hs.get(ob1);
System.out.println(s);
}//end of main

}// end of class car

now the o/p obtained is Rahi.i understand why is it so.as i have reffered the key ob1 for Rahi at last.

i want to know how the hashtable retreives the data,and how can i override equals() method,so that key/value pair is unique.

please give thw way as how i should override the equals() method to make my code more efficient.

[ankur rathi]

i want to know how the hashtable retreives the data

Hashing Technique :
-----------------

Suppose you want to store 1000 objects into HashMap or Hashtable ( or any data structure that is based on hashing technique ) . what this technique does is it put all object whose hashcode is equal into a sigle bucket ... so suppose you have :
first 200 obejcts has hashcode 1
then 500 obejcts has hashcode 2
then last 300 objects has hashcode 3

So there will be 3 buckets of hashcode 1, 2 & 3 respectively & first bucket will have 200 objects , second will have 500 & third will have 300 objects .

At the time of searching any object , what happens is , first JVM retrieves the hashcode of object then find bucket & then with the help of equals method it find the actual object .

------------------------------------------------------
1] So if your hashcode() method implementation is like it is giving same hashcode for every object then your HashMap will work like List ( it will take time in searching )

hope everything is right & clear .

[Ajay Bhargov]

Hi,

Tnx for ur wonderful reply...

Can u just go into detail regarding the hashcode,the importance of it in Hashtable and as to how the hashcode is calculated given a particular object. Can you explain to me by taking an example..

[sri rallapalli]

1] So if your hashcode() method implementation is like it is giving same hashcode for every object then your HashMap will work like List ( it will take time in searching )

do we need to implement hashcode() every time when we want to use HASHING.
how can we implement this method in such a way that we should give different value for each object.

[ankur rathi]

class Hash {
 
    public int hashCode() {
         return 1;
    }
 
}

This is legal but not appropriate use of hashCode() method because every object will be stored in the same bucket ...


One more thing about hashcode is if two object are equal then their hash code must be same .

If two object having different hash code then they must not be equal .


The following is not appropriate implementation of either hashCode() or equals() method ...

public class Hash {

public static void main(String[] args) {

Hash h1 = new Hash();
Hash h2 = new Hash();

HashMap hm = new HashMap();
hm.put(h1,"first");
hm.put(h2,"second");

System.out.println(hm.get(h1));
System.out.println(hm.get(h2));

}

public boolean equals(Object o) {
return false;
}

public int hashCode() {
return 1;
}
}
 
output :
null
null
 

public class Hash {

public static void main(String[] args) {

Hash h1 = new Hash();
Hash h2 = new Hash();

HashMap hm = new HashMap();
hm.put(h1,"first");
hm.put(h2,"second");

System.out.println(hm.get(h1));
System.out.println(hm.get(h2));

}
}
 
output :
first
second
 

[ March 23, 2005: Message edited by: rathi ji ]

[Ajay Bhargov]

Hi rathi,

Tnx for ur reply....

I hve some questions regarding ur reply..

public class Hash {public static void main(String[] args) {Hash h1 = new Hash();Hash h2 = new Hash();HashMap hm = new HashMap();hm.put(h1,"first");hm.put(h2,"second");System.out.println(hm.get(h1));System.out.println(hm.get(h2));}public boolean equals(Object o) {return false;}public int hashCode() {return 1;}} output :nullnull

So according to the definition of ur hashcode method it should return the same hashcode for all the objects and therefore all the objects that u hve created will be stored in the same bucket. So the hashtable behaves like a list.

In ur earlier reply u had posted that

At the time of searching any object , what happens is , first JVM retrieves the hashcode of object then find bucket & then with the help of equals method it find the actual object .

if we cross check to the code that u hve written

when the compiler encounters the line "System.out.println(hm.get(h1));".... it first computes the hashcode of h1 and according to the above code it should return 1. So once it gets the hashcode it goes to that particular bucket in the hashtable,but according to the above code it gets 2 key-value pairs. One is "h1, first" and the second one is "h2, second".So from here how does the equals method help us in getting the desired object.

Think that the above particular code works properly...

Do plz reply to my question.

[Animesh Shrivastava]

if we cross check to the code that u hve written

when the compiler encounters the line "System.out.println(hm.get(h1));".... it first computes the hashcode of h1 and according to the above code it should return 1. So once it gets the hashcode it goes to that particular bucket in the hashtable,but according to the above code it gets 2 key-value pairs. One is "h1, first" and the second one is "h2, second".So from here how does the equals method help us in getting the desired object.

Think that the above particular code works properly...

Ajay,
When doing a get() on Hashtable what happens is that:
1) first it searches for the bucket where the item is stored, so executing the code u get the exact place where the item is stored.
2) After getting the bucket, it executes the following condition:

  
    if (<The hash value stored is same as u r searching for> [B] and [/B])
        < The value stored is equal to the value searching for> :wink:  {
         <Now get the item>
    }
    
   

So now even though the first condition of ur if statement is true the second one returns false because equals returns false in ur code.
So u get null as the result.

Hope thats clear now.

[Animesh Shrivastava]

Rathi,
I guess the hashtable stores the data but u cannot retrieve it because of the get method implementation as i have shown in my previous post.

[Ajay Bhargov]

Hi Animesh,

Tnx for ur reply....

I still hve one question...

Say in the code for equals method i return true then would the get methokd retrieve the object and if so which one would it retrieve because the hashcode value is same for all the objects.

Do comment on this...

[Animesh Shrivastava]

Ajay,
When ur equals method returns true,
The values will be overridden and u will get the last one stored.
For ur code: the result would be

 
System.out.println(hm.get(h1));
System.out.println(hm.get(h2));
 

It would give the result as "Second" for both the SOPs
For more info on storage in a hashtable go thru the code for Hashtable
Its explained well.

[ankur rathi]

yes .
sorry , something was wrong in my post . I have edited that .
Thanks .

[Ajay Bhargov]

Hi guys,

Can 2 unequal objects hve there hashcode same...

Say I override the hashcode method such that it gives the same hashcode for all the objects stored in the hashtable, but their contents are different. Is this situation valid ???

Do comment on this

[Ajay Bhargov]

Hi Animesh,

I hve some questions for you...

1> Can u just brief me abt the organization of the hashtable??

2> Is it possible for 2 or more objects to have the same hashcode???

3> Say if two or more objects have the same hashcode, then is it necessary for their equal methods to return true???

4> Say i overide the hashcode method is it must for me to override the equals method???

[ankur rathi]

Can 2 unequal objects hve there hashcode same...

Yes .

Is it possible for 2 or more objects to have the same hashcode???

Yes .

Say if two or more objects have the same hashcode, then is it necessary for their equal methods to return true???

No .

---------------
1] if two object are equal then their hash code must be same .

2] If two object having different hash code then they must not be equal .
[ March 23, 2005: Message edited by: rathi ji ]

[Animesh Shrivastava]

Ajay,

Can u just brief me abt the organization of the hashtable??

Rathi, in his previous post, has very well explained u about the way hashing works and how the data gets stored in a hashtable. Are u getting confused anywhere, do post it.
Remember these points:
By Rathi:

1] if two object are equal then their hash code must be same .

2] If two object having different hash code then they must not be equal .

In addition to that,
3] If two objects are unequal its not necessary that their hashcodes are not equal, they may be equal as well.

4> Say i overide the hashcode method is it must for me to override the equals method???

See there is a contract which says that "equal objects should have equal hashcodes"
So suppose by overriding the hashcode if u get different results for two equal objects, u r violationg the contract. So, better we should avoid doing it.
U may not see such cases where u override equals because u have overridden hashcode. But u will find cases where u override hashcode because u have overridden equals. This can be viewed in the equals method of String class. There hashCode() method has been overridden to suit the requirements of equals method.

I hope its clear
[ March 24, 2005: Message edited by: Animesh Shrivastava ]

[Ajay Bhargov]

Hi

Tnx a lot for the reply...