Correctly Implementing equals()

This page discusses the finer points of the equals implementation suggested in "How Do I Correctly Implement the equals() Method?" (Dr. Dobb's Journal, May 2002).

Eran Tromer writes:

The code presented in the DDJ article causes test duplication. For instance, if an object is compared to itself then the full comparison test, including recursive calls to blindlyEquals of all the ancestors, is carried out twice: once in the this.blindlyEquals(o) direction and once in the o.blindlyEquals(this) direction.

Here is one solution -- in one direction it performs all tests, but in the other direction it avoids duplicating tests that were already performed. Changes from the original code are in bold.

class Point {
   protected boolean blindlyEquals(Object o, bool first) {
     bool b = o instanceof Point;
     if (!b || !first))
       return b;
     Point oo = (Point)o;
     return (someTest(oo,this));
   }
   public boolean equals(Object o) {
     return (this.blindlyEquals(o, false) &&
             o.blindlyEquals(this, true));
   }
}

class ColorPoint extends Point {
   protected boolean blindlyEquals(Object o, bool first) {
     bool b = o instanceof ColorPoint;

     if (!b || !first))
        return b;
     ColorPoint oo = (ColorPoint)o;
     return (super.blindlyEquals(oo, true) && additionalTest(oo,this));
   }
}

This is always correct, and the test of each ancestor class (in the union of ancestor classes of the compared instances) is performed at most once.

Note that the above form for X.blindlyEquals() is correct if noninstances of X can never equal instances of X. Otherwise, obvious changes are needed in this specific X.blindlyEquals().

However, suppose that the above always holds. That is, for any class X that needs to overrides the equality test, instances of X can never equal noninstances of X. (Is this a reasonable assumption? I can think of counterexamples, but not natural ones). Then X may equal Y only when they share an ancestor Z such that both X and Y still use the equality test inherited from Z. Thus the following also works:

class Point {
   protected boolean equalsImpl(Object o, bool asko) {
     if (!(o instanceof Point)
       return false;
     Point oo = (Point)o;
     if (asko)
       return oo.equalsImpl(this, false);
     return someTest(oo,this);
   }
   public boolean equals(Object o) {
     return (this.equalsImpl(o, true));
   }
}

class ColorPoint extends Point {
   protected boolean equalsImpl(Object o, bool asko) {
     if (!(o instanceof ColorPoint)
       return false;
     ColorPoint oo = (ColorPoint)o;
     if (asko)
       return oo.equalsImpl(this, false);
     return (super.equalsImpl(oo, false) && additionalTest(oo,this));
   }
}

In essence, this first verifies that both instances have the same equality test (though not necessarily the same class), and then peforms this test once. The advantage is that it avoids the situation where the comparison in one direction is fully executed, even though the other direction fails trivially already in the class check.

By the way, I suspect the matter can be classified as case of double-dispatch (with certain properties), and the various solutions, especially the last one above, are reminiscent of the classical method to emulate double dispatch, as observed for instance in the Visitor design pattern

I've had an interesting exchange of letters with Rene Smit, who first wrote:

Doesn't your implementation of equals boil down to making sure the two objects are of the same class? Doesn't the following implementation work just as well?

class Point {
        private int x;
        private int y;

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

        public boolean equals(Object o) {
                if (o == null || !getClass().equals(o.getClass()))
                        return false;
                Point p = (Point)o;
                return x == p.x && y == p.y;
        }
}

class ColorPoint extends Point {
        private Color c;

        public ColorPoint(int x, int y, Color c) {
                super(x, y);
                this.c = c;
        }

        public boolean equals(Object o) {
                if (o == null || !getClass().equals(o.getClass()))
                        return false;

                ColorPoint cp = (ColorPoint)o;
                return super.equals(cp) && c == cp.c;
        }
}

(Several other readers had asked the same question.) Two things are different between Rene's implementation and mine. First, Rene's suggestion uses run-time type information (the getClass() method), which might not be available in all OO languages; my solution relies on instanceof only. (In particular, versions of Java prior to Java 2 did not include the getClass() method.)

Second, sometimes subclasses do not add new fields -- it only overrides methods or add new ones, for example. Using my suggested implementation of equals(), a subclass of that kind could have instances that are equal to those of the parent class; not so with Rene's code.

The first problem is a theoretical one, and does not apply to modern Java. The second problem was elegantly solved by Rene's next letter:

Then I suggest the addition of a new method called getEquivalenceClass() that returns a non-null Object representing the class. A subclass doesn't override either equals() or getEqualityClass() if it doesn't add new fields.

So, for the case that new fields are added:

class Point {
        private int x;
        private int y;

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

