The Artima Developer Community
Sponsored Link

Articles Forum
How to Write an Equality Method in Java

44 replies on 3 pages. Most recent reply: Jun 5, 2013 10:25 AM by Winston Gutkowski

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 44 replies on 3 pages [ 1 2 3 | » ]
Bill Venners

Posts: 2244
Nickname: bv
Registered: Jan, 2002

How to Write an Equality Method in Java Posted: Jun 1, 2009 1:00 AM
Reply to this message Reply
Advertisement
This article, adapted from a section in Programming in Scala, describes a technique for overriding the equals method in Java that preserves the contract of equals even when subclassses of concrete classes add new fields:

http://www.artima.com/lejava/articles/equality.html

What do you think of the technique presented in the article?


Alex Blewitt

Posts: 44
Nickname: alblue
Registered: Apr, 2003

Re: How to Write an Equality Method in Java Posted: Jun 1, 2009 8:12 AM
Reply to this message Reply
It's really a shame when people cite LSP as if it were some kind of golden rule. In fact, it doesn't exist, and never has - it was cited as a 'wouldn't it be nice if' rule and is trivially disproven:

http://alblue.blogspot.com/2004/07/java-liskov-substution-principle-does.html

The problem is that you can't, in fact, blindly substitute one thing for another hand have your program work in exactly the same way. Mocking is an explicit example of this, where you don't want your program to work the same way (but want to supply a different implementation that does nothing/is testable/doesn't have the setup costs etc.

Unfortunately, far more people use Bloch's implementation (using instanceof) instead of one which preserves transitivity and obeying the contract as is.

You can either (a) test for instance field equality (using getClass and friends) or (b) test behavioural equality using the results of property accessors, but mixing the two is self-inconsistent.

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: How to Write an Equality Method in Java Posted: Jun 1, 2009 1:49 PM
Reply to this message Reply
> The problem is that you can't, in fact, blindly substitute
> one thing for another hand have your program work in
> exactly the same way.

I'm pretty sure this is not what the LSP means.

This is how Robert Martin paraphrases it which is pretty much how I understand it: "Functions that use pointers or references to base classes must be able to use objects of derived classes without knowing it."

http://www.objectmentor.com/resources/articles/lsp.pdf

Or in my own words, if I have a type Foo and a type Bar that extends Foo and I write a method doStuff(Foo), doStuff has to treat Bar instances the same way it treats Foo instances. This is clearly not the case if you use class equality in an equals method.

If the substitution could not change the behavior there would be little reason for the substitution in the first place.

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: How to Write an Equality Method in Java Posted: Jun 1, 2009 2:06 PM
Reply to this message Reply
Kind of continuing the discussion from the other article, I don't really the obsession over equals. My experience is that ultimately there is never one single way everyone will want to compare two objects, even when they are of the same type. Object.equals is only really useful when you know exactly how it will be used.

The solution here works but the concrete example shown basically comes down to this:
if (that instanceof this && this instanceof that)
{
   //...
}
else
{
  return false;
}


Which is barely different from the class comparison approach. Is there a different type of implementation that allows for correctness i.e. is there another valid way to implement canEquals()? I haven't thought it through but I would think that any deviation from this formula and we are back to violating the contract of equals.

What about when I want to compare a collection of Points as Points without regard to their color? I have to write a separate equals routine. What I'd actually do is create a Comparator and use a TreeSet or something that supports Comparators. It would be nice to have an Equalator that supported hashing but it seems that people would rather chase their tails trying to come up with technically correct but useless equals methods.

Bill Venners

Posts: 2244
Nickname: bv
Registered: Jan, 2002

Re: How to Write an Equality Method in Java Posted: Jun 1, 2009 2:59 PM
Reply to this message Reply
Hi Alex,

> It's really a shame when people cite LSP as if it were
> some kind of golden rule. In fact, it doesn't exist, and
> never has - it was cited as a 'wouldn't it be nice if'
> rule and is trivially disproven:
>
> http://alblue.blogspot.com/2004/07/java-liskov-substution-p
> rinciple-does.html
>
> The problem is that you can't, in fact, blindly substitute
> one thing for another hand have your program work in
> exactly the same way. Mocking is an explicit example of
> this, where you don't want your program to work the same
> way (but want to supply a different implementation that
> does nothing/is testable/doesn't have the setup costs
> etc.
>
On LSP, I brought it up in the book chapter and article because I'd heard it as an objection to the canEqual approach. So I wanted to put an "LSP defense" in the text to head this objection off at the pass. When I did, I looked up the original text and it also looked to me like Liskov was saying that subtypes must have exactly the same behavior as supertypes. But what the world thinks LSP means is that *at some level of abstraction" the behavior is compatible, or that the subtype behavior must fulfill the semantic contract of its supertype. I felt a bit uneasy saying the latter is what LSP means, because I also wasn't sure that's what Liskov meant, but it is what the general usage of the term LSP seems to mean.

> Unfortunately, far more people use Bloch's implementation
> (using instanceof) instead of one which preserves
> transitivity and obeying the contract as is.
>
> You can either (a) test for instance field equality (using
> getClass and friends) or (b) test behavioural equality
> using the results of property accessors, but mixing the
> two is self-inconsistent.
>
I'm not sure I understand your b. Or maybe your whole last paragraph. Can you clarify?

What you wrote in 2004 in the blog post you linked to is what I think has been the conventional wisdom in the Java community for a long time, although it wasn't necessarily widespread wisdom. You wrote:

Specifically, in order to rely on the LSP, you have to ensure that M> obeys the contract defined in T, which implies that it must be reflexive, symmetric and transitive. If you don't have that, you don't have a valid overridden method as per the LSP definition, so you can't even use that as your argument.

Lastly, if you do try and use instanceof, you can guarantee that you break symmetry, because the instanceof is asymmetric. I did point out in my proof on JavaWorld, that it is possible to overcome this behaviour; however, for any implementation of .equals() using instanceof that obeys reflexivity and symmetry will be forced to break transitivity.

So the arguments are set in stone. The LSP doesn't hold in Java, and never has.

--end of Alex quote

It is true that if you use instanceof in the first two ways shown in this article, you either break symmetry or transitivity, and that if you use getClass you can fulfill the equals contract. This is basically what you're saying in the above quote. But what's been missing from the discussion is that there is a technique that lets you use instanceof while at the same time maintaining the equals contract, and that's what this article is trying to show. The benefit of instanceof/canEqual over just using getClass is that subclasses instances can equal superclass instances. The writer of the subclass decides whether this is possible based on whether or not he or she overrides the canEqual method.

James Watson

Posts: 2024
Nickname: watson
Registered: Sep, 2005

Re: How to Write an Equality Method in Java Posted: Jun 1, 2009 4:33 PM
Reply to this message Reply
> The benefit of
> instanceof/canEqual over just using
> getClass is that subclasses instances can
> equal superclass instances. The writer of the subclass
> decides whether this is possible based on whether or not
> he or she overrides the canEqual method.

Is it not the case, however, that if the subclass overrides equals() and doesn't override canEqual() to return {that instance of this}, we are back in non-compliance territory.

The only benefit I see to this is that the subclass controls the behavior instead of the superclass. That's better but it doesn't address the fundamental issue of designing a part of a system using the equals() method as defined in my base class. If I depend on equals to determine if two points have the same x,y coordinates (e.g. use collections naively) canEquals() solves nothing.

Bill Venners

Posts: 2244
Nickname: bv
Registered: Jan, 2002

Re: How to Write an Equality Method in Java Posted: Jun 1, 2009 5:15 PM
Reply to this message Reply
> > The benefit of
> > instanceof/canEqual over just using
> > getClass is that subclasses instances can
> > equal superclass instances. The writer of the subclass
> > decides whether this is possible based on whether or
> not
> > he or she overrides the canEqual method.
>
> Is it not the case, however, that if the subclass
> overrides equals() and doesn't override canEqual() to
> return {that instance of this}, we are back in
> non-compliance territory.
>
Yes, if you make a Point subclass, say GoodPoint, that overrides equals, and inside that does an (other instanceof GoodPoint), then it would need to override canEqual too. And GoodPoints would never be equal to Points. If you didn't override canEqual in that case, it would indeed be breaking the equals contract again (the same instanceof breaking symmetry problem we started with).

> The only benefit I see to this is that the subclass
> controls the behavior instead of the superclass. That's
> better but it doesn't address the fundamental issue of
> designing a part of a system using the equals() method as
> defined in my base class. If I depend on equals to
> determine if two points have the same x,y coordinates
> (e.g. use collections naively) canEquals() solves nothing.
>
No, I don't think the superclass can do it by itself, right? It can determine if the other object is an instance of its class. What it can't figure out is whether the other object is an instance of a subclass that overrode equals and added an (other instanceof <subclass type>) in there. That's what screws up the symmetry, and so the superclass has to always ask the other class if it can equal this one, which is what the canEqual method allows it to do.

Kyle Winter

Posts: 1
Nickname: kwinter
Registered: Jun, 2009

Re: How to Write an Equality Method in Java Posted: Jun 1, 2009 6:46 PM
Reply to this message Reply
#3 should probably be entitled "Defining hashcode in terms of mutable fields," as the issue doesn't truly lie with the equals method, but in the fact that HashSet only calculates the hash once when the object is added. Using a List instead of HashSet would return true for all 3.

Chris Hansen

Posts: 2
Nickname: chansen
Registered: Jun, 2009

Re: How to Write an Equality Method in Java Posted: Jun 1, 2009 10:16 PM
Reply to this message Reply
I'm the co-author of a library which is designed to help with this sort of thing. It uses reflection to implement hashCode(), equals(Object) and toString() for you, so that you don't fall into one of the common pitfalls listed in the article. Which fields/methods are included in or excluded from those operations are controlled via annotations. It's called Pojomatic and can be found at http://www.pojomatic.org . An intro can be found here: http://polyglot-window.blogspot.com/2009/01/introducing-pojomatic.html

Chris Hansen

Posts: 2
Nickname: chansen
Registered: Jun, 2009

Re: How to Write an Equality Method in Java Posted: Jun 1, 2009 10:40 PM
Reply to this message Reply
Sorry for the double-post, but I should mention that the library I mentioned previously will not help with pitfalls 1 or 3, but we also recommend @Override for #1. As for pitfall #3, it should be noted that using mutable data in equals does not violate the contract of equals because the consistency requirement specifically accounts for mutability.

Carfield Yim

Posts: 32
Nickname: carfield
Registered: Sep, 2002

Re: How to Write an Equality Method in Java Posted: Jun 1, 2009 11:44 PM
Reply to this message Reply
The amend case is the one hit most of the time :-/

Jason Young

Posts: 6
Nickname: apollodude
Registered: Dec, 2008

Re: How to Write an Equality Method in Java Posted: Jun 2, 2009 9:35 AM
Reply to this message Reply
I don't think LSP is a problem in the article. Defining "equals" is. It has subtly different meanings in different contexts, even where meaning is well-established. We confuse equality and sameness all the time in the world of software development.

Equality means different things not only for different types but also in different domains. Sometimes, you need different meanings of "equals" for the same type in different contexts. Thus, it is unwise to write code that relies on an override of object.equals. One should instead allow client code to specify an equality tester.

As for LSP, indeed, if overriding methods must behave 100% the same as the methods which they override, then overriding is useless. If they merely must fulfill (and optionally extend) their parents' contracts, then LSP is respected in the original article.

Daniel Jimenez

Posts: 40
Nickname: djimenez
Registered: Dec, 2004

Re: How to Write an Equality Method in Java Posted: Jun 2, 2009 11:03 AM
Reply to this message Reply
What exactly are we attempting to solve with this? Using the most implementation-y form of inheritance to very slightly reduce some minor code duplication? All so we can have Point3D extend Point2D or Circle extend Ellipse?

Is that very slight gain really worth this very real cost?

(That said, it's a clever technique.)

Gregor Zeitlinger

Posts: 108
Nickname: gregor
Registered: Aug, 2005

Re: How to Write an Equality Method in Java Posted: Jun 3, 2009 4:13 PM
Reply to this message Reply
> What it can't figure out is whether the
> other object is an instance of a subclass that overrode
> equals
If could find out if the other class overrode equals - using reflection.
This could very well be the task of a library method like pojomatic mentioned above.

Gregor Zeitlinger

Posts: 108
Nickname: gregor
Registered: Aug, 2005

Re: How to Write an Equality Method in Java Posted: Jun 3, 2009 4:37 PM
Reply to this message Reply
There's a version that doesn't require canEqual and is even more flexible:
Point.equals(Object o) {
  if (o instanceof Point) {
    if (!o.getClass.isAssignableFrom(getClass())) {
      //let the subclass decide if we are equal
      return o.equals(this);
    }
    Point p = (Point)o;
    return x == p.x && y == p.y;
  }
  return false;
}

now ColoredPoint could be defined in either way:
ColoredPoint.equals(Object o) {
  if (o instanceof ColoredPoint) {
    if (!o.getClass.isAssignableFrom(getClass())) {
      //let the subclass decide if we are equal
      return o.equals(this);
    }
    ColoredPoint p = (ColoredPoint)o;
    return color == p.color && super.equals(o);
  }
  return false;
}

or
ColoredPoint.equals(Object o) {
  if (o instanceof ColoredPoint) {
    if (!o.getClass.isAssignableFrom(getClass())) {
      //let the subclass decide if we are equal
      return o.equals(this);
    }
    ColoredPoint p = (ColoredPoint)o;
    return color == p.color && super.equals(o);
  } else if (o instanceof Point) {
    return color == Color.RED && super.equals(o);
  }
  return false;
}

Flat View: This topic has 44 replies on 3 pages [ 1  2  3 | » ]
Topic: Testing Private Methods with JUnit and SuiteRunner Previous Topic   Next Topic Topic: How Scala Changed My Programming Style


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us