Tal is a researcher in IBM's Haifa Research Labs in Israel. He can be contacted at [email protected].
The Java equals() method, which is defined in java.lang.Object, is used for instance equality testing (as opposed to reference equality, which is tested using the == operator). Consider, for example, these two assignments:
Date d1 = new Date(2001, 10, 27);
Date d2 = new Date(2001, 10, 27);
In this case, d1 == d2 returns False (since == tests for reference equality, and the two variables are references to different objects). However, d1.equals(d2) returns True.
The default implementation of equals() is based on the == operator: Two objects are equal if and only if they are the same object. Naturally, most classes should define their own alternative implementation of this important method.
However, implementing equals() correctly is not straightforward. The equals() method has a contract that says the equality relation must meet these demands:
- It must be reflexive. For any reference x, x.equals(x) must return True.
- It must be symmetric. For any two nonnull references x and y, x.equals(y) should return the exact same value as y.equals(x).
- It must be transitive. For any three references x, y, and z, if x.equals(y) and y.equals(z) are True, then x.equals(z) must also return True.
- It should be consistent. For any two references x and y, x.equals(y) should return the same value if called repeatedly (unless, of course, either x or y were changed between the repeated invocations of equals()).
- For any nonnull reference x, x.equals(null) should return False.
This doesn't sound complicated: The first three items are the natural mathematical properties of equality, and the last two are trivial programmatic requirements. It looks like any implementation based on simple field-by-field comparison would do the trick. For example, in Listing One the class Point represents a point in two-dimensional space, with a suggested implementation for the equals() method. At first glance, it looks as though Listing One meets all five demands placed by the contract:
- It is reflexive, since whenever the parameter o is actually this (which is what happens when one invokes it using x.equals(x)), the fields match and the result is True.
- It seems symmetric. If some Point object p1 finds its fields are equal to those of some other Point object p2, then p2 would also find that its own fields are equal to those of p1. For example, after the two assignments:
Point p1 = new Point(1, 2);
Point p2 = new Point(1, 2);
both p1.equals(p2) and p2.equals(p1) return True. If, on the other hand, p2 is different than p1, both calls return False.
- It seems transitive, for the same reasons.
- It is clearly consistent.
- Any call of the form x.equals(null) returns False, thanks to the test at the beginning of the code: If the parameter is not an instance of the class Point, the method returns False immediately. Since, in particular, null is not an instance of Point (nor indeed of any other class), the condition is met.
However, this is a naïve implementation. As Joshua Bloch shows in his book Effective Java Programming Language Guide (Addison-Wesley, 2001), things get much more complex when inheritance is involved.
Bloch presents the class ColorPoint (Listing Two), which extends Point and adds an aspect (namely, a new field). If ColorPoint implements equals() similarly to its superclass Point, symmetry is violated. Again, the implementation seems straightforward and correct. The problem arises when two objects are involved, each of a different class:
ColorPoint p1 = new ColorPoint(1, 2, Color.RED);
Point p2 = new Point(1, 2);
Now, p2.equals(p1) returns True, since the two fields p2's equals() method compares, x and y, are indeed equal. Yet p1.equals(p2) returns False because p2 is not an instance of the ColorPoint class.
It is important to understand that an incorrect implementation of equals(), like that just presented, would cause problems in many unexpected places; for example, when the objects are used in various collection classes (that is, in their containment tests). And you have just seen that this simple implementation does not provide symmetry.
Listing Three, an alternative implementation of equals(), does meet the symmetry requirement. While at first it might seem a better solution, Bloch shows that it is broken, too. Symmetry is indeed preserved. p1 and p2 (from the earlier example) would both provide the same answer when asked if one equals the other. However, this implementation violates the demand for "transitivity." To see how, add a third reference, p3:
ColorPoint p3 = new ColorPoint(1, 2, Col or.BLUE);
In this case, p1.equals(p2) returns True, since p1 realizes p2 is not a ColorPoint and performs a color-blind comparison. p2.equals(p3) also returns True, since p2, being a simple Point, compares only the x and y fields and finds them to be equal. Transitivity demands that if a=b and b=c, then a=c as well. But in this case, even though p1.equals(p2) and p2.equals(p3), the call p1.equals(p3) returns False.
One way to avoid the problem is to ignore any fields added in subclasses. This way, ColorPoint inherits the implementation of equals() provided by Point, and doesn't override it. This solution does meet all the contract demands for equals(). However, it is hardly a useful equality test; for example, p1.equals(p3) returns True, even though each point has a different color.
Bloch claims that "It turns out that this is a fundamental problem of equivalence relations in object-oriented languages. There is simply no way to extend an instantiable class and add an aspect while preserving the equals contract." He suggests that programmers use composition rather than inheritance to work around this problem. Taking this approach, the ColorPoint class would not extend Point, but rather include a field of that type, like Listing Four.
Is this the only solution? Not really. The Point class can be extended, adding an aspect, while preserving the equals() contract. The basic idea is this: For two objects to be equal, both must agree that they are equal. To prevent endless recursion during the mutual verification, you define a protected helper method, blindlyEquals(), which compares fields blindly. The equals() method then verifies that both objects agree that they are blindly equal to each other; see Listing Five. Note how the implementation of blindlyEquals() is simply the original implementation of equals(). However, blindlyEquals() is not bound by the equals() contract. By itself, it does not provide a symmetric comparison, but it does provide equals() with the services it needs to fully meet the contract demands.
In subclasses, you override blindlyEquals() only, leaving equals() unchanged. Listing Six, therefore, is a proper implementation of the class ColorPoint. Again, the implementation of blindlyEquals() is the original, nonsymmetric attempt to implement equals(). The equals() method itself is inherited from Point, and not overridden.
It is easy to see that this new implementation is both symmetric and transitive, as well as meeting all other demands placed by the equals() contract. In particular, when using the three objects defined in the previous examples:
- p2.blindlyEquals(p1) returns True, but p1.blindlyEquals(p2) returns False. Since equals() checks both ways, both p1.equals(p2) and p2.equals(p1) return False.
- Since p1.equals(p2) returns False (and p2.equals(p3) returns False as well), the transitivity demand does not hold in this case (a
b and bc means you do not know in advance if a=c or not).
It can be mathematically proven that symmetry and transitivity always hold with this implementation. The symmetry part is easy: For any two references x and y, x.equals(y) and y.equals(x) execute the same code (calling both x.blindlyEquals(y) and y.blindlyEquals(x), although in a different order). Transitivity can be proven using reductio ad absurdum. And of course, the other three contract demands — reflexivity, consistency, and returning False when tested on null — are also met.
The technique presented here can be applied to any object hierarchy you define in Java. That equals() itself is never overridden means it would have been best if this implementation was part of the standard java.lang.Object() class, along with a default implementation of blindlyEquals(), which could be easily overridden by each subclass. However, since this change in the Java standard libraries is not likely to occur anytime soon, we will have to be content with manually including it in programs.
In short, whenever you define a new class, a definition of blindlyEquals() must be included as a nonsymmetric comparison operation, and an implementation of equals() (as presented here) should be added. Then, all subclasses of this newly defined class need only override blindlyEquals() to provide a complete, contract-abiding equals() comparison.
The method presented here can be used in any object-oriented language, and does not rely on run-time type information (other than the instanceof operator, which is required for any implementation of equals()). It does incur a price on performance, but a relatively minor one: The equality test is repeated twice, but only if the two objects are indeed equal. A few simple modifications can reduce the cost significantly. For an additional discussion, please visit http://www.forum2.org/tal/equals.html.
DDJ
Listing One
class Point {
private int x;
private int y;
// (obvious constructor omitted...)
public boolean equals(Object o) {
if (!(o instanceof Point))
return false;
Point p = (Point)o;
return (p.x == this.x && p.y == this.y);
}
}
Listing Two
class ColorPoint extends Point {
private Color c;
// (obvious constructor omitted...)
public boolean equals(Object o) {
if (!(o instanceof ColorPoint))
return false;
ColorPoint cp = (ColorPoint)o;
return (super.equals(cp) && cp.color == this.color);
}
}
Listing Three
class ColorPoint extends Point {
private Color c;
// (obvious constructor omitted...)
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:
ColorPoint cp = (ColorPoint)o;
return (super.equals(cp) && cp.color == this.color);
}
}
Listing Four
class ColorPoint {
private Point point;
private Color color;
// ...etc.
}
Listing Five
class Point {
private int x;
private int y;
protected boolean blindlyEquals(Object o) {
if (!(o instanceof Point))
return false;
Point p = (Point)o;
return (p.x == this.x && p.y == this.y);
}
public boolean equals(Object o) {
return (this.blindlyEquals(o) && o.blindlyEquals(this));
}
}
Listing Six
class ColorPoint extends Point {
private Color c;
protected boolean blindlyEquals(Object o) {
if (!(o instanceof ColorPoint))
return false;
ColorPoint cp = (ColorPoint)o;
return (super.blindlyEquals(cp) &&
cp.color == this.color);
}
}
