TreeSet affiche des résultats incorrects

En travaillant avec un arbre, 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(Ssortingng... args) { Set s = new TreeSet(Ssortingng.CASE_INSENSITIVE_ORDER); s.addAll(Arrays.asList("a", "b")); s.removeAll(Arrays.asList(args)); System.out.println(s); } public static void main(Ssortingng[] args) { test("A"); test("A", "C"); } } 

mais étrangement il imprime:

 [b] [a, b] 

Pourquoi le jeu d’arbres se comporte-t-il comme ça?

Cela se produit car Comparator de SortedSet est utilisé pour le sorting, mais removeAll s’appuie sur la méthode equals de chaque élément. De la documentation SortedSet :

Notez que l’ordre géré par un ensemble sortingé (qu’un comparateur explicite soit fourni ou non) doit être cohérent avec les égaux si l’ensemble sortingé doit implémenter correctement l’interface Set . (Voir l’interface Comparable ou Comparator pour une définition précise de la cohérence avec les égaux. ) En effet, l’interface Set est définie en termes d’opérations equals , mais un ensemble sortingé effectue toutes les comparaisons d’éléments en utilisant sa compareTo (ou compare ) Ainsi, deux éléments jugés égaux par cette méthode sont, du sharepoint vue du jeu sortingé, égaux. Le comportement d’un ensemble sortingé est bien défini même si son classement est incohérent avec les égaux; il ne parvient tout simplement pas à respecter le contrat général de l’interface Set .

L’explication de «compatible avec les égaux» est définie dans la documentation comparable :

On dit que l’ordre naturel d’une classe C est égal à égal à 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 une instance d’aucune classe et que e.compareTo(null) doit e.equals(null) NullPointerException même si e.equals(null) renvoie false .

Il est fortement recommandé (mais pas obligatoire) que les classements naturels soient cohérents avec les égaux. Cela est dû au fait que les ensembles sortingés (et les cartes sortingées) sans comparateurs explicites se comportent “étrangement” lorsqu’ils sont utilisés avec des éléments (ou des clés) dont l’ordre naturel est incompatible avec les égaux. En particulier, un tel ensemble sortingé (ou une carte sortingée) viole le contrat général pour set (ou map), qui est défini en termes de méthode equals .

En résumé, le comparateur de votre ensemble se comporte différemment de la méthode des éléments, ce qui entraîne un comportement inhabituel (bien que prévisible).

Eh bien, cela m’a surpris, je ne sais pas si j’ai raison, mais regardez cette implémentation dans 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 set est égale à la taille des arguments à supprimer. La condition else est donc appelée. Dans cette condition, il y a une vérification si votre collection d’arguments à supprimer contains l’élément actuel de l’iterator, et cette vérification est sensible à la casse, donc il vérifie si c.contains("a") et il retourne false, car c contient "A" , pas "a" , donc l’élément n’est pas supprimé. Notez que lorsque vous ajoutez un élément à votre ensemble s.addAll(Arrays.asList("a", "b", "d")); cela fonctionne correctement, car size() > c.size() est maintenant vrai, donc il n’y a plus de contrôle de contains .

Pour append des informations sur la raison pour laquelle la remove de TreeSet supprime réellement la casse dans votre exemple (et à condition que vous suiviez le chemin if (size() > c.size()) comme expliqué dans la réponse de @Shadov):

Ceci est la méthode remove dans TreeSet :

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

il appelle remove de son TreeMap interne:

 public V remove(Object key) { Entry p = getEntry(key); if (p == null) return null; V oldValue = p.value; deleteEntry(p); return oldValue; } 

qui appelle getEntry

  final Entry 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 k = (Comparable) key; Entry 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; } 

S’il existe un Comparator (comme dans votre exemple), l’entrée est recherchée en fonction de ce Comparator (cela est fait par getEntryUsingComparator ), c’est pourquoi il est effectivement trouvé (puis supprimé), malgré la différence de casse.

C’est intéressant, voici donc quelques tests avec sortie:

 static void test(Ssortingng... args) { Set s =new TreeSet(Ssortingng.CASE_INSENSITIVE_ORDER); s.addAll(Arrays.asList( "a","b","c")); s.removeAll(Arrays.asList(args)); System.out.println(s); } public static void main(Ssortingng[] 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, cela fonctionne exactement comme un HashSet() sortingé HashSet() :

  static void test(Ssortingng... args) { Set s = new TreeSet();// s.addAll(Arrays.asList( "a","b","c")); s.removeAll(Arrays.asList(args)); System.out.println(s); } public static void main(Ssortingng[] 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:

booléen public removeAll (Collection c)

Supprime de cet ensemble tous ses éléments contenus dans la collection spécifiée (opération facultative). Si la collection spécifiée est également un ensemble, cette opération modifie effectivement cet ensemble afin que sa valeur soit la différence de jeu asymésortingque des deux ensembles.

Cette implémentation détermine quel est le plus petit de cet ensemble et la collection spécifiée, en appelant la méthode de taille sur chacun. Si cet ensemble contient moins d’éléments, l’implémentation effectue une itération sur cet ensemble, vérifiant tour à tour chaque élément renvoyé par l’iterator pour voir s’il est contenu dans la collection spécifiée. S’il est ainsi contenu, il est supprimé de cet ensemble avec la méthode remove de l’iterator. Si la collection spécifiée contient moins d’éléments, l’implémentation effectue une itération sur la collection spécifiée, supprimant de cet ensemble chaque élément renvoyé par l’iterator, en utilisant la méthode remove de cet ensemble.

La source