CODEWITHSUNDEEP
javadictionaryset
kal
kal

Reputation: 29381

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

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?

Upvotes: 4

Views: 9677

Answers (7)

Diego Pino
Diego Pino

Reputation: 11586

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

Upvotes: 1

user85421
user85421

Reputation: 29680

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

[]]

Upvotes: 1

user98989
user98989

Reputation:

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.

Upvotes: 0

Tom Hawtin - tackline
Tom Hawtin - tackline

Reputation: 147164

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.

Upvotes: 0

Fabian Steeg
Fabian Steeg

Reputation: 45734

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

Upvotes: 0

Jon Skeet
Jon Skeet

Reputation: 1500805

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.

Upvotes: 3

Michael Myers
Michael Myers

Reputation: 191945

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

Upvotes: 4

Related Questions