Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

JVM Languages

Java Q&A: How Do I Correctly Implement the equals() Method?


May02: Java Q&A

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 (ab 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);
    }
} 

Back to Article

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);
    }
} 

Back to Article

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);
    }
} 

Back to Article

Listing Four

class ColorPoint {
    private Point point;
    private Color color;
    // ...etc.
} 

Back to Article

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));
    }
} 

Back to Article

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);
    }
} 

Back to Article


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.