5

this question is specifically about the performance and to some extent brevity of the various implementation alternatives.

I refreshed myself with this article on implementing equality right. My question particularly corresponds to canEqual (to ensure equivalence relation).

instead of overloading canEquals method to use instanceOf in every class in the hierarchy( instance of paramenter is a compile time class ). Why not use isAssignableFrom ( which is resolved dynamically ) in only the top level class. Makes for much concise code and you dont have to overload a third method.

While, this alternative works. Are there any performance considerations that I need to be aware of?

enum Color {
    RED, ORANGE, YELLOW, GREEN, BLUE, INDIGO, VIOLET;
}
class Point {

    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }


    @Override public boolean equals(Object other) {
        boolean result = false;
        if (other instanceof Point) {
            Point that = (Point) other;
            //Option 1
            //result = (that.canEqual(this) && this.getX() == that.getX() && this.getY() == that.getY());
            //Option 2
            //result = (that.getClass().isAssignableFrom(this.getClass()) && this.getX() == that.getX() && this.getY() == that.getY());
            //Option 3
            //result = (getClass() == that.getClass() && this.getX() == that.getX() && this.getY() == that.getY());
        }
        return result;
    }

    @Override public int hashCode() {
        return (41 * (41 + x) + y);
    }

    public boolean canEqual(Object other) {  return (other instanceof Point);   }
}

public class ColoredPoint extends Point{
      Color color;

        public ColoredPoint(int x, int y, Color color) {
            super(x, y);
            this.color = color;
        }

        @Override public boolean equals(Object other) {
            boolean result = false;
            if (other instanceof ColoredPoint) {
                ColoredPoint that = (ColoredPoint) other;
                result = (this.color.equals(that.color) && super.equals(that));
            }
            return result;
        }

        @Override public int hashCode() {
            return (41 * super.hashCode() + color.hashCode());
        }

        @Override public boolean canEqual(Object other) {    return (other instanceof ColoredPoint);   }

    public static void main(String[] args) {
        Object p = new Point(1, 2);
        Object cp = new ColoredPoint(1, 2, Color.INDIGO);

        Point pAnon = new Point(1, 1) {
            @Override public int getY() {
                return 2;
            }
        };

        Set<Point> coll = new java.util.HashSet<Point>();
        coll.add((Point)p);

        System.out.println(coll.contains(p)); // prints true
        System.out.println(coll.contains(cp)); // prints false
        System.out.println(coll.contains(pAnon)); // prints true
    }
}
smartnut007
  • 6,324
  • 6
  • 45
  • 52

7 Answers7

5

Update: Actually, your method is not technically valid like I first thought, because it breaks the symmetry contract of equals for subclasses that don't override equals:

Point p = new Point(1, 2);
Point pAnon = new Point(1, 1) {
    @Override public int getY() {
        return 2;
    }
};

System.out.println(p.equals(pAnon)); // prints false
System.out.println(pAnon.equals(p)); // prints true

The reason is that p.getClass().isAssignableFrom(pAnon.getClass()) is true while the inverse, pAnon.getClass().isAssignableFrom(p.getClass()) is false.

If you are not convinced by this, try actually running your code and compare it to the version in the article: you will notice that it prints true, false, false, instead of true, false, true like the example in the article.

waxwing
  • 18,547
  • 8
  • 66
  • 82
3

unless you want to allow comparing classes of different types, the easiest, safest, most concise and probably most efficient impl is:

(getClass() == that.getClass())
jtahlborn
  • 52,909
  • 5
  • 76
  • 118
  • 1
    +1. With `that != null && ...` this should definitely be your goto unless you have a compelling reason to allow equality of different concrete types. – Mike Samuel Jan 20 '12 at 20:43
  • 1
    -1 Yes, but that "unless" clause is often a big limitation. And OP clearly wants to compare objects of different types (Point and ColoredPoint) – user949300 Jan 20 '12 at 20:44
1

See my answer for What is the difference between equality and equivalence?.

You can't equate two objects from different classes because it breaks symmetry.

Edit:

It comes down to whether x in the following:

