Why does Set.contains() not seem to be using o.equals()?

Question

I have a TreeSet containing wrappers which store a Foo object at a certain position, defined like so:

class Wrapper implements Comparable<Wrapper> {
  private final Foo foo;
  private final Double position;

  ...

  @Override boolean equals(Object o) {

    ... 

    if(o instanceof Wrapper)
        return o.getFoo().equals(this.foo);

    if(o instanceof Foo)
        return o.equals(this.foo);
  }

  @Override public int compareTo(MarkerWithPosition o) {
      return position.compareTo(o.getPosition());
  }
}

NavigableSet<Wrapper> fooWrappers = new TreeSet<Wrapper>();

because I want my TreeSet to be ordered by position but searchable by foo. But when I perform these operations:

Foo foo = new Foo(bar);
Wrapper fooWrapper = new Wrapper(foo, 1.0);
fooWrappers.add(fooWrapper);

fooWrapper.equals(new Wrapper(new Foo(bar), 1.0));
fooWrapper.equals(new Foo(bar));
fooWrappers.contains(fooWrapper);
fooWrappers.contains(new Wrapper(foo, 1.0));
fooWrappers.contains(new Wrapper(new Foo(bar), 1.0));
fooWrappers.contains(new Wrapper(foo, 2.0));
fooWrappers.contains(foo);

I get:

true
true
true
true
true
false
Exception in thread "main" java.lang.ClassCastException: org.gridqtl.Marker cannot be cast to java.lang.Comparable
    at java.util.TreeMap.getEntry(TreeMap.java:325)
    at java.util.TreeMap.containsKey(TreeMap.java:209)
    at java.util.TreeSet.contains(TreeSet.java:217)

when I expecting them all to return true, so it seems like TreeSet.contains is not using my equals method as the API suggests. Is there another method I need to overwrite?

possible duplicate of [Treeset.contains() problem](http://stackoverflow.com/questions/3432772/treeset-contains-problem) — Miquel, Jul 30 '12 at 13:19
Precisely Because comparision in TreeSet is not consistent with equals — Geek, Jul 30 '12 at 13:22

score 10 · Accepted Answer · answered Jul 30 '12 at 13:17

10

TreeSet is a Set implementation that does indeed use compareTo, as explained in the javadoc - emphasis mine:

Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because 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.

answered Jul 30 '12 at 13:17

assylias

321,522
82
660
783

Does this mean I should create a `compareTo(Foo)` as well? But then my `Comparable` cannot be parameterised. – bountiful Jul 30 '12 at 13:24
@fophillips, you _really_ can't do what you're trying to do. You can't force a `TreeMap` to be ordered in one way but to search in another way. The first thing I'd try is to stop your `equals` method from messing with different types as it currently is, and do an explicit linear search through the set...which you'd need to do anyway, since you wanted the ordering to be different from the search. – Louis Wasserman Jul 30 '12 at 13:27
It means that foo1.equals(foo2) should be equivalent to foo1.compareTo(foo2) == 0, or you will have unexpected results. It is not the case here because Wrapper(foo, 1) is equal to Wrapper(foo, 2) but compareTo does not return 0. You might want to reconsider your design. – assylias Jul 30 '12 at 13:28
But the [JavaDoc](http://docs.oracle.com/javase/6/docs/api/java/lang/Comparable.html#compareTo(T)) states that "It is strongly recommended, but not strictly required that (x.compareTo(y)==0) == (x.equals(y))", so I'm not sure why what I am trying to do is so wrong. – bountiful Jul 30 '12 at 13:32
1

It's recommended because violating that recommendation can cause weird, confusing behavior...as you've just discovered. (The behavior is still well-defined -- it never uses `equals`, only `compareTo` -- but as stated in the quoted Javadoc, your comparator "*must* be consistent with equals" if you expect the `Set` interface guarantees to hold.) – Louis Wasserman Jul 30 '12 at 13:34

score 0 · Answer 2 · edited Nov 03 '12 at 22:46

0

TreeSet is an ordered set.

equals cannot give you ordering information, hence TreeSet has to use something else.

This 'something else' is Comparable interface, or its cousin Comparator interface.

Both interfaces provide an information about how to order 2 objects of a class.

edited Nov 03 '12 at 22:46

Frank

16,476
7
38
51

answered Jul 30 '12 at 13:19

Alexander Pogrebnyak

44,836
10
105
121

Why does Set.contains() not seem to be using o.equals()?

2 Answers2