TreeSet显示错误的输出

Question

TreeSet显示错误的输出

在使用树集时,我发现了非常奇特的行为.根据我的理解,这个程序应该打印两个相同的行:

public class TestSet {
    static void test(String... args) {
        Set<String> s = new TreeSet<String>(String.CASE_INSENSITIVE_ORDER);
        s.addAll(Arrays.asList("a", "b"));
        s.removeAll(Arrays.asList(args));
        System.out.println(s);
    }

    public static void main(String[] args) {
        test("A");
        test("A", "C");
    }
}

Run Code Online (Sandbox Code Playgroud)

但奇怪的是它打印:

[b]
[a, b]

Run Code Online (Sandbox Code Playgroud)

为什么树集会表现得像这样？

Answer 1

VGR*_*VGR 40

这是因为SortedSet的Comparator用于排序,但removeAll依赖于equals每个元素的方法.从SortedSet文档:

请注意,如果有序集合要正确实现接口,则由有序集合维护的排序(无论是否提供显式比较器)必须与equals一致Set.(请参阅Comparable接口或Comparator接口以获得与equals一致的精确定义.)这是因为Set接口是根据equals操作定义的,但是有序集使用其compareTo(或compare)方法执行所有元素比较,因此两个元素是从排序集的角度来看,这种方法被认为是相等的.即使排序与equals不一致,排序集的行为也是明确定义的; 它只是不遵守Set界面的一般合同.

可比文档中定义了"与equals一致"的解释:

一类的自然顺序C被说成是与equals一致当且仅当e1.compareTo(e2) == 0具有相同的布尔值的e1.equals(e2)每一个e1和e2阶级的C.请注意,这null不是任何类的实例,并且e.compareTo(null)应该抛出一个NullPointerException偶数e.equals(null)返回false.

强烈建议(尽管不要求)自然排序与equals一致.这是因为没有显式比较器的有序集(和有序映射)在与自然顺序与equals不一致的元素(或键)一起使用时表现得"奇怪".特别地,这样的有序集(或有序映射)违反了集合(或映射)的一般契约,其根据该equals方法定义.

总之,Set的比较器的行为与元素的equals方法不同,导致异常(虽然可预测)行为.

这里的问题恰恰是依赖合同会产生意想不到的结果.调用方法的集合的大小以及参数确定使用哪个方法(迭代`this`或参数).根据它,删除可以通过`this.remove(argumentElement)`或通过`argument.contains(elementFromThis)`来确定.因此**可以**但并不总是依赖于给定参数的`contains()`语义,而`remove()`也可以在`contains()`上运行,但对于`TreeSet`它没有,它在`compareTo()`值上运行.... (5认同)
基本上`AbstractSet`的工作假设`contains()`和`remove()`对于每个集合都有相同的语义(相等检查),但是从它继承的`TreeSet`会违反该契约.仅仅因为它提到这并不能使它好,当然也不是当结果不一致时(即使可预测).这里的结果取决于实现细节而不是语义. (5认同)
小说明，在正常情况下，`removeAll` 依赖于 `contains`，如您在 Shadov 的回答中所见，它依赖于 `equals`，但根据相对集合大小，它可能只调用 `remove`，而在 `TreeSet` 中仅依赖于在比较器上，而不是相等。所以实际上你的第一句话需要调整，因为它只在某些情况下依赖于 `equals`。 (2认同)
要突出显示G_H注释中的一个点,如果将另一个TreeSet(String.CASE_INSENSITIVE_ORDER)作为removeAll(而不是列表)的参数传递,它将按预期工作,因为两个集合现在都遵循相同的contains()定义. (2认同)
我很惊讶`TreeSet`没有覆盖`removeAll()`来使用比较器相等. (2认同)

Answer 2

Sha*_*dov 15

嗯,这让我感到惊讶,我不知道我是否正确,但看看这个实现AbstractSet:

public boolean removeAll(Collection<?> c) {
  Objects.requireNonNull(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;
}

Run Code Online (Sandbox Code Playgroud)

基本上在您的示例中,set的大小等于要删除的参数的大小,因此调用else条件.在那种情况下,检查你的参数集合是否删除contains了迭代器的当前元素,并且该检查区分大小写,因此它检查是否c.contains("a")返回false,因为c包含"A",而不是"a",因此元素不会被删除.请注意,当您向集合添加元素时,s.addAll(Arrays.asList("a", "b", "d"));它可以正常工作,因为size() > c.size()现在是正确的,因此不再进行contains检查.

来自 SortedSet 的 Javadoc：“请注意，如果排序集要正确实现 Set 接口，则排序集维护的排序（无论是否提供显式比较器）必须与 equals 一致。（请参阅 Comparable 接口或 Comparator用于精确定义与等于一致的接口。） ... (2认同)
这是因为 Set 接口是根据 equals 操作定义的，但是有序集合使用它的 compareTo（或 compare）方法执行所有元素比较，因此从该方法的角度来看，两个元素被认为相等排序集，相等。有序集合的行为是明确定义的，即使它的排序与 equals 不一致；它只是不遵守 Set 接口的一般约定。” (2认同)
@JacobG。检查哪个集合最小并迭代那个集合（“this”或参数）是一种优化，以避免在“this”包含一个元素时迭代 10000 个元素的参数。但是这里出乎意料的副作用是相当戏剧性的。 (2认同)

归档时间：	8 年，4 月前
查看次数：	1542 次
最近记录：	8 年，3 月前