TreeSet показывает неправильный вывод

Ответ 1

Это происходит потому, что для сортировки используется Sort ComparSets Comparator, но removeAll полагается на метод equals для каждого элемента. Из Документация SortedSet:

Обратите внимание, что порядок, поддерживаемый сортированным набором (будь то явный компаратор), должен быть согласован с равным, если отсортированный набор должен правильно реализовать интерфейс Set. (См. Интерфейс Comparable или Comparator для точного определения соответствия с равными.) Это происходит потому, что интерфейс Set определяется в терминах операции equals, но отсортированный набор выполняет все сравнения элементов используя метод compareTo (или compare), поэтому два элемента, которые считаются равными этому методу, равны, с точки зрения сортированного набора. Поведение сортированного множества хорошо определено, даже если его упорядочение не соответствует равным; он просто не подчиняется генеральному контракту интерфейса Set.

Объяснение "согласуется с равными" определено в Сопоставимая документация:

Естественное упорядочение для класса C называется согласованным с равенствами тогда и только тогда, когда e1.compareTo(e2) == 0 имеет то же булево значение, что и e1.equals(e2) для каждого e1 и e2 класса C. Обратите внимание: null не является экземпляром какого-либо класса, а e.compareTo(null) должен вызывать NullPointerException, хотя e.equals(null) возвращает false.

Настоятельно рекомендуется (хотя и не обязательно), чтобы естественные порядки соответствовали равенствам. Это связано с тем, что сортированные наборы (и отсортированные карты) без явных компараторов ведут себя "странно", когда они используются с элементами (или ключами), естественное упорядочение которых несовместимо с равными. В частности, такой сортированный набор (или отсортированная карта) нарушает общий контракт для множества (или карты), который определяется в терминах метода equals.

В заключение, ваш Sets Comparator ведет себя иначе, чем метод equals, что вызывает необычное (хотя и предсказуемое) поведение.

Ответ 2

Ну, это меня удивило, я не знаю, правильно ли я, но посмотрите на эту реализацию в 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() теперь истинно, поэтому больше нет contains.

Ответ 3

Чтобы добавить некоторую информацию о том, почему remove из TreeSet фактически удаляет без учета регистра в вашем примере (и при условии, что вы следуете пути if (size() > c.size()), как описано в ответе @Shadov):

Это метод 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), поэтому он фактически найден (затем удален), несмотря на то, что кейс разница.

Ответ 4

Это интересно, поэтому вот несколько тестов с выходом:

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

Теперь из документации:

public boolean removeAll (коллекция c)

Удаляет из этого множества все его элементы, которые содержатся в указанная коллекция (дополнительная операция). Если указанная коллекция также является множеством, эта операция эффективно изменяет этот набор так, что его значение представляет собой асимметричную разность множеств двух множеств.

Эта реализация определяет, какая из них меньше, и указанной коллекции, путем вызова метода размера для каждого. Если это set имеет меньше элементов, тогда реализация выполняет итерацию по этому установите, проверяя каждый элемент, возвращаемый итератором, в свою очередь, чтобы убедиться, что он содержится в указанной коллекции. Если он так содержится, он удаляется из этого набора с помощью метода удаления итератора. Если указанная коллекция имеет меньшее количество элементов, то реализация выполняет итерацию по указанной коллекции, удаляя из этого набора каждый элемент, возвращаемый итератором, используя этот метод удаления set.

Источник