Skip to main content

All equals() are not born equal

Posted by schaefa on October 29, 2004 at 2:37 PM PDT

During a discussion with a colleague we started talking about the problems of equals() with inheritance. He mentioned Joshua Bloch's Effective Java book which covers this topic quit well but more or less said that this problem cannot be resolved. This was enough to get me hooked onto this problem and I came up with a solution quite fast. Afterwards I started to think about other solutions and their problems. Because all of them made sense I started to question myself if my solution was even necessary and until now I am still not sure if it does or if it is just a solution for theorists in the ivory tower. But even if it is just theory I think it is an interesting problem to talk about.

The equals() method defined in java.lang.Object has some restrictions to its implementation. Among other things it needs to symmetrical meaning that target of the method can switch places with the argument and it must yield the same result (if A is equal to B then B must be equal to A). Also it must be transient meaning that if A is equal to B and B equal to C then also A must be equal to C. There are two common ways to implement an equals() method:

  1. The method ensures that it only compares to instance of its own kind (class)
  2. The method ensures that it tests against an interface of base class and only tests if they are equal to that. An example is the AbstractList in java.util.

The first is a simple solution but breaks if someone tries to extend this class. The second solution cannot test parts of the extension of a class without breaking the rules for equals.

Before I start explaining my solution I want to come up with a use case to reason why equals() should work with inheritance. The use case is quite synthetic but it is the best model I could think of that is short and intuitive. In math you have the irrational numbers representing numbers like 1, ½, pi or e. An extension of it are the complex numbers that contain two irrational numbers one for the real part and for the imaginary part. For more information visit Dave's short course on Complex Numbers. In complex numbers you can also express pure irrational numbers by setting the imaginary part to 0. This means that e = e + 0i. For us this means that an irrational number should be equal to a complex number if the imaginary part is set to 0. The algebra behind the complex numbers does ensure that equals is symmetrical and transient. Now, shouldn't this be good enough for us software developers to achieve the same? The first solution mentioned above fails because it breaks with inheritance and the second solution will break mathematical because any complex number with the same real part as the irrational number will be equal because there is no test against the complex part.

To solve the equals() test with inheritance the equals() method must be written with inheritance in mind because only a sub class is able to determine equality correctly but in order to support symmetry the base class must delegate the test to the sub class if a sub class instance is given. An equals method of the irrational number would look like:

 1 public boolean equals(Object o) {
2    if(o == null) return false;
3    if(o == this) return true;
4    if(o instanceof Irrational) {
5       if(o.getClass().equals(Irrational.class)) {
6          return ((Irrational)o).real == real;
7       } else {
8           return o.equals(this);
9       }
10    }
11    return false;
12 }

In line 5 we check if the given object is of the same type and then we test is like normal. In line 8 the given argument is of a sub class so we delegate the test to this sub class with this instance as parameter.

In the Complex class we need to adjust the equals method a little bit:\

 1 public boolean equals(Object o) {
2    if(o == null) return false;
3    if(o == this) return true;
4    if(o instanceof Complex) {
5       if(o.getClass().equals(Complex)) {
6          return ((Complex)o).real == real && ((Complex)o).imag == imag;
7       } else {
8           return o.equals(this);
9       }
10    } else {
11       if(o.getClass().equals(Irrational.class)) {
12          return imag == 0 && ((Irrational)o).real == real;
13       }
14    }
15    return false;
16 }

The only difference to the Irrational's equals method is that we here check in line 11 if the given object is of type Irrational and then we allow the instances to be equal if the imaginary part is set to 0 and the real part is equal. So line 8 in both classes ensures that the equals() method is symmetrical and line 11 to 13 in the Complex class ensures that it is transient. Even thought this looks great so far it has three problems:

  • All sub class must overwrite and adjust the equals() method otherwise line 8 in the base class will create an endless loop
  • The equals() method in the sub class cannot call the equals() method in the base class otherwise it ends up in an endless loop, too
  • Line 11 in the Complex class cannot check against a sub class of Irrational in a different branch (meaning it is not a sub class of Complex, too)

The solution above works quite well even when it has some restrictions. Still, you might think that this is not useful in the real world but imagine a scenario where you have an ArrayList of Irrational type (generic types in JDK 1.5). This allows you to add Irrational numbers but also Complex numbers. If the equals() method would not support inheritance you would not be able to find an Irrational instance with a Complex instance that represents the same irrational number because the imaginary part is set to zero. One would also fail if one will search a Complex number with imaginary part set to zero with an Irrational instance. In a world of distributed computing sometimes we cannot just change all the code and so inheritance provides a way to introduce changes with localized side effects. This also means we must put some effort in the design of a class so that inheritance does not break especially on crucial parts like equality.

Happy coding – Andy

Related Topics >>