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’interfaceComparable
ouComparator
pour une définition précise de la cohérence avec les égaux. ) En effet, l’interfaceSet
est définie en termes d’opérationsequals
, mais un ensemble sortingé effectue toutes les comparaisons d’éléments en utilisant sacompareTo
(oucompare
) 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’interfaceSet
.
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 sie1.compareTo(e2) == 0
a la même valeur booléenne quee1.equals(e2)
pour chaquee1
ete2
de la classeC
Notez quenull
n’est une instance d’aucune classe et quee.compareTo(null)
doite.equals(null)
NullPointerException
même sie.equals(null)
renvoiefalse
.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 super K> k = (Comparable super K>) 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