        protected Object getEquivalenceClass() {
                return Point.class;
        }
        
        public boolean equals(Object o) {
                if (!(o instanceof Point))
                        return false;
                Point p = (Point)o;
                return getEquivalenceClass().equals(p.getEquivalenceClass())
                        && x == p.x && y == p.y;
        }
}

class ColorPoint extends Point {
        private Color c;

        public ColorPoint(int x, int y, Color c) {
                super(x, y);
                this.c = c;
        }

        protected Object getEquivalenceClass() {
                return ColorPoint.class;
        }

        public boolean equals(Object o) {
                if (!(o instanceof ColorPoint))
                        return false;
                ColorPoint cp = (ColorPoint)o;
                return super.equals(cp) && c == cp.c;
        }
}

And in case no new fields are added (i.e. its equivalence class is equal), simply:

class AnotherPoint extends Point {
        public AnotherPoint(int x, int y) {
                super(x, y);
        }
}

Rene is correct, of course. At first I thought that there is still one case where my original solution (symmetrical equality tests) has a slight advantage: when a subclass adds a field, and assumes an implicit 'default' value for this field in instances of the superclass. For example, a ColorPoint can ensure that a Point instance equals it if they both share the same coordinates, and the ColorPoint has the black color (the implicit default). But this, too, can be done with equality classes. In Rene's own words:

You would be right if my equivalence class method is static, but it isn't. So to make it work I can write getEquivalenceClass like this:

protected Object getEquivalenceClass() {
    return Color.black.equals(c) ? Point.class : ColorPoint.class;
}

Like your solution, it can dynamically determine how equivalent it is to Point. If the value has the default value then it can decide to make it equivalent to Point, else to ColorPoint. However, for this to work, the equals of ColorPoint should relaxed a bit and rewritten as:

public boolean equals(Object o) {
    if (o instanceof ColorPoint) {
        ColorPoint cp = (ColorPoint)o;
        if (c != cp.c)
            return false;
    }
    return super.equals(o);
}

In the previous version, this implementation of equals still works the same because the old equals contained an implicit test on equivalence class, which is already done in super.equals. So I think this implementation is better anyway.

By the way, for speed, if it's Java code, getEquivalenceClass can return java.lang.Class and the test can become getEquivalenceClass() == p.getEquivalenceClass().

Prof. Dr. Dominik Gruntz from the University of Applied Sciences Brugg-Windisch notes:

In order to guarantee that the equals() method is not overwritten I would recommend to declare equals() as final.

Richard Jepps notes that there are a few small errors in some of the code samples, that would prevent proper compilation. He had submitted the following complete test program, which complies and works properly:

public class EqualsTest {
    public static void main(String[] args) {
        Point      p1  = new Point(1, 1);
        Point      ap1 = new Point(1, 1); // another point

        ColorPoint c1  = new ColorPoint(1, 1, 1);

        System.out.println("Reflexive:  p1.equals(p1)  = " + p1.equals(p1)  + " Should be true.");
        System.out.println("Symmetric:  p1.equals(ap1) = " + p1.equals(ap1) + " Should be true.");
        System.out.println("Symmetric:  ap1.equals(p1) = " + ap1.equals(p1) + " Should be true.");
        System.out.println("Symmetric:  p1.equals(c1)  = " + p1.equals(c1)  + " Should be false."); 
                                                      // this was true in the naive implementation
        System.out.println("Symmetric:  c1.equals(p1)  = " + c1.equals(p1)  + " Should be false.");
    }
}

class Point {
    public double x;
    public double y;

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

    protected boolean blindlyEquals(Object o, boolean first) {
        boolean b = o instanceof Point;
        if (!b || !first)
            return b;
        Point oo = (Point)o;
        return (someTest(oo,this));
    }

    public boolean equals(Object o) {
        return (this.blindlyEquals(o, false) &&
            ((Point) o).blindlyEquals(this, true));
    }

    final protected boolean someTest(Point p1, Point p2) {
        return (p1.x == p2.x) && (p1.y == p2.y);
    }
}

class ColorPoint extends Point {
    public int color;

    public ColorPoint(double x, double y, int color) {
        super(x, y);

        this.color = color;
    }

    protected boolean blindlyEquals(Object o, boolean first) {
        boolean b = o instanceof ColorPoint;
        if (!b || !first)
            return b;
        ColorPoint oo = (ColorPoint)o;
        return (super.blindlyEquals(oo, true) && additionalTest(oo,this));
    }

    final protected boolean additionalTest(ColorPoint p1, ColorPoint p2) {
        return p1.color == p2.color;
    }
}

If you have additional comments, please contact tal@forum2.org.

- Tal Cohen