Why is the hashCode method usage of HashSet not specified in the API?

Question

I was trying to debug my code which uses a HashSet and searching through the SO, I found out that I needed to override the hashCode method as well. The strange part is, checking the related API, I did not see any part in it mentioning about the hashCode method. Quoting the definition of the add method of HashSet as seen in the API:

public boolean add(E e)

Adds the specified element to this set if it is not already present. More formally, adds the specified element e to this set if this set contains no element e2 such that (e==null ? e2==null : e.equals(e2)). If this set already contains the element, the call leaves the set unchanged and returns false.

Now in the quotation above, I don't see anywhere that mentions about the hashCode method. Shouldn't the correct statement have been like:

... if this set contains no element e2 such that (e==null ? e2==null : e.equals(e2)) AND if this set contains no element e2 such that (e==null ? e2==null : e.hashCode() == e2.hashCode()).

Now if you say that: "If o1.equals(o2) returns true, o1.hashCode() == o2.hashCode() MUST evaluate to true as well.", then I would ask three questions:

1. Where is that fact specified? (in general, or in the API)

2. Even if that fact is specified somewhere, where in the API it is specified that HashSet makes use of the hashCode method?

3. If that fact is indeed correct, why isn't the compiler enforces overriding the hashCode method, whenever the equals method is overridden?

Answer 1

1. in the documentation of hashcode itself:

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.

2. not that I can find, but hashcode is specifically there for the support of hash tables as said in the documentation.

Answer 2

The specifics of the hashCode in the API is a few steps deep from HashSet:

• HashSet See also -> HashMap ("This class implements the Set interface, backed by a hash table (actually a HashMap instance).")
• HashMap See also: -> Object.hashCode()
• Object#hashCode()

There, it reads:

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 compiler doesn't know or care about the relationships between objects or methods. On the other hand, there are several static analysis tools that do care:

Findbugs Class defines equals() but not hashCode():

This class overrides equals(Object), but does not override hashCode(). Therefore, the class may violate the invariant that equal objects must have equal hashcodes.

Findbugs Class defines equals() and uses Object.hashCode()

This class overrides equals(Object), but does not override hashCode(), and inherits the implementation of hashCode() from java.lang.Object (which returns the identity hash code, an arbitrary value assigned to the object by the VM). Therefore, the class is very likely to violate the invariant that equal objects must have equal hashcodes.

If you don't think instances of this class will ever be inserted into a HashMap/HashTable, the recommended hashCode implementation to use is:

public int hashCode() {
    assert false : "hashCode not designed";
    return 42; // any arbitrary constant will do
}

PMD OverrideBothEqualsAndHashcode

Override both public boolean Object.equals(Object other), and public int Object.hashCode(), or override neither. Even if you are inheriting a hashCode() from a parent class, consider implementing hashCode and explicitly delegating to your superclass.

CheckStyle EqualsHashCode

Checks that classes that override equals() also override hashCode().

Rationale: The contract of equals() and hashCode() requires that equal objects have the same hashCode. Therefore, whenever you override equals() you must override hashCode() to ensure that your class can be used in hash-based collections.

Some IDEs may also have built in static analysis tools or generators to create equals and hashcode - sometimes as part of the same step (these are the fields of interest - poof there's the code).

Answer 3

... if this set contains no element e2 such that (e==null ? e2==null : e.equals(e2)) AND if this set contains no element e2 such that (e==null ? e2==null : e.hashCode() == e2.hashCode()).

The above statement is not correct. It is and should be possible to add an object e1 to a HashSet or a Set in general, where the set contains an element e2, which fulfills e1.hashCode() == e2.hashCode() && e1.equals(e2) == false.

You can easily create examples for this: Imagine a class Person with the attributes name, surname and resident city. The equals method compares all attributes and the hashCode method uses the hash code of the resident city. The contract of equals and hashCode is fulfilled, but with the above contract of add, it would not be possible to add to persons to a set, that live in the same city.

The documentation of HashSet does not explicitly state the use of the method hashCode (I would consider that a implementation detail. The important thing you need to know is, that HashSet fulfills the contract of Set). However there is a hint in the documentation:

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets.

Answer 4

1. Where is that fact specified? (in general, or in the API)

It is specified clearly in the documentation of the .equals() 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.

You overrode the .equals() method without looking at the documentation of the method you were overriding, and you broke its requirements.

2. Even if that fact is specified somewhere, where in the API it is specified that HashSet makes use of the hashCode method?

It doesn't need to be specified anywhere. .hashCode() is a method on Object and thus all objects have it. Any class is allowed to make use of it.

That HashSet uses .hashCode() is an implementation detail, not part of its API. The API of HashSet is basically the same as the API of the Set interface which it implements. HashSet does not add any additional requirements on the type, any more than Set does. The Set contract make sure that there are no two .equals() elements in the set, and the lookup methods lookup using .equals(). HashSet does the same. HashSet uses .hashCode() as part of doing those operations, but it should be able to safely do so because .hashCode() is supposed to be consistent with .equals() as part of the contract of .equals().

3. If that fact is indeed correct, why isn't the compiler enforces overriding the hashCode method, whenever the equals method is overridden?

There is no mechanism in the language to enforce this.

Answer 5

Absent an explicit promise not to do so, any equality-based collection is allowed to use hashCode if so inclined to quickly decide that things don't match (note that sorted collections which regard items of equal rank as matching would not be allowed to do so, since items may have equal rank and yet be unequal). Further, there is no guarantee that hash-set implementations will always call hashCode. It would be legitimate to have a hashSet implementation which didn't bother calling hashCode on anything until they contained some number of items. This could be useful in some nested-collection contexts which produce many collection instances that never get very many items added. Thus, the name hashSet basically says performance will be tied to the quality of the hash function, but that doesn't mean its' the only thing that can or will use it.