• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Transitivity in Overriding equals

 
Joe Harry
Ranch Hand
Posts: 10112
3
Eclipse IDE Mac PPC Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Guys,

How not to violate transitivity when overriding the equals method?
 
Joe Harry
Ranch Hand
Posts: 10112
3
Eclipse IDE Mac PPC Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Found an interesting linke here
 
Campbell Ritchie
Sheriff
Posts: 48652
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please check that link; it won't open for me.
 
Rob Spoor
Sheriff
Pie
Posts: 20514
54
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Joe Harry
Ranch Hand
Posts: 10112
3
Eclipse IDE Mac PPC Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 48652
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 10112
3
Eclipse IDE Mac PPC Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 48652
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 3041
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
[[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
Posts: 48652
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Maybe my statement about instanceof was a bit sweeping . . .
 
Joe Harry
Ranch Hand
Posts: 10112
3
Eclipse IDE Mac PPC Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 20514
54
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 1951
7
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you declare Foo.equals() final, shouldn't you do the same for Foo.hashCode()?
 
Joe Harry
Ranch Hand
Posts: 10112
3
Eclipse IDE Mac PPC Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 3041
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
[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
Posts: 3041
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
[Jelle]: If you declare Foo.equals() final, shouldn't you do the same for Foo.hashCode()?

Yup.
 
Joe Harry
Ranch Hand
Posts: 10112
3
Eclipse IDE Mac PPC Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 3041
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic