TreeSet 给出不正确的输出 - Java8

问题描述 投票：0回答：4

在处理树集时，我发现了非常奇怪的行为。

根据我的理解，以下程序应该打印两行相同的行：

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");
    }
}

但奇怪的是它打印：

[b]
[a, b]

我无法理解 - 为什么树集会这样？

java treeset
4个回答
42
投票

发生这种情况是因为 SortedSet 的 Comparator 用于排序，但 removeAll 依赖于每个元素的 

equals
方法。来自 SortedSet 文档：

请注意，如果排序集要正确实现 Set 接口，则排序集维护的顺序（无论是否提供显式比较器）必须

与 equals
一致。 （有关 
 与 equals 一致的精确定义，请参阅
Comparable
 接口或
Comparator 接口。）之所以如此，是因为 
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
 方法不同，导致异常（尽管可以预测）的行为。
    





      

      
      
      

      

        

          

            

              
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;
}




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





      

      
      
      

      

        

          

            

              
3
投票

              
            

          

        

        
remove
 的 
TreeSet
 实际上在示例中不区分大小写地删除的信息（并且前提是您遵循@Shadov 答案中所解释的 
if (size() > c.size())
 路径）：
这是
remove
中的
TreeSet
方法：
public boolean remove(Object o) {
        return m.remove(o)==PRESENT;
    }



它从内部调用 
remove
 
TreeMap
:
public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    V oldValue = p.value;
    deleteEntry(p);
    return oldValue;
}



调用 
getEntry
:
 final Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }



如果有 
Comparator
 （如您的示例中所示），则会根据此 
Comparator
 搜索条目（这是由 
getEntryUsingComparator
 完成的），这就是为什么它实际上被找到（然后被删除），尽管存在大小写差异.
    





      

      
      
      

      

        

          

            

              
0
投票

              
            

          

        

        



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

public static void main(String[] args) {
    test("C");          output: [a, b]
    test("C", "A");     output: [b]
    test("C", "A","B"); output: [a, b, c]
    test("B","C","A");  output: [a, b, c]
    test("K","C");      output: [a, b]
    test("C","K","M");  output: [a, b, c] !!
    test("C","K","A");  output: [a, b, c] !!
}




现在没有比较器，它的工作方式就像排序的
HashSet<String>()
：


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

public static void main(String[] args) {
    test("c");          output: [a, b]
    test("c", "a");     output: [b]
    test("c", "a","b"); output: []
    test("b","c","a");  output: []
    test("k","c");      output: [a, b]
    test("c","k","m");  output: [a, b]
    test("c","k","m");  output: [a, b]
}




现在从文档来看：




  
公共布尔值removeAll（集合c）

  
  
从该集合中删除包含在该集合中的所有元素
  指定集合（可选操作）。如果指定集合
  也是一个集合，这个操作有效地修改了这个集合，使得
  它的值是两个集合的不对称集合差。

  
  
此实现确定哪个是该集合中较小的一个，并且
  通过对每个集合调用 size 方法来获取指定的集合。如果这
  set 的元素较少，那么实现会对此进行迭代
  set，依次检查迭代器返回的每个元素是否
  它包含在指定的集合中。如果它是这样包含的，那么它
  使用迭代器的remove方法从该集合中删除。如果
  指定集合元素较少，则执行
  迭代指定的集合，从该集合中删除每个
  迭代器返回的元素，使用此集合的删除方法。





来源

    


      

      
    

  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.