Why is equals() not called while adding to HashSet and hashCode matches?

Question

When I run this code why only hashCode() is called not equals method while my hashCode() implementation generate same hashCode for both entries to HashSet?

import java.util.HashSet;

public class Test1 {
    public static void main(String[] args) {
        Student st=new Student(89);
        HashSet st1=new HashSet();
        st1.add(st);
        st1.add(st);
        System.out.println("Ho size="+st1.size());
    }
}
class Student{
    private int name;
    private int ID;
    public Student(int iD) {
        super();
        this.ID = iD;
    }
    @Override
    public int hashCode() {
        System.out.println("Hello-hashcode");
        return ID;
    }
    @Override
    public boolean equals(Object obj) {
        System.out.println("Hello-equals");
        if(obj instanceof Student){
            if(this.ID==((Student)obj).ID){
                return true;
            }
            else{
                return false;
            }
        }
        return false;  
    }
}

The output for this is:

Hello-hashcode
Hello-hashcode
Ho size=1

Answer 1

The hash set checks reference equality first, and if that passes, it skips the .equals call. This is an optimization and works because the contract of equals specifies that if a == b then a.equals(b).

I attached the source code below, with this check highlighted.

If you instead add two equal elements that are not the same reference, you get the effect you were expecting:

    HashSet st1=new HashSet();
    st1.add(new Student(89));
    st1.add(new Student(89));
    System.out.println("Ho size="+st1.size());

results in

$ java Test1
Hello-hashcode
Hello-hashcode
Hello-equals
Ho size=1

---

Here's the source code from OpenJDK 7, with equality optimization indicated (from HashMap, the underlying implementation of HashSet):

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
//                                         v-- HERE
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

Answer 2

A HashSet uses a HashMap as its backing mechanism for the set. Normally, we would expect that hashCode and equals would be called to ensure that there are no duplicates. However, the put method (which calls a private putVal method to do the actual operation) makes an optimization in the source code:

if (e.hash == hash &&
    ((k = e.key) == key || (key != null && key.equals(k))))

If the hash codes match, it first checks to see if the keys are the same before calling equals. You are passing the same Student object, so they are already ==, so the || operator short-circuits, and equals is never called.

If you passed in a different Student object but with the same ID, then == would return false and equals would be called.

Answer 3

Looking through the source code of HashSet it is using HashMap for all of its operations and the add method performs put(element, SOME_CONSTANT_OBJECT). Here is the source code for the put method for JDK 1.6.0_17 :

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

as you can see it performs a == comparison before using the equals method. Since you are adding the same instance of an object twice the == returns true and the equals method is never called.

Answer 4

Equals is always called after the hashCode method in a java hashed collection while adding and removing elements. The reason being, if there is an element already at the specified bucket, then JVM checks whether it is the same element which it is trying to put.

hashcode() and equals() method

Answer 5

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.