33

The contract for equals(object) method specifies 4 properties to follow: Reflexive, Symmetric, Transitive and Consistent. While I understand the danger of not following Reflexive, Symmetric and Consistent , and can definitely agree its good to follow transitive, I was wondering what harm it would bring if its violating the Transitive property?

Specifically, which of the Java library (or various third party libraries) need the dependency upon equals to be transitive to work correctly? In my understanding, the Collections framework will work if the other 3 properties are well implemented.

Joachim Sauer
  • 302,674
  • 57
  • 556
  • 614
Bhaskar
  • 7,443
  • 5
  • 39
  • 51

4 Answers4

44

Assume three objects a,b,c with

a == a, b == b, c == c (reflexive)
a == b, b == a
b == c, c == b
a != c, c != a

(Pseudocode, x == y stands for x.equals(y)).

Now, let's add the objects to a set:

Set s = new HashSet(); // Set implementation doesn't matter
s.add(b); // s = [b]
s.add(a); // s doesn't change, because a == b
s.add(c); // s doesn't change, because c == b

In contrast, if we were to add them in a different order:

Set s = new HashSet();
s.add(a); // s = [a]
s.add(b); // s doesn't change, because b == a
s.add(c); // s = [a,c], because c != a

That is clearly counter-intuitive and doesn't match the behavior one would expect of a set. For example, it would mean that the union of two sets (i.e. the state of s after s.addAll(someOtherSet)) could depend on the implementation (order of elements) of someOtherSet.

phihag
  • 278,196
  • 72
  • 453
  • 469
  • Thats a real good one :) Though you'd rather want to write ".equals" in the first block instead of "==" ;) – Gandalf Oct 08 '11 at 14:16
  • 2
    @Gandalf I wouldn't. Makes it much more complicated and convoluted than necessary I think ;) Good example. – Voo Oct 08 '11 at 14:20
  • 1
    @Gandalf Alright, wrote `equals`. I understand why the Java guys left it out, but it doesn't exactly make code readable. The criteria for an equivalence relation are language-independent. – phihag Oct 08 '11 at 14:22
  • @Voo You're right. Reverted to `==` and added a comment for nitpicking magicians. – phihag Oct 08 '11 at 14:24
9

At the moment I am not aware of a Java API that has problems with the absence of transitivity. (I am still reflecting for an example).

But independent of that, transitivity is required for equality because that is the mathematical algebraical definition of the equality relation. http://en.wikipedia.org/wiki/Equality_(mathematics)

If transitivity is not present the method must not be called equals because this would be misleading taking into account the expectation one has when hearing/reading "equality". This would contradict the principle of least astonishment. http://en.wikipedia.org/wiki/Principle_of_least_astonishment

[EDIT]

The interesting thing about this is that strictly mathematical speaking the "equality" defined by the java equals method is not an equality but rather the more general equivalence relation http://en.wikipedia.org/wiki/Equivalence_relation because different objects can also be "equal" according to java, thus contradicting the antisymmetry property required for a true equality.

Conclusion:

.equals in Java is a equivalence relation (which still requires transitivity)

== in Java is an equality (or identity) relation

danielkza
  • 2,517
  • 1
  • 22
  • 20
Gandalf
  • 2,350
  • 20
  • 28
1

Consider Object a == b == c with a != c ( non transitive equality )

First problem would be hashcode() contract which requires that hashcodes are equal if objects are equal. And you will be able to add a and c to the same set - this can lead to subtle problems in unexpected places

Konstantin Pribluda
  • 12,329
  • 1
  • 30
  • 35
  • 3
    `hashCode` is not a problem: `int hashCode() {return 0;}` fulfills the implication `x == y ⇒ x.hashCode() == y.hashCode()`. – phihag Oct 08 '11 at 14:08
  • 3
    I don't see why this is a problem. If a == b and b == c then a and b have the same hashcode, and b and c have the same hashcode, so a and c have the same hashcode. Just because a != c does not mean that they cannot share a hashcode. – Eric Lippert Oct 08 '11 at 15:27
  • After hearing some talks from @joshbloch (who did a lot of work developing collections framework in java and other things) I put a lot of caution while writing hashCode and equals - breaking their contract can lead to very strange results – Konstantin Pribluda Oct 08 '11 at 15:57
0
Integer a = new Integer(1);
Integer b = new Integer(1);

a == 1 is true, b == 1 is true but, a == b is not true.

Tunaki
  • 132,869
  • 46
  • 340
  • 423
user5601421
  • 19
  • 1
  • 1
    That neither answers the question nor does it explain something. – Kalle Richter Dec 18 '16 at 00:37
  • Java is the only language have box types of primitive types I know. And I never see another language makes 1 != 1 happen, not python, not javascript, not c#, not c, not go, not rust. – TimYi Mar 27 '17 at 07:10