aspose file tools*
The moose likes Java in General and the fly likes Transitivity in Overriding 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 "Transitivity in Overriding equals" Watch "Transitivity in Overriding equals" New topic
Author

Transitivity in Overriding equals

Joe Harry
Ranch Hand

Joined: Sep 26, 2006
Posts: 9382
    
    2

Guys,

How not to violate transitivity when overriding the equals method?


SCJP 1.4, SCWCD 1.4 - Hints for you, Certified Scrum Master
Did a rm -R / to find out that I lost my entire Linux installation!
Joe Harry
Ranch Hand

Joined: Sep 26, 2006
Posts: 9382
    
    2

Found an interesting linke here
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38817
    
  23
Please check that link; it won't open for me.
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19693
    
  20

It does for me.

The article is quite good, but it fails to see one thing. I applaud it for discouraging using instanceof in equals unless the class is final. What they fail to see is that you can also use instanceof if the equals method is final and the class isn't.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
Joe Harry
Ranch Hand

Joined: Sep 26, 2006
Posts: 9382
    
    2

I'm able to open it.

From Joshua Bloch's book on condition for Transitivity,

There is no way to extend an instantiable class and add a value component while preserving the equals contract.

Does he means to say that we can acheive transitivity only by using getClass() instead of using instanceof and using instanceof only when the class is final?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38817
    
  23
