Which method does Set.removeAll() use underneath: equals or compareTo?

Question

Consider the code:

class A {

  private int i;

  boolean equals( Object t) {
      if (this == t)
          return true;
      if (!( t instanceof A))
          return false;
      if (this.i == t.i);
  }

}

Map<String,A> orig;
Map<String,B> dup;

I am trying to do this

orig.entrySet().removeAll(dup.entrySet());

I see that the equals method is called; is this always true, or might it call compareTo instead?

Answer 1

Yes, it calls equals(). compareTo() could only be used if the Set knew that it contained Comparable objects (sorted sets, for instance, might possibly do this).

Answer 2

It depends on the implementation.

For instance, a HashSet will use hashCode and equals. A TreeSet will probably use compareTo. Ultimately, so long as your types behave appropriately it shouldn't matter.

Answer 3

Some Set implementations rely on hashCode (e.g. HashSet). That is why you should always override hashCode too when you override equals.

Answer 4

The only implementation within the Java library that I am aware of that wont do this is IdentityHashMap. TreeMap for instance does not have an appropriate Comparator.

Answer 5

I don't see where compareTo is used; the javadoc for remove() for the Map interface says "More formally, if this map contains a mapping from key k to value v such that (key==null ? k==null : key.equals(k)), that mapping is removed." While for the Set interface it similarly says "More formally, removes an element e such that (o==null ? e==null : o.equals(e)), if the set contains such an element."

Note that removeAll()'s javadoc doesn't say how it operates, which means, as others have said, that it's an implementation detail.

In Sun's Java, according to Bloch in his Effective Java (if I remember correctly), it iterates over the collection and calls remove(), but he stresses that you must never assume that's how it's always done.

Answer 6

The TreeSet uses the compareTo, try this:

public class A {

    private int i;

    A(int i) {
        this.i = i;
    }

    @Override
    public boolean equals(Object t) {
        if (this == t)
            return true;
        if (!( t instanceof A))
            return false;
        return (this.i == ((A)t).i);
    }

    public static void main(String[] args) {
        List<A> remove = Arrays.asList(new A(123), new A(789));
        Set<A> set = new TreeSet<A>(new Comparator<A>() {
            @Override
            public int compare(A o1, A o2) {
                return o1.i - o2.i;  
                // return 0; // everything get removed
            }
        });
        set.add(new A(123));
        set.add(new A(456));
        set.add(new A(789));
        set.add(new A(999));

        set.removeAll(remove);
        for (A a : set) {
            System.out.println(a.i);
        }
        System.out.println("done");
    }
}

make the Comparator always return 0 and everything will be removed! Same happens if not using a Comparator but implementing Comparable.

The TreeSet is based on a TreeMap which uses the compareTo in getEntry.
In the Javadoc of the TreeSet you can (finally) read:

...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...

[]]

Answer 7

http://java.sun.com/j2se/1.5.0/docs/api/java/util/Collection.html

"Implementations are free to implement optimizations whereby the equals invocation is avoided, for example, by first comparing the hash codes of the two elements."

Most likely will use equals, but considering the statement above, you cannot fully rely on equals() to be called. Remember that it's always a good idea to override hashCode() whenever you override equals().