hashcode() and equals()

[rakesh sugirtharaj]

I can understand why hashcode has to be overrided each time equals is changed but where do these find their application other than Sets? :roll:

[Nitesh Kant]

Originally posted by rakesh sugirtharaj:
I can understand why hashcode has to be overrided each time equals is changed but where do these find their application other than Sets? :roll:

They will be used wherever some one uses a hash algorithm.
Theoretically, a hash is not universally unique. In hashing, wherever there is a hash collision (same hash for two entries) equals is checked to find whether the two entries are the same or not. If equals, does not return true then both the entries are kept under the same hash (popularly known as Bucket)
For further information, you can see wiki entry for hashing

[Rob Spoor]

hashCode() is also used in the toString() method of Object:

public String toString() {
    return getClass().getName() + "@" + Integer.toHexString(hashCode());
}

[Adeel Ansari]

Its not just about Set, but Collection, or better say where ever its about comparison or sorting. So, beside other things, now Array is also included.

Cheers.

[Matthew Walton]

Any Collection which has an internal implementation using hashes will need a decent implementation of hashCode() to be efficient. Fortunately most of them have 'Hash' in their classnames - HashMap, Hashtable, HashSet, LinkedHashSet etc.

There's not a huge amount of application for it outside the realm of storing objects inside hashing data structures though.

[Jim Yingst]

[Adeel Ansari]: Its not just about Set, but Collection, or better say where ever its about comparison or sorting. So, beside other things, now Array is also included.

Do you mean java.util.Arrays? I don't think that's correct. Methods like sort() and binarySearch() rely on the Comparable and Comparator interfaces to determine both order and equality. There's no need for hashCode() or equals(). Meanwhile Arrays.equals() relies on the equals() method of each object in the array, but not hashCode(). Obviously, Arrays.hashCode() does rely on the hashCode() of each contained object - but aside from that, java.util.Arrays() does not use hashCode().

Still, in general you never know when some third-party code you're using may use a HashMap internally, since they're very useful. So anytime you have a class that overrides equals() but not hashCode() (or vice versa, or otherwise provides an incorrect implementation of equals() or hashCode()) then strange things may happen without warning. So I would be careful to always override correctly unless I was sure the class would never be used in a context where a good hashCode() is required - and it's very rare that I'm that sure about possible future uses of a class I'm writing.

[Rob Spoor]

You should always override equals and hashCode together so they match. Why? Because the API says so.

If you don't, you will break the general contract for equals and hashCode, and code using your class may behave strange, and nobody will know why.

I always override hashCode to use the same fields I check on in the equals method, sometimes omitting a few, but never adding anything else.

[Stan James]

I've always wondered why "they" don't recommend overriding compareTo to be compatible as well. I guess because Comparable is optional.

[Jim Yingst]

Yes, compareTo() is optional - and also, even when compareTo() is used (e.g. by Collections.sort()), equals() and hashCode() are ignored entirely. Sort algorithms use the result compareTo(other) == 0 to define equality, instead of using equals(). After all, using equals() would (a) be inefficient since compareTo() has already given a result, and (b) prevent us from using different Comparators to give different sort orders. Compatibilty between compareTo() and equals()/hashCode() may be nice, but it is never a requirement in order to get consistent, sensible results from a sort. In comparison, a HashMap does require both equals() and hashCode() to be compatible, and can give completely nonsensical results if this requirement is not met.

[Adeel Ansari]

Originally posted by Jim Yingst:
Compatibilty between compareTo() and equals()/hashCode() may be nice, but it is never a requirement in order to get consistent, sensible results from a sort.

Yes, I encountered the similar thing in Effective Java by Joshua Bloch.

[Adeel Ansari]

Originally posted by Jim Yingst:
Do you mean java.util.Arrays? I don't think that's correct. Methods like sort() and binarySearch() rely on the Comparable and Comparator interfaces to determine both order and equality. There's no need for hashCode() or equals(). Meanwhile Arrays.equals() relies on the equals() method of each object in the array, but not hashCode(). Obviously, Arrays.hashCode() does rely on the hashCode() of each contained object - but aside from that, java.util.Arrays() does not use hashCode().

Right. I just confused both the things. Thanks for the correction.

[Rob Spoor]

Actually, because compareTo and equals do not have to be compatible, the Collections API allows users to break their own contract.