I think it is actually reflexivity that is preserved by using getClass() rather than instanceof.
As Rob has already said (I have a copy of Bloch's book) you can preserve reflexivity by using getClass() or final classes or (I never knew that either) final methods. Using instanceof in extends-able methods risks losing reflexivity.

But, Rob, if you are making the equals() method final, doesn't that restrict inheritance from that class?
Joe Harry
Ranch Hand

Joined: Sep 26, 2006
Posts: 9382
    
    2

Guys, then how do we attain Transitivity in an extensiable class?

Joshua Bloch's book says that we cannot acheive transitivity in an extensible class but rather a compositional reference would help us acheive transitivity.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38817
    
  23
Transitivity means that if a.equals(b) and b.equals(c) then a.equals(c).

You would achieve it the same way as with reflexivity. As far as I can remember (I am too tired to find my copy of Bloch) Bloch doesn't give a simple formula for equals() but rather principles to try and achieve the contract of Object#equals.
I don't think there is "the way" to work out equals. Using this.getClass() == obj.getClass() will probably achieve it, but if I remember correctly Bloch shows an example where getClass() can be too restrictive.

But we have seen that instanceof is not at all reliable in equals.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3014
    
  10
[[Jothi]: Guys, then how do we attain Transitivity in an extensiable class?

Well, you can look at the API for List and AbstractList for one example. List defines the equals() and hashCode() methods such that they do not depend on the type of the List; they only depend on the contents of the list, and their order. And AbstractList provides an implementation of this. Unfortunately, AbstractList does not make the equals() and hashCode() methods final, though it probably should have. Maybe this was an oversight, or maybe they wanted to allow implementors to find more efficient implementations for some special cases.

[Jothi]: Joshua Bloch's book says that we cannot acheive transitivity in an extensible class but rather a compositional reference would help us acheive transitivity.

Um, I doubt he says that. Where exactly do you think he says you cannot achive transitivity in an extensible class?

[Campbell]: But we have seen that instanceof is not at all reliable in equals

I would argue that it's quite reliable if you use it correctly. But it's not reliable in the sense that you can always use it indiscriminately.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38817
    
  23
Maybe my statement about instanceof was a bit sweeping . . .
Joe Harry
Ranch Hand

Joined: Sep 26, 2006
Posts: 9382
    
    2

Originally posted by Mike Simmons:
[[Jothi]: Guys, then how do we attain Transitivity in an extensiable class?

Well, you can look at the API for List and AbstractList for one example. List defines the equals() and hashCode() methods such that they do not depend on the type of the List; they only depend on the contents of the list, and their order. And AbstractList provides an implementation of this. Unfortunately, AbstractList does not make the equals() and hashCode() methods final, though it probably should have. Maybe this was an oversight, or maybe they wanted to allow implementors to find more efficient implementations for some special cases.

Then what could be the solution to acheive transitivity in a subclass where I have added yet another field?

[Jothi]: Joshua Bloch's book says that we cannot acheive transitivity in an extensible class but rather a compositional reference would help us acheive transitivity.

Um, I doubt he says that. Where exactly do you think he says you cannot achive transitivity in an extensible class?

[Campbell]: But we have seen that instanceof is not at all reliable in equals

I would argue that it's quite reliable if you use it correctly. But it's not reliable in the sense that you can always use it indiscriminately.
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19693
    
  20

Originally posted by Campbell Ritchie:
I think it is actually reflexivity that is preserved by using getClass() rather than instanceof.

Actually it's symmetry.

But, Rob, if you are making the equals() method final, doesn't that restrict inheritance from that class?

No, you just can't redefine what equality means. You can still perfectly extend that class.

The reason why instanceof is so dangerous is because of the types they are comparing to. Example:

Now new X().equals(new Y()) will return true because Y IS-A X, so the instanceof check will be valid. However, new Y().equals(new X()) will return true because X IS-A Y is false.


If you make X.equals final, then Y's equals method will also check if the parameter is an instanceof X. So new Y().equals(new X()) will also return true, and symmetry is maintained.
Jelle Klap
Bartender

Joined: Mar 10, 2008
Posts: 1763
    
    7

If you declare Foo.equals() final, shouldn't you do the same for Foo.hashCode()?


Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.
Joe Harry
Ranch Hand

Joined: Sep 26, 2006
Posts: 9382
    
    2

Originally posted by Mike Simmons:
[[Jothi]: Guys, then how do we attain Transitivity in an extensiable class?

Well, you can look at the API for List and AbstractList for one example. List defines the equals() and hashCode() methods such that they do not depend on the type of the List; they only depend on the contents of the list, and their order. And AbstractList provides an implementation of this. Unfortunately, AbstractList does not make the equals() and hashCode() methods final, though it probably should have. Maybe this was an oversight, or maybe they wanted to allow implementors to find more efficient implementations for some special cases.

[Jothi]: Joshua Bloch's book says that we cannot acheive transitivity in an extensible class but rather a compositional reference would help us acheive transitivity.

Um, I doubt he says that. Where exactly do you think he says you cannot achive transitivity in an extensible class?

[Campbell]: But we have seen that instanceof is not at all reliable in equals

I would argue that it's quite reliable if you use it correctly. But it's not reliable in the sense that you can always use it indiscriminately.


Mike,

Can you show me a case where you implement the equals method in the subclass which adds yet another instance field parameter?
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3014
    
  10
[Jothi]: Can you show me a case where you implement the equals method in the subclass which adds yet another instance field parameter?

Sure:

It's essentially the same technique shown in the article you linked to in your second post above, in the section labeled "Correct Implementation Example". You just have to apply it to both classes separately.

As far as I know, if you want to be able to add instance fields in subclasses, you need to use getClass() rather than instanceof, or you'll lose symmetry, as Rob showed. However instanceof is still useful in a class like AbstractList, which defines equals() such that if subclasses add any instance fields, those instance fields may not participate in the equals() relationship.
[ September 10, 2008: Message edited by: Mike Simmons ]
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3014
    
  10
[Jelle]: If you declare Foo.equals() final, shouldn't you do the same for Foo.hashCode()?

Yup.
Joe Harry
Ranch Hand

Joined: Sep 26, 2006
Posts: 9382
    
    2

Mike,

I got the following line from Joshua Bloch"s book, page 64.

There is no way to extend an instantiable class with a new value component while preserving the compareTo contract, unless you are willing to forgo the benefits of object-oriented abstraction (Item 8).

Can you comment on the above line keeping in mind the equals method instead of the compareTo?
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3014
    
  10
Well that's true, though I would amend it to say "forgo some benefits" rather than "forgo the benefits". The latter sounds like you're giving up all benefits, which I think is an exaggeration. Josh talks more about this, specifically for equals(), on pages 39 and 40.

Note that what he's saying here is different from "Joshua Bloch's book says that we cannot acheive transitivity in an extensible class". He's saying you cannot achieve transitivity in an extensible class if subclasses need to be able to add instance fields which are used in equals(), and if you are unwilling to break the Liskov substitution principle.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Transitivity in Overriding equals