TreeSet affiche une sortie incorrecte

Question

Tout en travaillant avec un ensemble d'arbres, j'ai trouvé un comportement très particulier. Selon ma compréhension, ce programme devrait imprimer deux lignes identiques:

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

mais étrangement cela imprime:

 [b]
[a, b] 
 

Pourquoi les arbres se comportent-ils de la sorte?

Answer 1

Cela se produit car un SortedSet du Comparateur est utilisé pour le tri, mais removeAll s'appuie sur l' equals méthode de chaque élément. À partir de la SortedSet de la documentation:

Notez que la commande est maintenue par un ensemble trié (que ce soit ou non explicitement la comparaison est fourni) doit être compatible avec égal à égal si l'ensemble trié est à mettre correctement en œuvre l' Set interface. (Voir l' Comparable interface ou Comparator interface pour une définition précise de la cohérence avec d'égal à égal.) Il en est ainsi parce que l' Set interface est définie dans les termes de l' equals opération, mais un ensemble trié effectue tous les éléments de comparaisons à l'aide de son compareTo (ou compare) méthode, donc, deux éléments qui sont considérés comme égaux par cette méthode sont, du point de vue de l'ensemble trié, l'égalité. Le comportement d'un ensemble trié est bien défini, même si son classement est incompatible avec égal à égal; simplement, il ne respecte pas les conditions générales du contrat de l' Set interface.

L'explication de l'expression "conformément à égal" est défini dans le Comparable de la documentation:

L'ordre naturel pour une classe C qui est dit pour être compatible avec des égaux si et seulement si e1.compareTo(e2) == 0 a la même valeur booléenne que e1.equals(e2) pour chaque e1 et e2 de la classe C. Notez que null n'est pas une instance de classe, et e.compareTo(null) jette NullPointerException même si e.equals(null) retours false.

Il est fortement recommandé (mais pas obligatoire) que les ordonnancements être compatible avec d'égal à égal. Il en est ainsi parce que les ensembles classés (et le tri des cartes) sans l'accord des comparateurs de se comporter "étrangement" lorsqu'ils sont utilisés avec des éléments (ou clés) dont l'ordre naturel est incompatible avec égal à égal. En particulier, un tel ensemble trié (ou triés à la carte) viole les conditions générales du contrat pour l'ensemble (ou map), qui est définie en termes de equals méthode.

En résumé, l'Comparateur se comporte différemment que les éléments" equals méthode, provoquant inhabituelle (bien que prévisible) le comportement.

Answer 2

Eh bien, cela m'a surpris, je ne sais pas si je suis correct, mais regardez cette mise en œuvre, 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;
}

En gros, dans votre exemple, la taille de l'ensemble est égale à la taille des arguments que vous souhaitez supprimer, de sorte que la condition else est invoquée. Dans cette condition, il y a une case si votre collection d'arguments pour supprimer contains l'élément courant de itérateur, et que l'enregistrement est sensible à la casse, il vérifie si c.contains("a") et elle retourne false, c contient "A", pas "a", de sorte que l'élément n'est pas supprimé. Notez que lorsque vous ajoutez un élément à votre ensemble s.addAll(Arrays.asList("a", "b", "d")); il fonctionne correctement, parce que, size() > c.size() est maintenant vrai, donc il n'y a pas d' contains contrôle plus.

Answer 3

Pour ajouter quelques informations sur les raisons de l' remove de TreeSet supprime réellement le cas-insensively dans votre exemple (et à condition que vous suivez l' if (size() > c.size()) chemin d'accès comme expliqué dans la réponse par @Shadov) :

C'est l' removeméthode de TreeSet :

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

il appelle remove de son interne 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;
}

qui demande 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 il y a un Comparator (comme dans votre exemple), l'entrée est recherché sur cette base Comparator (ce qui est fait par getEntryUsingComparator), c'est pourquoi il est effectivement trouvé (puis retiré) , en dépit de la différence de casse.

Answer 4

Ce qui est intéressant, voici donc quelques tests avec sortie:

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

Maintenant, sans le comparateur, il fonctionne exactement comme une triés 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]
}

Maintenant à partir de la documentation:

public boolean removeAll(Collection c)

Supprime de l'ensemble de ses éléments qui sont contenus dans le collection spécifiée (facultatif de l'opération). Si la collection spécifiée aussi, cette opération de manière efficace modifie cette série, de sorte que sa valeur est à l'asymétrie de différence entre les deux ensembles.

Cette mise en œuvre détermine qui est le plus petit de cet ensemble et la collection spécifiée, en invoquant la méthode de dimensionnement sur chaque. Si ce a moins d'éléments, puis la mise en œuvre itère sur ce ensemble, la vérification de chaque élément retourné par l'itérateur à son tour, pour voir si elle est contenue dans la collection spécifiée. Si c'est le cas, il est retiré de cet ensemble avec l'itérateur de la méthode remove. Si l' collection spécifiée a moins d'éléments, puis la mise en œuvre parcourt la collection spécifiée, la suppression de cet ensemble chaque élément retourné par l'itérateur, à l'aide de cet ensemble de supprimer la méthode.

Source