Comparator and violating the contract of set

Question

The JavaDoc of Comparator states that

It is strongly recommended (though not required) that natural orderings be consistent with equals.

They also give an example of a "strange" behaviour when (a.equals(b) && c.compare(a,b) != 0).

Now, can someone give me an example of a "strange" behavour in case (!a.equals(b) && c.compare(a,b) == 0)? This second case should occur more often than the first because it is easy to forget implementing equals for the compared type when implementing Comparator. It's hard to come up with an example without knowing the implementation of, e.g., TreeSet.

(It's a longer story why this question is relevant to me. And it's not a homework assignment)

If you read the documentation for `Set`, it says that if you have two equal objects, then only one (or neither) of them is stored in the set. This is not true if it's a TreeSet using a comparator that is not consistent with equals. — user253751, Feb 25 '15 at 08:06
See my answer here: https://stackoverflow.com/a/53901802/1441122 — Stuart Marks, Dec 23 '18 at 06:59
Thanks, Stuart Marks. Could you add your comment as regular answer, so that I can accept it? — Ulrich Scholz, Jan 07 '19 at 10:24

OldCurmudgeon · Answer 1 · 2015-02-25T10:25:15.987

Here's a simple demo. We have a class called Strange that implements equals and hashCode using case insensitive string comparisons but implements compareTo case sensitive.

class Strange implements Comparable<Strange> {

    final String s;

    public Strange(String s) {
        this.s = s;
    }

    @Override
    public boolean equals(Object o) {
        // Kind of equals - case insensitive.
        return (o instanceof Strange) && ((Strange) o).s.equalsIgnoreCase(s);
    }

    @Override
    public int hashCode() {
        // Consistent with equals.
        return s.toUpperCase().hashCode();
    }

    @Override
    public int compareTo(Strange o) {
        // Exact ordering including case - inconsistent with equals.
        return s.compareTo(o.s);
    }

    @Override
    public String toString() {
        return s;
    }

}

public void test() {
    Set<Strange> set1 = new HashSet<>();
    Set<Strange> set2 = new TreeSet<>();
    for (String s : new String[]{"Hello", "hello", "Everyone", "everyone"}) {
        Strange strange = new Strange(s);
        set1.add(strange);
        set2.add(strange);
    }
    System.out.println("Set1: " + set1);
    System.out.println("Set2: " + set2);
}

We get - as you probably expect:

Set1: [Hello, Everyone]
Set2: [Everyone, Hello, everyone, hello]

See how putting the strings in a TreeSet changes the outcome? This is because TreeSet uses compareTo while HashSet uses equals and hashCode. This can break things in many different (and most important unexpected) ways because you shouldn't have to know what kind of Set is being used behind the scenes.

This demonstrates (a.equals(b) && a.compareTo(b) != 0) gives strange results. It is easy to show that the opposite issue (!a.equals(b) && a.compareTo(b) == 0) also demonstrates strange results.

score 0 · Answer 2 · answered Feb 25 '15 at 08:08

0

JDK implementations of Collections rely on behavioural relationships like this. Another good example is HashSet, which relies on equals() and hashCode() agreeing.

By "strange" they mean "undefined" - there is no definition of how these classes will behave if they are working with classes that don't follow the rules. They may work perfectly, they may not. But you can not rely on them working properly if your element classes don't adhere to the behaviour described in their javadoc.

answered Feb 25 '15 at 08:08

Bohemian

412,405
93
575
722

Of course, the behaviour is undefined. But usually, there is a deterministic behaviour, depending on a concrete implementation (and sometimes on other factors, like VM version, operating system, ...) I was hoping for a concrete example of non-set behaviour in case of the given contract violation. – Ulrich Scholz Feb 25 '15 at 08:26

Radiodef · Answer 3 · 2015-02-25T09:44:31.320

Suppose the following API:

final class Foo {
    int bar;
    Foo(int bar) { this.bar = bar; }
    public int hashCode() {
        return bar;
    }
    public boolean equals(Object o) {
        return o instanceof Foo && ((Foo)o).bar == bar;
    }
}

static Set<Foo> getSetOpaquely() {???}

I don't know where the Set comes from, just that I need to use it.

Suppose I assume the Set is like HashSet and defined in terms of equals.

They also give an example of a "strange" behaviour when (a.equals(b) && c.compare(a,b) != 0)

Suppose I do

Set<Foo> mySet = getSetOpaquely();
mySet.add(new Foo(1));
System.out.println(mySet.add(new Foo(1));

Suppose my surprise when this prints true because it was a TreeSet with a Comparator

(lhs, rhs) -> lhs == rhs ? 0 : 1

Now, can someone give me an example of a "strange" behavour in case (!a.equals(b) && c.compare(a,b) == 0)?

Suppose I do

Set<Foo> mySet = getSetOpaquely();
mySet.add(new Foo(102));
System.out.println(mySet.add(new Foo(12));

Suppose my surprise when this prints false because it was a TreeSet with a Comparator

(lhs, rhs) -> Integer.compare(lhs.bar % 10, rhs.bar % 10)

Now, there isn't an inherent problem with defining ordering that is inconsistent with equals. The point is that a TreeSet might behave other than specified in the documentation for Set.

This is clearly documented:

[...] the Set interface is defined in terms of the equals operation, but a TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal. The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.

As long as the Comparator isn't hacky and you know that it's a TreeSet with a particular ordering, you won't be surprised. (If it's hacky like (lhs, rhs) -> 1 you might be surprised.)

Comparator and violating the contract of set

3 Answers3