5

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?

  • 8
    The HashSet documentation does not, technically, need to specify that hashCode: The contract that equality implies equal hash codes is a general contract on Object#hashCode, so it applies to all objects. All code is within its rights to use hashCode and assume that contract holds. That said, given that many beginners do not read that part of the documentation, and that many other resources felt the need to mention it explicitly, it certainly would be more useful if the JavaDoc highlighted this aspect. – user7043 Dec 6 '14 at 23:42
8
  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.
  1. not that I can find, but hashcode is specifically there for the support of hash tables as said in the documentation.
  • (1) Thanks. By the way, although it is stated that: > Returns a hash code value for the object. This method is supported for > the benefit of hash tables such as those provided by HashMap. shouldn't the API be explicitly specifing the usage of the hashCode method everywhere it is used? From the given quote, I can guess that hashCode is used in "every class that bears the word hash in its name", but I cannot be sure, right? I mean, shouldn't the API be explicitly specifing the usage of the hashCode method everywhere it is used to be more precise? – Utku Dec 7 '14 at 7:55
  • (2) To me, this looks like not specifying the usage of equals method in definitions of, say contains methods. I can guess that some sort of comparison mechanism is used. I can even guess that that comparison mechanism is the (optionally) overridden equals method but I can never be sure that the comparison mechanism used is really the (optionally) overridden equals method. Isn't that right? – Utku Dec 7 '14 at 7:55
3

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).

enter image description here

  • (1) Thanks. By the way, although it is stated that: > Returns a hash code value for the object. This method is supported for > the benefit of hash tables such as those provided by HashMap. shouldn't the API be explicitly specifing the usage of the hashCode method everywhere it is used? From the given quote, I can guess that hashCode is used in "every class that bears the word hash in its name", but I cannot be sure, right? I mean, shouldn't the API be explicitly specifing the usage of the hashCode method everywhere it is used to be more precise? – Utku Dec 7 '14 at 7:53
  • (2) To me, this looks like not specifying the usage of equals method in definitions of, say contains methods. I can guess that some sort of comparison mechanism is used. I can even guess that that comparison mechanism is the (optionally) overridden equals method but I can never be sure that the comparison mechanism used is really the (optionally) overridden equals method. Isn't that right? – Utku Dec 7 '14 at 7:54
  • @Utku where are you going to use it? Its used for HashMap... but, I've used it in other situations too. I also use equals a lot and I need to make sure if someone else puts my object in a HashMap without my knowledge, it works too. Other times, I don't care about equals other than the identity and thus don't care about hashCode either - so I don't need to add code I don't care about. – user40980 Dec 8 '14 at 2:38
  • @Utku as for contains and equals, the default equality is identity - if it's the same object, its equals; if not not equal. But you can define equality any way you want (you could have it be based on the id field of a record and forget all that other stuff). Using == for anything other than primitive types in Java is only rarely done. Beyond that, this is starting to diverge from the question and answer and I would urge you to stop by Software Engineering Chat (The Whiteboard) some time and ask for some more clarification on this. – user40980 Dec 8 '14 at 2:42
2

... 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.

1
  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.

  1. 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().

  1. 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.

  • +1 for a nice explanation. As to HashSet using .hashCode(), I haven't looked at the HashSet source, but I suspect it doesn't, rather that it uses .equals(). And APIs almost never specify what the APIs they use use. – Ross Patterson Dec 9 '14 at 13:18
  • @RossPatterson: Well, it has to use .hashCode(), because the point of using HashSet is that it has average-case constant complexity for lookup, insertion, and deletion. And that is only possible if it uses .hashCode() for a hash table. – user102008 Dec 9 '14 at 19:18
  • Just checked the HashSet source. It doesn't use either .hashCode() or .equals(). HashSet.add() defers all of its processing to HashMap.put(). HashMap.put(), though, uses both of them, and in fact, doesn't say so! – Ross Patterson Dec 10 '14 at 0:46
  • @RossPatterson: Right, because sets and maps are analogous and can be implemented in terms of one another. – user102008 Dec 10 '14 at 9:33
0

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.

protected by gnat Dec 30 '14 at 8:13

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.