how does the remove method work for sets and hashsets

[haridharna]

Hello,
I am hari a resident of india.
I have been to this form many times. but this is my first posting.

I have a little confusion with the remove method of Set and HashSet.
Can any one tell me how does this method work exactly.
See the code and the result given below. I am confused aboud when the hashcode and the equals methods will be called.

Code:

import java.util.*;

class KeyMaster {
	public int i;

	public KeyMaster(int i) {
		this.i = i;
	}

	public boolean equals(Object o) {
		System.out.println("equal:"+ (i == ((KeyMaster) o).i));
		return i == ((KeyMaster) o).i;
	}

	public int hashCode() {
		System.out.println("Hashcode:"+i);
		return i;
	}
	
	public String toString() {
		return ""+i;
	}
}

public class MapIt {
	public static void main(String[] args) {
		Set<KeyMaster> set = new HashSet<KeyMaster>();
		KeyMaster k1 = new KeyMaster(1);
		KeyMaster k2 = new KeyMaster(2);
		set.add(k1);
		set.add(k2);
		
		k1.i=2;
		set.remove(k1);
		System.out.println(set.contains(k2));
		System.out.println(set);
	}
}

The ouput for the above code is :
Hashcode:1
Hashcode:2
Hashcode:2
equal:true
Hashcode:2
false
[2]

Code:

public class MapIt {
	public static void main(String[] args) {
		Set<KeyMaster> set = new HashSet<KeyMaster>();
		KeyMaster k1 = new KeyMaster(1);
		KeyMaster k2 = new KeyMaster(2);
		set.add(k1);
		set.add(k2);
		
	//	k1.i=2;
		set.remove(k1);
		System.out.println(set.contains(k2));
		System.out.println(set);
	}
}

if we comment the k1.i=2 the following is the output.
Hashcode:1
Hashcode:2
Hashcode:1
Hashcode:2
true
[2]
---------------

Code:

public class MapIt {
	public static void main(String[] args) {
		Set<KeyMaster> set = new HashSet<KeyMaster>();
		KeyMaster k1 = new KeyMaster(1);
		KeyMaster k2 = new KeyMaster(2);
		set.add(k1);
		set.add(k2);
		
		k1.i=2;
		set.remove(k1);
		System.out.println(set.contains(k1));
		System.out.println(set.contains(k2));
		System.out.println(set);
	}
}

for the above code the following is the output:

Hashcode:1
Hashcode:2
Hashcode:2
equal:true
Hashcode:2
false
Hashcode:2
false
[2]

I am confused with when the equals method will be called and why the contains method is giving false.

[brianhks]

A little intro to Hash tables: When inserting an object into a hashtable the hash code is retrieved from that object. Based on the hash code the object is placed in one of several buckets. (the number of buckets varies) The bucket is just a linked list of objects. Now when trying to find an object the hash code is used to locate the bucket and then the equals is called for each object in the bucket to find the exact match. So think of hash code as fuzzy match and equals() as exact match.

One thing you have done here is changed the hash code for an object. That should not be done once the object is placed within the hash table. The reason is you just change what bucket the object should be in without actually moving the object.

Also your equals is comparing the same as your hash code. This will not work well. Remember all objects in the same bucket have the same hash code and you can have multiple objects in a hash table that have the same hash code. The .equals() method is supposed to be able to tell them apart. In some of your examples you set k1 and k2 to have the same i value. Now you cannot tell them apart.

[haridharna]

Brainhks thanks for the reply.
But I still have some doubts.
1)-- In the above code, equals method is called sometimes and sometimes it is not called. Can you or any one tell the reason for that.
2)-- When I set K2.i =1 the equals method is called and when I set k2.i=2 or with some other number the equals method is not called.
3)-- When i call the contains method after removing k2 both set.contains(k2) and set.contains(k1) are returning false. why is it so even when there is a value in the hashset.
4)-- Is the result same for the Hashtable and HashSet both same.

[brianhks]

Hashtable, HashSet, HashMap; they all use a hash to store the objects.

Code:

k1.i=2;

Just so you understand, the above line of code is evil. You are changing the hash value of an object that has already been placed in the Set. If you place an object in a HashSet and then change its hash code the object will get lost. Because later when you try to remove it the HashSet will go looking in the wrong bucket for the object and not find it.

Equals is only called if the bucket into which the object is being placed already contains an object. Now as for why equals is called intermittently. My suspicion is that when comparing objects they first use the '=' to see if they are in fact the same object before calling .equals(). Notice that the equals is only called when you change the value of k1 to equal k2 and then try to remove k1. Because k1 has the value of k2 it will remove k2 from the Set but k1 = k2 is not true so it will call k1.equals(k2).

[haridharna]

Thank you for the reply Brianhks.