if (other instanceof Point) {
   Point that = (Point) other;

   boolean x = that.getClass().isAssignableFrom(this.getClass());
}

has the same power as getClass() == that.getClass(). According to @waxwing's answer it doesn't.

Even if it were correct, I don't see any performance benefit here by calling that.getClass().isAssignableFrom.

Community
  • 1
  • 1
Eugene Yokota
  • 94,654
  • 45
  • 215
  • 319
  • @smartnut007 Unfortunately (or fortunately) equals must be symmetric. You can either treat ColoredPoint as just another Point, using the Point's equals method, or, if it is truly different, you can compare for equality only to ColoredPoints, and have to use this.getClass() == that.getClass(). But your "hybrid" approach will fail cause it isn't symmetric. – user949300 Jan 20 '12 at 21:04
  • It's possible for a type to define equality in such a way as to allow mutual equivalence with subtypes. One such approach is to define a canonical form which will be applicable to all subtypes, and specify that two objects shall be deemed equivalent if they have the same canonical form. For example, one might have a abstract `ImmutableMatrix` type whose most common concrete subtype stores a matrix as a 2d array, but which also had a subtypes to compactly store a constant matrix (all values equal), a diagonal matrix (all items off the diagonal are zero), etc. – supercat Feb 02 '13 at 22:35
  • Every matrix would have to define `Equals` in terms of element-by-element comparison, and `hashcode` in terms of a function that was run on each element, but would not always have to implement them that way. A diagonal matrix which recognized that it was being compared to a constant matrix wouldn't have to check all of its always-zero cells against the other matrix's always-constant cells; checking the diagonal and one cell that was off the diagonal would be sufficient. – supercat Feb 02 '13 at 22:39
1

All the answers given so far don't answer the question - but point out the equals() contract. Equality must be an equivalence relation (transitive, symmetric, reflexive) and equal objects must have the same hash code. That extends perfectly fine to subclasses - provided subclasses don't themselves override equals() or hashCode(). So you have two choices - you either inherit equals() from Point (so ColoredPoint instances are equal if they have the same coordinates, even if they have a different color), or you override equals() (and now must make sure a Point and a ColoredPoint are never equal).

If you need to perform a pointwise comparison, then don't use equals() - write a method pointwiseEquals() instead.

Whatever you choose to do, you still have to perform the class check in equals().

getClass() == that.getClass()

is clearly the best performer, but it does break if you expect to be able to equality test subclasses that don't themselves override equals() (and in practice, the only way you can guarantee that is to make the class or the equality methods final and not allow any subclasses to override at all). If it's a choice between instanceOf and isAssignableFrom, there's no practical difference, they both in fact perform the same run-time test (the only difference is, instanceOf can perform a compile-time sanity check, but in this case, it can't know anything when the input is just Object). In both cases, the runtime check is identical - check for the target class in the object's listed interfaces (which doesn't apply here, since we're not checking for an interface), or walk up the class hierarchy until we either find the listed class or get to the root.

Chris Nash
  • 2,941
  • 19
  • 22
  • Thanks. But, See @waxwing answer. instanceof and isAssignableFrom dont behave the same. – smartnut007 Jan 20 '12 at 23:01
  • Design consideration, as brought up by @user949300. `other instanceof Point` says "this class knows about `Point` objects" - which it should, because it's a `Point`. Once you start messing around with `this.getClass()` and `that.getClass()`, your code is making assumptions about subclasses, which it has no right to do. – Chris Nash Jan 21 '12 at 00:47
  • @ChrisNash: Not only do base classes have every right to impose requirements upon subclasses (and assume that they will abide by such assumptions)--they can't avoid doing so. A base class which regards all subclass instances as being unequal to it will allow subclasses to define any desired equivalence relation among their instances. A base class which sometimes reported itself as equal to certain subclass instances would require all such subclass instances to report themselves as equal to each other. Approach #1 is generally safer and less restrictive than #2; a third approach... – supercat Feb 02 '13 at 23:00
  • ...is to require that every subclass which might compare itself as equal to some other type must define a canonical representation, and define `equals` and `hashcode` in terms of that representation. Under this approach, an `IdentityMatrix` of size 3 could compare equal to an `DiagonalMatrix` containing [1,1,1], since the canonical form for both would be a 3x3 matrix containing 1's on the diagonals and zeroes everywhere else. That approach is the most versatile, but also the most complicated. In most cases, such complexity would offer no real benefit to justify the cost. – supercat Feb 02 '13 at 23:07
