我在处理单个Comparators
时发现了AbstractSets
的removeAll
方法的这种奇怪行为。
根据比较集合的大小,使用不同的比较器。
它实际上是在API中记录的,但我仍然看不出背后的原因
这是代码:
import java.util.Comparator;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;
public class Test {
public static void main(String[] args) {
// Any comparator. For this example, the length of a string is compared
Set<String> set = new TreeSet<String>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.length() - o2.length();
}
});
set.add("a");
set.add("aa");
set.add("aaa");
set.add("aaaa");
System.out.println(set); // output: [a, aa, aaa, aaaa]
Stack<String> stack = new Stack<String>();
stack.push("b");
stack.push("bb");
stack.push("bbb");
stack.push("bbbb");
set.removeAll(stack); // NO ITEMS ARE REMOVED from the set
System.out.println(set); // output: [a, aa, aaa, aaaa]
// Now let's see what happens if I remove an object from the stack
stack.pop();
set.removeAll(stack); // ALL ITEMS from the stack are removed from the
// set
System.out.println(set); // output: [aaaa]
/* Reason for this strange behaviour: Depending on the size of the
* passed Collection, TreeSet uses either the remove() function of
* itself, or from the Collection object that was passed. While the
* remove() method of the TreeSet uses the comparator to determine
* equality, the remove() method of the passed usually determines
* equality by calling equals() on its objects.
*/
}
}
这是JavaDoc。
您基本上已经创建了未定义的行为,因为您的集合具有不同的相等标准。以任何方式组合集合都只能在集合相同的情况下工作。你基本上违反了A.equals(B)
必须产生与B.equals(A)
相同的结果的约定。
可比较:强烈建议(尽管不是必需的)自然排序与equals一致。这是因为没有显式比较器的排序集(和排序映射)在与自然排序与等于不一致的元素(或键)一起使用时表现得"奇怪"。特别是,这样的排序集(或排序映射)违反了集合(或映射)的一般约定,该约定是根据equals方法定义的。
如果你问他们为什么选择这样实现:
这可能是出于性能原因。考虑具有两个TreeSet
s,一个包含m
元素,另一个包含n
元素。现在考虑从具有n
元素的元素中移除具有m
元素的元素的所有元素。如果我们坚持遍历传入的集合并调用remove,如果m
比n
大得多,这将比遍历当前集合并检查其是否存在(O(m log n) > O(n log m)
)慢得多。比较大小可以防止这种情况发生。
这不是一个完美的系统——如果你把Stack
传递给TreeSet
,那么通过TreeSet
迭代总是比通过Stack
(O(m n) > O(m log n)
)迭代更糟糕的想法,但它将遵循与上述相同的规则。尽管考虑所有允许类型的组合会有点麻烦。
如果您问代码为什么会这样做:
这是removeAll
:的代码
public boolean removeAll(Collection<?> c) {
boolean modified = false;
if (size() > c.size()) {
for (Iterator<?> i = c.iterator(); i.hasNext(); )
modified |= remove(i.next());
} else {
for (Iterator<?> i = iterator(); i.hasNext(); ) {
if (c.contains(i.next())) {
i.remove();
modified = true;
}
}
}
return modified;
}
因此,当Stack
具有比TreeSet
更多或相同数量的元素时(发生在第一种情况下),removeAll
将遍历TreeSet
并移除Stack
中包含的每个元素。由于Stack
使用默认的String
比较,因此不会有任何字符串匹配,也不会删除任何内容。
当Stack
的元素较少时(发生在第二种情况下),removeAll
将遍历Stack
,并对每个元素的TreeSet
调用remove,这将使用您的Comparator
,从而删除所有长度匹配的元素,只留下长度为4的元素,对应于弹出的元素。