Behind HashSet

[Naresh Shanmugam]

When we use hashset

1. Bucket number will be computed using "hashcode" method
2. Check if already an element with same value using "equals" method

But in the below program

    
public class HashsetCheck {

	int i;
	HashsetCheck (int i)
	{
		this.i= i;
	}

	public boolean equals(Object obj) {
		System.out.println("In Equals Method");
		return (i == ((HashsetCheck)obj).i);
	}
	
	public int hashCode() {
		System.out.println("In Hashcode Method");
		return i;
	}
	
	public static void main(String[] args) {
		HashSet<HashsetCheck> a = new HashSet<HashsetCheck>();
		HashsetCheck obj = new HashsetCheck(2);
		HashsetCheck obj1 = new HashsetCheck(3);
		HashsetCheck obj2 = new HashsetCheck(4);
		a.add(obj);
		a.add(obj1);
		a.add(obj2);
	}
}

Every time i add a new object i am getting a message saying "In Hashcode Method" (boz i have that message in my overriden hashcode method) but i am not getting the message "In Equals Method"(which i have added in my overriden equals method). Does that mean equals method is not invoked???
Hope equals method would be invoked everytime an object is added...

[Henry Wong]

Naresh Shanmugam wrote:
Hope equals method would be invoked everytime an object is added...

Why? The equals / hashcode contract says that if two objects are equal, then the hashcodes must be equal. So, if two hashcode are not equal, why do you need to bother with calling the equals() method?

Henry

[Matthew Brown]

At the moment, this is what's happening:

- calculate the hashCode
- find the bucket
- the bucket is empty, so there's nothing to compare to

Try adding two HashsetChecks with the same value and see what happens.

[Campbell Ritchie]

Please don't write "boz" or similar.

[Naresh Shanmugam]

Thank you Henry and Matthew I got the point..

Sure Campbell i will follow that for sure..

[Naresh Shanmugam]

Now with the same code i showed above, i did this,

   
a.add(obj);
a.add(obj);

So for the first time the when "obj" is added

1. Hashcode method would have written a valid bucket number and since it is the new element "equals" method will not be invoked.

Now for the second time when the "obj" is added

1. Hashcode method will return the same bucket number, because this is the same object which we have added already, and now "equals method should have been called to check whether the same object is present",

But it is not called, any idea why it is not called Matthew and Henry??


Does that mean "hashcode" method does "equality check also???"

[Deepak Chopra]

Try this -

  
import java.util.HashSet;

 public class HashsetCheck {  
   
     int i; 
     String name = null;
     HashsetCheck (int i, String name)  
     {  
         this.i= i;
         this.name = name;
     }  
   
     public boolean equals(Object obj) {  
         System.out.println("Checking Equals Method while putting "+ this.name);  
         return (i == ((HashsetCheck)obj).i);  
     }  
       
     public int hashCode() {  
         System.out.println("In Hashcode Method "+ this.name);  
         return i;  
     }  
       
     public static void main(String[] args) {  
         HashSet<HashsetCheck> a = new HashSet<HashsetCheck>();  
         HashsetCheck obj = new HashsetCheck(2, "2");  
         HashsetCheck obj1 = new HashsetCheck(3, "3");  
         HashsetCheck obj2 = new HashsetCheck(2,"4");  
         a.add(obj);  
         a.add(obj1);  
         a.add(obj2);  
         System.out.println(a.size());
     }  
 }  
  

[Naresh Shanmugam]

 import java.util.HashSet;   

public class HashsetCheck {     
     
    int i;    
    String name = null;   
    HashsetCheck (int i, String name)     
    {     
        this.i= i;   
        this.name = name;   
    }     
     
    public boolean equals(Object obj) {     
        System.out.println("Checking Equals Method while putting "+ this.name+" in bucket "+ this.i);     
        return (i == ((HashsetCheck)obj).i);     
    }     
         
    public int hashCode() {     
        System.out.println("In Hashcode Method "+ this.name);     
        return i;     
    }     
         
    public static void main(String[] args) {     
        HashSet<HashsetCheck> a = new HashSet<HashsetCheck>();     
        HashsetCheck obj = new HashsetCheck(2, "2");     
        HashsetCheck obj1 = new HashsetCheck(3, "3");     
        HashsetCheck obj2 = new HashsetCheck(2,"4");     
        a.add(obj);     
        a.add(obj);     
        System.out.println(a.size());   
    }     
}     

In the above scenario i am trying to add same "obj" twice, on the same bucket. Second time it should have called "equals" method to check for the presence of the same element(because already elements exist on the same bucket), but it didnt invoke "equals" method !!! --- Does that mean hashcode does some part of equality checking??

[Campbell Ritchie]

Naresh Shanmugam wrote:Does that mean hashcode does some part of equality checking??

No.

You have to write your hashCode method to maintain the general contract for Object#equals(java.lang.Object) and Object#hashCode().

[Mike Simmons]

Naresh Shanmugam wrote:In the above scenario i am trying to add same "obj" twice, on the same bucket. Second time it should have called "equals" method to check for the presence of the same element(because already elements exist on the same bucket), but it didnt invoke "equals" method !!! --- Does that mean hashcode does some part of equality checking??

Sure, hashCode() can do "some part" of equality checking - but not all of it. You are correct to think that a HashSet must do something else to confirm that two objects are really equal. Usually, that means calling equals(). But there is a third possibility - call == first. That's a shortcut to skip calling equals() in some cases. If two references are really == to each other, then equals() must also return true. (Assuming a valid implementation.) If you look at the source code for HashSet, you can probably find a place where they do something like this

if (x == y || x.equals(y)) {
  ...
}

[Naresh Shanmugam]

Thank you so much for valuable words Mike..

[Deepak Chopra]

Naresh Shanmugam wrote:

In the above scenario i am trying to add same "obj" twice, on the same bucket. Second time it should have called "equals" method to check for the presence of the same element(because already elements exist on the same bucket), but it didnt invoke "equals" method !!! --- Does that mean hashcode does some part of equality checking??

It did not invoke...Well when i run it - I got this -

In Hashcode Method 2
In Hashcode Method 3
In Hashcode Method 4
Checking Equals Method while putting 4

[Campbell Ritchie]

But if you have written your equals() method well, it will look like this

/**
 * @see java.lang.Object.equals
 */
@Override
public boolean equals(Object obj)
{
    return this == other ||
    . . .
}

So it should incorporate the == test anyway.

Two objects with equal hashcodes are not necessarily equal to each other. Two objects with different hashcodes must not be equal to each other.

[Naresh Shanmugam]

I clearly understood the fundamentals now...
Thank you all for spending your valuable time..

[Campbell Ritchie]

Well done, and you're welcome