Understanding HashSet

Question

Well here is my question, Can "HashSet Objects" have elements duplicated??

If I read the Set Interface definition, I see:

A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.

And now we are going to write a simple example:

Define class A:

public class A {

    @Override
    public boolean equals(Object obj) {
        return true;
    }

}

Now execute this code;

Set<A> set = new HashSet<A>();
set.add(new A());
set.add(new A());
System.out.println(set.toString());

And this is the result:

[com.maths.graphs.A@b9e9a3, com.maths.graphs.A@18806f7]

Why a class what implements Set Interface like HashSet contains elements duplicated?

Thanks!!

Answer 1

You have broken the equals-hashcode contract.

If you override the equals method you must also override the hashCode() method such that:

Two objects which are equal give the same hash, and preferably unequal objects are highly likely to give different hashcodes

This is important because many objects (unsurprisingly including the HashSet) use the hashcode as a quick, efficient early step to eliminate unequal objects. This is what has happened here since the hashcodes of the different As will be different as they are still using the implementation of .hashCode() provided within object.

If you were to create the class A as follows it would not allow more than 1 A in the set

public class A {

    @Override
    public boolean equals(Object obj) {
        return true;
    }

    @Override
    public int hashCode() {
        int hash = 1; //any number since in this case all objects of class A are equal to everything
        return hash;
    }

}

From the javadoc

public int hashCode()

Returns a hash code value for the object. This method is supported for the benefit of hash tables such as those provided by HashMap.

The general contract of hashCode is:

• Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.

• If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.

• It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.

Most IDEs will object if you do not include an overriding HashCode method when overiding the equals method and can generate a hashCode method for you.

Notes

Strictly speaking my hashCode() method doesn't completely satisfy the contract. Since A#equals(Object obj) equals anything including objects which are not of type A it is impossible to fully satisfy the contract. Ideally the equals method would be changed to the following as well to cover all bases

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof A){
           return true;
        }else{
           return false;
        }
    }

Answer 2

Here the HashSet does not have duplicates, as the two add methods add new objects in the HashSet and these are different Objects. The reason that the hash codes for the two elements of the set are different for this reason. Try changing the code to:

Set<A> set = new HashSet<A>();
A a = new A();
set.add(a);
set.add(a);
System.out.println(set.toString());

and you will see that there is only one value in the set.

Or just add the following in you code and check

@Override
public int hashCode() {
    return 31;
}

Answer 3

You have violated the hashCode() method contract i.e for same key it should return same hashcode() every time