As specified by Set, the contains method uses equals to check if an object is present. SortedSet does not override this method so this should still hold. However, TreeSet uses (through TreeMap) compareTo (or its Comparator's compare) instead of equals.

Now if compareTo and equals aren't compatible, this is clearly a violation of the Set contract.

[Adeel Ansari]

Originally posted by Rob Prime:
As specified by Set, the contains method uses equals to check if an object is present. SortedSet does not override this method so this should still hold. However, TreeSet uses (through TreeMap) compareTo (or its Comparator's compare) instead of equals.

And the API docs says nothing about this implementation. Yes, thats strange. It should use equals method - as specified by Sets contains() - if doing otherwise, it should be mentioned.

A very good example. So, the statement remains the same, "Its better to make compareTo() and equals() compatible. Otherwise you might be losing your objects".

[Jim Yingst]

Adeel, it's discussed in the API for SortedSet, which extends Set, and the discussion is repeated in the API for TreeSet:

Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Set interface is defined in terms of the equals operation, but a TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal. The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.

There are also warnings in the Comparable and Comparator interfaces. They didn't hide this info. Unfortunately the implementations in TreeSet and TreeMap inherit some of the original JavaDoc from Set and Map, without revising it to mention that they don't use equals(). The result is that some of the JavaDoc is contradictory.

[Adeel]: A very good example. So, the statement remains the same, "Its better to make compareTo() and equals() compatible. Otherwise you might be losing your objects".

Not really. I don't see how this would lead to losing objects. It's just that the equals() method isn't what is used to define equality, when using a SortedSet (or SortedMap). Objects in the set or map may still be found and retrieved - unlike what happens in a HashSet if the hashCode() is incompatible with equals().
[ December 19, 2007: Message edited by: Jim Yingst ]

[Adeel Ansari]

Jim Yingst:
Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface.

Yeah, I know and its fair enough.

Jim Yingst:
This is so because the Set interface is defined in terms of the equals operation, but a TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal.

Its fair enough, too.

The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.

Here we have the problem and that was my whole point. Can we say not-clear-enough documentation?

Actually, I would expect something like, "This method's implementation depends on compareTo() method, instead", in the API docs. So, one can know without looking to the actual implementation or digging into it.

[Adeel Ansari]

Just checked API docs for Java 5, its there.
Thanks.

So, now agreed terms are:

- TreeSet contains() implementation is a clear violation of Set contract
- Its better to make compareTo() and equals() methods compatible with each other.
[ December 19, 2007: Message edited by: Adeel Ansari ]

[Jim Yingst]

Sorry, I just edited my above post and added some new info. Didn't realize you had added posts here. Yes, I would agree the documentation is not as clear as it could be. I think OrderedSet should have added new JavaDoc for contains() and add() which made clear that compareTo() or compare() would be used instead of equals(). Otherwise they can't really say the behavior is "well-defined" since the API is contradictory.

[Jim Yingst]

[Adeel]: - TreeSet contains() implementation is a clear violation of Set contract

But it's not a violation unless the compareTo() or comare() method used is incompatible with equals(). That's dependent on the objects in the collection, not on TreeSet itself. So TreeSet allows users to violate the contract, but it doesn't violate the contract itself.

The other thing is, in many cases it doesn't seem to matter much. TreeSet and TreeMap still work just fine - they just don't work exactly like they were described in the original Set and Map interfaces. I have not encountered a use case where this really makes a difference. Maybe there is one somewhere - but in general, I really don't have a problem with letting compare() replace equals() as the tool for comparing elements. I think perhaps it would have been better if the Set and Map APIs had been a little less specific in the first place about the role of equals(), allowing different implementations to perform comparisons differently.

[Adeel Ansari]

Originally posted by Jim Yingst:
But it's not a violation unless the compareTo() or comare() method used is incompatible with equals().

Violation in the sense of this statement, "...if this set contains no element e such that (o==null ? e==null : o.equals(e)).".

[Jim Yingst]

But if you implement compareTo() or compares() to be compatible with equals(), that requirement is not violated.

Really, I guess we're just going in circles. It's clear that a violation can occur, whether we blame Comparable/Comparator or SortedSet/SortedMap. I suppose it doesn't really matter that much which one is blamed. I do still think that the vast majority of the time, this violation doesn't really matter in the sense that it doesn't prevent the programmer from successfully using the SortedSet or SortedMap to do what they need it to do.

[Adeel Ansari]

Originally posted by Jim Yingst:
Not really. I don't see how this would lead to losing objects. It's just that the equals() method isn't what is used to define equality, when using a SortedSet (or SortedMap). Objects in the set or map may still be found and retrieved - unlike what happens in a HashSet if the hashCode() is incompatible with equals().

Sorry, I was not very clear when I said this. To elaborate my point, I would like to give an example. Say I am creating a ArrayList object from a TreeSet object. Now all objects get copied. But when I checked for a particular object in the arrayList, using contains() method, it said false and then I checked the same in the treeSet, using contains(), whether it was there or not, so I found that its returning true. It means your object is there in the arrayList but its not friendly with contains() method.

[Adeel Ansari]

Originally posted by Jim Yingst:
But if you implement compareTo() or compares() to be compatible with equals(), that requirement is not violated.

May be, but from where I am looking at it, its violated. Because its clearly mentioning the statement o.equals(e), and contrarily its using o.compareTo(e). Now if both are compatible thats great but doesn't really according to the specs. Its compatible by chance or by making it compatible deliberately, whereas making it compatible is optional. So, we can make both compatible but the specs are not at all saying, we have to. I hope you got my point.