1

Here's my Second Answer to the clarified question

Consider when we call Point.equals(ColoredPoint cp);

Point.equals() first checks for 

if (other instanceof Point)...

Which passes. Out of the three options presented, all three of them check that the other object, in this case a ColoredPoint, satisfies some more test. The options are:

  1. will only be true if Point is an instanceof ColoredPoint, which is never
  2. will only be true if ColoredPoint is assignable from Point, which is never
  3. will never be true.

From a performance (and design) perspective, there was no value in checking for other instanceof Point, because the actual behavior OP wants (which he has been unable to express) is that for his particular use case, equality between these Objects means they must be the same class.

Therefore, for both performance and design, just use

 this.getClass() == that.getClass()

as was suggested by @jthalborn

When a later coder sees instanceof or isAssignableFrom in your code, he will think that subclasses are allowed to equal the base class, which is completely misleading.

user949300
  • 15,364
  • 7
  • 35
  • 66
0

OK we here we have the example from Effective Java (i have the 2nd Edition 2008). The example is in ITEM 8: OBEY THE GENERAL CONTRACT WHEN OVERRIDING EQUALS starting from page 37 (I write this in case you want to check).

class ColoredPoint extends Point{} and there are 2 attepts in demostrating why instanceof is BAD. The first attempt was 

// Broken - violates symmetry!
@Override public boolean equals(Object o) {
          if (!(o instanceof ColorPoint))
          return false;
          return super.equals(o) && ((ColorPoint) o).color == color;

}

and the second was 

 // Broken - violates transitivity!
@Override public boolean equals(Object o) {
if (!(o instanceof Point))
    return false;
// If o is a normal Point, do a color-blind comparison
if (!(o instanceof ColorPoint))
    return o.equals(this);
// o is a ColorPoint; do a full comparison
return super.equals(o) && ((ColorPoint)o).color == color;

}

First of all the second IF will never be reached. If 'o' is not a Point which is a superclass to ColorPoint how might it happen a non-Point to be a ColorPoint ??????

So the second attempt from the beginning is wrong ! Where the only chance for a TRUE comparison is super.equals(o) && ((ColorPoint)o).color == color;, which is not enough !! a solution here would be:

if (super.equals(o)) return true;

  if (!(o instanceof ColorPoint))  
      if ((o instanceof Point)) return this.equals(o); 
      else return false;

  return (color ==((ColorPoint)o).color && this.equals(o));

obj.getClass() is used for very specific equals(), But your implementations depends of your scope. How do you define that two objects are equal or not? Implement it and it will work accordingly.

DayaMoon
  • 357
  • 2
  • 7
0

I think you solution will fail because it isn't transitive OOPS, symmetric. See The chapter from Effective Java

Point p = new Point(2,3);
ColoredPoint cp = new ColoredPoint(2,3, Color.WHITE);

I believe (haven't run your code) that

p.equals(cp) is true

but

cp.equals(p) is false

Though I don't fully understand your code - it refers to canEquals() which was commented out. The short answer is that you either have to ignore color for equality, or you have to do what @jthalborn suggested.

user949300
  • 15,364
  • 7
  • 35
  • 66
  • ah forgive me, there all references to canEqual should have been commented. – smartnut007 Jan 20 '12 at 20:57
  • you are wrong! no version of the sample code above would return true for p.equals(cp) – smartnut007 Jan 20 '12 at 21:02
  • 1
    How can you edit your code to change it, then give me a downvote for something you just changed??? If you never want a Point to equals a ColoredPoint, use @jthalborn answer. – user949300 Jan 20 '12 at 21:08
  • I am not sure if you can look at the history. My edit just commented out a spurious line of code. Should not change the results. – smartnut007 Jan 20 '12 at 22:35