HashSet allows duplicate item insertion if hashCode() is not overridden

Question

class temp {
int id;

public int getId() {
  return id;
}

temp(int id) {
  this.id = id;
}

public void setId(int id) {
  this.id = id;
}

@Override
public boolean equals(Object obj) {
  if (this == obj)
      return true;
  if (obj == null)
      return false;
  if (getClass() != obj.getClass())
      return false;
  temp other = (temp) obj;
  if (id != other.id)
      return false;
  return true;
}
}

public class testClass {

    public static void main(String[] args) {
      temp t1 = new temp(1);
      temp t2 = new temp(1);
      System.out.println(t1.equals(t2));
      Set<temp> tempList = new HashSet<temp>(2);
      tempList.add(t1);
      tempList.add(t2);
      System.out.println(tempList);
}

The program adds both the elements to the Set. I was shocked at first because while adding methods to set, equals method is invoked.

But then I overrode the hashCode method:

@Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + id;
        return result;
    }

And then it did not add. This is surprising as the Javadoc of Set and add() method says that it checks only equals() while adding into the Set.

And this is the javadoc for add():

/**
     * Adds the specified element to this set if it is not already present.
     * More formally, adds the specified element <tt>e</tt> to this set if
     * this set contains no element <tt>e2</tt> such that
     * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
     * If this set already contains the element, the call leaves the set
     * unchanged and returns <tt>false</tt>.
     *
     * @param e element to be added to this set
     * @return <tt>true</tt> if this set did not already contain the specified
     * element
     */
    public boolean add(E e) {
      return map.put(e, PRESENT)==null;
    }

Then I realized that the HashSet is implemented as a HashMap and in the map, the hashCode of the object is used as the key. So, it is treating them using different keys if you dont override hashCode.

Shouldn't this be in the documentation of the add() method or that of HashSet?

Answer 1

It kind of is documented. See the documentation for java.lang.Object, where it says on hashCode():

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.

Additionally the following is found in the documentation for the Object.equals(Object) method:

Note that it is generally necessary to override the hashCode method whenever this method is overridden, so as to maintain the general contract for the hashCode method, which states that equal objects must have equal hash codes.

In other words, if with your class when instanceA.equals(instanceB) == true and instanceA.hashCode() != istanceB.hashCode() you are in fact violating the contract of the Object class.

Answer 2

Just take a look also at equals() documentation:

Note that it is generally necessary to override the hashCode method whenever this method is overridden, so as to maintain the general contract for the hashCode method, which states that equal objects must have equal hash codes.

The fact is that equals() and hashCode() are strongly linked. Both should always be considered when working with one of them to avoid these consistency issues.

Answer 3

If you override equals() you must override hashCode() as well.

There are some restrictions placed on the behavior of equals() and hashCode(), which are enumerated in the documentation for Object. In particular, the equals() method must exhibit the following properties:

• Symmetry: For two references, a and b, a.equals(b) if and only if b.equals(a)
• Reflexivity: For all non-null references, a.equals(a)
• Transitivity: If a.equals(b) and b.equals(c), then a.equals(c)
• Consistency with hashCode(): Two equal objects must have the same hashCode() value

See this for more details.