File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes hashcode() and equals() Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "hashcode() and equals()" Watch "hashcode() and equals()" New topic
Author

hashcode() and equals()

rakesh sugirtharaj
Ranch Hand

Joined: Dec 16, 2007
Posts: 151
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:


Cheers!
RSR
Nitesh Kant
Bartender

Joined: Feb 25, 2007
Posts: 1638

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


apigee, a better way to API!
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19670
    
  18

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


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Adeel Ansari
Ranch Hand

Joined: Aug 15, 2004
Posts: 2874
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
Greenhorn

Joined: Dec 18, 2007
Posts: 12
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.


What do you mean, 'only String gets to have overloaded operators'?
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
[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.


"I'm not back." - Bill Harding, Twister
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19670
    
  18

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
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
I've always wondered why "they" don't recommend overriding compareTo to be compatible as well. I guess because Comparable is optional.


A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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
Ranch Hand

Joined: Aug 15, 2004
Posts: 2874
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
Ranch Hand

Joined: Aug 15, 2004
Posts: 2874
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
Sheriff

Joined: Oct 27, 2005
Posts: 19670
    
  18

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
Ranch Hand

Joined: Aug 15, 2004
Posts: 2874
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
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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
Ranch Hand

Joined: Aug 15, 2004
Posts: 2874
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
Ranch Hand

Joined: Aug 15, 2004
Posts: 2874
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
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
[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
Ranch Hand

Joined: Aug 15, 2004
Posts: 2874
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
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
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
Ranch Hand

Joined: Aug 15, 2004
Posts: 2874
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
Ranch Hand

Joined: Aug 15, 2004
Posts: 2874
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: hashcode() and equals()