java - como - TreeSet muestra resultados incorrectos

treeset java 8

Question

Mientras trabajaba con un conjunto de árboles, encontré un comportamiento muy peculiar. Según mi entendimiento, este programa debería imprimir dos líneas idénticas:

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

pero extrañamente imprime:

[b]
[a, b] 

¿Por qué el conjunto de árboles se comporta así?

Answer 1

Bueno, esto me sorprendió, no sé si estoy en lo cierto, pero mira esta implementación en 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;
}

Básicamente en su ejemplo, el tamaño del conjunto es igual al tamaño de los argumentos que desea eliminar, por lo que se invoca la condición else. En esa condición, hay una comprobación de si su colección de argumentos para eliminar contains el elemento actual de iterator, y esa verificación c.contains("a") mayúsculas y minúsculas, por lo que comprueba si c.contains("a") y devuelve false, porque c contiene "A" , no "a" , por lo que el elemento no se elimina. Tenga en cuenta que cuando agrega un elemento a su conjunto s.addAll(Arrays.asList("a", "b", "d")); funciona correctamente, porque size() > c.size() ahora es verdadero, por lo que ya no hay ningún control de contenido.

Answer 2

Esto es interesante, así que aquí hay algunas pruebas con resultados:

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

Ahora sin el comparador, funciona como un HashSet<String>() ordenado 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]
}

Ahora desde la documentación:

public boolean removeAll (Colección c)

Elimina de este conjunto todos sus elementos que están contenidos en la colección especificada (operación opcional). Si la colección especificada también es un conjunto, esta operación modifica efectivamente este conjunto de modo que su valor sea la diferencia del conjunto asimétrico de los dos conjuntos.

Esta implementación determina cuál es el más pequeño de este conjunto y la colección especificada, invocando el método de tamaño en cada uno. Si este conjunto tiene menos elementos, la implementación itera sobre este conjunto, verificando cada elemento devuelto por el iterador para ver si está contenido en la colección especificada. Si está tan contenido, se elimina de este conjunto con el método de eliminación del iterador. Si la colección especificada tiene menos elementos, la implementación itera sobre la colección especificada, eliminando de este conjunto cada elemento devuelto por el iterador, utilizando el método de eliminación de este conjunto.

Source

Answer 3

Esto sucede porque un Comparador de SortedSet se usa para clasificar, pero removeAll se basa en el método de equals de cada elemento. De la documentación SortedSet :

Tenga en cuenta que el orden mantenido por un conjunto ordenado (ya sea que se proporcione o no un comparador explícito) debe ser coherente con igual si el conjunto ordenado implementa correctamente la interfaz Set . (Consulte la interfaz Comparable o la interfaz Comparator para obtener una definición precisa de igual a igual ) . Esto es así porque la interfaz Set se define en términos de la operación equals , pero un conjunto ordenado realiza todas las comparaciones de elementos utilizando su compareTo (o compare ) , por lo que dos elementos que se consideran iguales por este método son, desde el punto de vista del conjunto ordenado, iguales. El comportamiento de un conjunto ordenado está bien definido, incluso si su orden es inconsistente con los iguales; simplemente no obedece el contrato general de la interfaz Set .

La explicación de "consistente con iguales" se define en la documentación comparable :

El orden natural para una clase C se dice que es consistente con los iguales si y solo si e1.compareTo(e2) == 0 tiene el mismo valor booleano que e1.equals(e2) para cada e1 y e2 de la clase C Tenga en cuenta que null no es una instancia de ninguna clase, y e.compareTo(null) debería arrojar una NullPointerException aunque e.equals(null) devuelve false .

Se recomienda encarecidamente (aunque no es obligatorio) que los ordenamientos naturales sean consistentes con los iguales. Esto es así porque los conjuntos ordenados (y los mapas ordenados) sin comparadores explícitos se comportan de forma "extraña" cuando se usan con elementos (o claves) cuyo ordenamiento natural es inconsistente con los iguales. En particular, dicho conjunto ordenado (o mapa ordenado) viola el contrato general para conjunto (o mapa), que se define en términos del método equals .

En resumen, el comparador de su Conjunto se comporta de manera diferente que el método de los equals de los elementos, causando un comportamiento inusual (aunque predecible).

Answer 4

Para agregar algo de información acerca de por qué la remove de TreeSet realmente elimina las mayúsculas y minúsculas en su ejemplo (y siempre que siga la ruta if (size() > c.size()) como se explica en la respuesta de @Shadov):

Este es el método de remove en TreeSet :

public boolean remove(Object o) {
        return m.remove(o)==PRESENT;
    }

llama remove de su TreeMap interno:

public V remove(Object key) {
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

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

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

Si hay un Comparator (como en su ejemplo), la entrada se busca en base a este Comparator (esto es hecho por getEntryUsingComparator ), es por eso que realmente se encuentra (luego se elimina), a pesar de la diferencia de caso.