Java ArrayList – Comment savoir si deux listes sont égales, l’ordre étant sans importance?

J’ai deux ArrayLists de type Answer (classe self-made).

Je voudrais comparer les deux listes pour voir si elles contiennent le même contenu, mais sans importance.

Exemple:

//These should be equal. ArrayList listA = {"a", "b", "c"} ArrayList listB = {"b", "c", "a"} 

List.equals indique que deux listes sont égales si elles contiennent la même taille, le même contenu et l’ordre des éléments. Je veux la même chose, mais sans importance.

Existe-t-il un moyen simple de le faire? Ou dois-je faire une boucle nestede et vérifier manuellement chaque index des deux listes?

Note: Je ne peux pas les changer de ArrayList en un autre type de liste, ils doivent le restr.

Vous pouvez sortinger les deux listes à l’aide de Collections.sort() , puis utiliser la méthode égale. Une solution légèrement meilleure consiste à vérifier d’abord s’ils ont la même longueur avant l’ordre, s’ils ne le sont pas, alors ils ne sont pas égaux, puis sortingent, puis utilisent des nombres égaux. Par exemple, si vous aviez deux listes de chaînes, ce serait quelque chose comme:

 public boolean equalLists(List one, List two){ if (one == null && two == null){ return true; } if((one == null && two != null) || one != null && two == null || one.size() != two.size()){ return false; } //to avoid messing the order of the lists we will use a copy //as noted in comments by ARS one = new ArrayList(one); two = new ArrayList(two); Collections.sort(one); Collections.sort(two); return one.equals(two); } 

Le moyen le plus simple pour une liste serait probablement:

 listA.containsAll(listB) && listB.containsAll(listA) 

Apache Commons Collections à la rescousse encore une fois:

 List listA = Arrays.asList("a", "b", "b", "c"); List listB = Arrays.asList("b", "c", "a", "b"); System.out.println(CollectionUtils.isEqualCollection(listA, listB)); // true 

 List listC = Arrays.asList("a", "b", "c"); List listD = Arrays.asList("a", "b", "c", "c"); System.out.println(CollectionUtils.isEqualCollection(listC, listD)); // false 

Docs:

org.apache.commons.collections4.CollectionUtils

 public static boolean isEqualCollection(java.util.Collection a, java.util.Collection b) 

Renvoie true si les Collection données contiennent exactement les mêmes éléments avec exactement les mêmes cardinalités.

En d’autres termes, si la cardinalité de e dans a est égale à la cardinalité de e dans b , pour chaque élément e dans a ou b .

Paramètres:

  • a – la première collection ne doit pas être null
  • b – la deuxième collection ne doit pas être null

Retourne: true Si les collections contiennent les mêmes éléments avec les mêmes cardinalités.

 // helper class, so we don't have to do a whole lot of autoboxing private static class Count { public int count = 0; } public boolean haveSameElements(final List list1, final List list2) { // (list1, list1) is always true if (list1 == list2) return true; // If either list is null, or the lengths are not equal, they can't possibly match if (list1 == null || list2 == null || list1.size() != list2.size()) return false; // (switch the two checks above if (null, null) should return false) Map counts = new HashMap<>(); // Count the items in list1 for (String item : list1) { if (!counts.containsKey(item)) counts.put(item, new Count()); counts.get(item).count += 1; } // Subtract the count of items in list2 for (String item : list2) { // If the map doesn't contain the item here, then this item wasn't in list1 if (!counts.containsKey(item)) return false; counts.get(item).count -= 1; } // If any count is nonzero at this point, then the two lists don't match for (Map.Entry entry : counts.entrySet()) { if (entry.getValue().count != 0) return false; } return true; } 

Ceci est basé sur la solution @cHao. J’ai inclus plusieurs correctifs et améliorations de performances. Cela tourne à peu près deux fois plus vite que la solution de copie ordonnée égale. Fonctionne pour n’importe quel type de collection. Les collections vides et nulles sont considérées comme égales. Utilisez à votre avantage;)

 /** * Returns if both {@link Collection Collections} contains the same elements, in the same quantities, regardless of order and collection type. * 

* Empty collections and {@code null} are regarded as equal. */ public static boolean haveSameElements(Collection col1, Collection col2) { if (col1 == col2) return true; // If either list is null, return whether the other is empty if (col1 == null) return col2.isEmpty(); if (col2 == null) return col1.isEmpty(); // If lengths are not equal, they can't possibly match if (col1.size() != col2.size()) return false; // Helper class, so we don't have to do a whole lot of autoboxing class Count { // Initialize as 1, as we would increment it anyway public int count = 1; } final Map counts = new HashMap<>(); // Count the items in list1 for (final T item : col1) { final Count count = counts.get(item); if (count != null) count.count++; else // If the map doesn't contain the item, put a new count counts.put(item, new Count()); } // Subtract the count of items in list2 for (final T item : col2) { final Count count = counts.get(item); // If the map doesn't contain the item, or the count is already reduced to 0, the lists are unequal if (count == null || count.count == 0) return false; count.count--; } // If any count is nonzero at this point, then the two lists don't match for (final Count count : counts.values()) if (count.count != 0) return false; return true; }

Pensez à la manière dont vous le feriez vous-même, en l’absence d’un ordinateur ou d’un langage de programmation. Je vous donne deux listes d’éléments, et vous devez me dire si elles contiennent les mêmes éléments. Comment le feriez-vous?

Une approche, comme mentionné ci-dessus, consiste à sortinger les listes, puis à passer élément par élément pour voir si elles sont égales (ce qui est le cas de List.equals ). Cela signifie que vous êtes autorisé à modifier les listes ou que vous êtes autorisé à les copier – et sans connaître l’affectation, je ne peux pas savoir si l’une / l’autre ou les deux sont autorisées.

Une autre approche serait de parcourir chaque liste en comptant combien de fois chaque élément apparaît. Si les deux listes ont les mêmes comptes à la fin, elles ont les mêmes éléments. Le code pour cela serait de traduire chaque liste en une carte d’ elem -> (# of times the elem appears in the list) et ensuite appeler des equals sur les deux cartes. Si les cartes sont HashMap , chacune de ces traductions est une opération O (N), tout comme la comparaison. Cela va vous donner un algorithme assez efficace en termes de temps, au prix d’une mémoire supplémentaire.

J’ai eu le même problème et j’ai proposé une solution différente. Celui-ci fonctionne également lorsque des doublons sont impliqués:

 public static boolean equalsWithoutOrder(List fst, List snd){ if(fst != null && snd != null){ if(fst.size() == snd.size()){ // create copied lists so the original list is not modified List cfst = new ArrayList(fst); List csnd = new ArrayList(snd); Iterator ifst = cfst.iterator(); boolean foundEqualObject; while( ifst.hasNext() ){ Iterator isnd = csnd.iterator(); foundEqualObject = false; while( isnd.hasNext() ){ if( ifst.next().equals(isnd.next()) ){ ifst.remove(); isnd.remove(); foundEqualObject = true; break; } } if( !foundEqualObject ){ // fail early break; } } if(cfst.isEmpty()){ //both temporary lists have the same size return true; } } }else if( fst == null && snd == null ){ return true; } return false; } 

Avantages par rapport à d’autres solutions:

  • complexité inférieure à O (N²) (bien que je n’ai pas testé sa performance réelle par rapport aux solutions dans d’autres réponses ici);
  • sort tôt;
  • vérifie la valeur null;
  • fonctionne même lorsque des doublons sont impliqués: si vous avez un tableau [1,2,3,3] et un autre tableau [1,2,2,3] plupart des solutions ici vous indiquent qu’elles sont identiques lorsque vous ne considérez pas la commande. Cette solution évite cela en supprimant des éléments égaux des listes temporaires;
  • utilise l’égalité sémantique ( equals ) et non l’égalité de référence ( == );
  • ne sortinge pas les autres, ils n’ont donc pas besoin d’être sortingables (par implement Comparable ) pour que cette solution fonctionne.

Je dirais que ces réponses manquent un tour.

Bloch, dans son Java essentiel, merveilleux et concis, dit, au point 47, intitulé “Connaître et utiliser les bibliothèques”, “Pour résumer, ne réinventez pas la roue”. Et il donne plusieurs raisons très claires pourquoi pas.

Il y a quelques réponses ici qui suggèrent des méthodes de CollectionUtils dans la bibliothèque Apache Commons Collections, mais aucune n’a trouvé la manière la plus élégante de répondre à cette question :

 Collection culprits = CollectionUtils.disjunction( list1, list2 ); if( ! culprits.isEmpty() ){ // ... then in most cases you will ardently wish to do something to these culprits: // at the very least, name-and-shame them. } 

Les coupables : les éléments qui ne sont pas communs aux deux Lists . Déterminer les coupables qui appartiennent à list1 et à list2 est relativement simple en utilisant CollectionUtils.intersection( list1, culprits ) et CollectionUtils.intersection( list2, culprits ) .
Cependant, il a tendance à se désagréger dans des cas tels que {“a”, “a”, “b”} disjunction avec {“a”, “b”, “b”} … sauf que cela ne constitue pas une défaillance du logiciel, mais inhérent à la nature des subtilités / ambiguïtés de la tâche souhaitée.


NB: Au début, je suis déçu qu’aucune des méthodes CollectionUtils ne propose une version surchargée vous permettant d’imposer votre propre Comparator (pour que vous puissiez redéfinir les résultats en fonction de vos besoins).

Mais à partir de collections4 4.0, il existe une nouvelle classe, Equator qui “détermine l’égalité entre les objects de type T”. A l’examen du code source de collections4 CollectionUtils.java, ils semblent utiliser cette méthode avec certaines méthodes, mais pour autant que je sache, cela ne s’applique pas aux méthodes en haut du fichier, en utilisant la classe CardinalityHelper … qui comprennent la disjunction et l’ intersection .

Je suppose que les personnes Apache ne sont pas encore parvenues à cela parce que ce n’est pas sortingvial: vous devriez créer quelque chose comme une classe “AbstractEquatingCollection” qui, au lieu d’utiliser les méthodes d’ equals et de hashCode de ses éléments, devrait plutôt utiliser ceux de l’ Equator pour toutes les méthodes de base, telles que add , contains , etc. NB en fait, lorsque vous regardez le code source, AbstractCollection n’implémente pas add , ni ses sous-classes abstraites telles que AbstractSet … jusqu’à ce que les classes concrètes telles que HashSet et ArrayList avant add soient implémentées. Assez mal à la tête.

En attendant, surveille cet espace, je suppose. La solution provisoire évidente consisterait à envelopper tous vos éléments dans une classe de wrapper sur mesure qui utilise equals et hashCode pour implémenter le type d’égalité souhaité, puis manipuler les Collections de ces objects wrapper.

La conversion des listes au Multiset de Guava fonctionne très bien. Ils sont comparés indépendamment de leur ordre et les éléments en double sont également pris en compte.

 static  boolean equalsIgnoreOrder(List a, List b) { return ImmutableMultiset.copyOf(a).equals(ImmutableMultiset.copyOf(b)); } assert equalsIgnoreOrder(ImmutableList.of(3, 1, 2), ImmutableList.of(2, 1, 3)); assert !equalsIgnoreOrder(ImmutableList.of(1), ImmutableList.of(1, 1)); 

Si la cardinalité des éléments n’a pas d’importance (c’est-à-dire que les éléments répétés sont considérés comme un seul), il existe un moyen de le faire sans avoir à sortinger:

boolean result = new HashSet<>(listA).equals(new HashSet<>(listB));

Cela créera un Set de chaque List , puis utilisera la méthode equals HashSet qui (bien sûr) ignore la commande.

Si la cardinalité est importante, vous devez vous limiter aux fonctionnalités fournies par List ; La réponse de @ jschoen serait plus appropriée dans ce cas.

Solution qui exploite la méthode de soustraction CollectionUtils:

 import static org.apache.commons.collections15.CollectionUtils.subtract; public class CollectionUtils { static public  boolean equals(Collection a, Collection b) { if (a == null && b == null) return true; if (a == null || b == null || a.size() != b.size()) return false; return subtract(a, b).size() == 0 && subtract(a, b).size() == 0; } } 

Si vous n’espérez pas sortinger les collections et que vous avez besoin du résultat que [“A” “B” “C”] n’est pas égal à [“B” “B” “A” “C”],

 l1.containsAll(l2)&&l2.containsAll(l1) 

ne suffit pas, vous devez probablement vérifier la taille aussi:

  List l1 =Arrays.asList("A","A","B","C"); List l2 =Arrays.asList("A","B","C"); List l3 =Arrays.asList("A","B","C"); System.out.println(l1.containsAll(l2)&&l2.containsAll(l1));//cautions, this will be true System.out.println(isListEqualsWithoutOrder(l1,l2));//false as expected System.out.println(l3.containsAll(l2)&&l2.containsAll(l3));//true as expected System.out.println(isListEqualsWithoutOrder(l2,l3));//true as expected public static boolean isListEqualsWithoutOrder(List l1, List l2) { return l1.size()==l2.size() && l1.containsAll(l2)&&l2.containsAll(l1); } 

Le meilleur des deux mondes [@DiddiZ, @Chalkos]: celui-ci repose principalement sur la méthode @Chalkos, mais corrige un bug (ifst.next ()), améliore les vérifications initiales (sockets depuis @DiddiZ) et supprime la nécessité de copier la première collection (supprime simplement les éléments d’une copie de la deuxième collection).

Ne nécessitant pas de fonction de hachage ni de sorting, et permettant une existence précoce sur la non-égalité, c’est la mise en œuvre la plus efficace à ce jour. C’est à moins que vous ayez une longueur de collection de plusieurs milliers ou plus, et une fonction de hachage très simple.

 public static  boolean isCollectionMatch(Collection one, Collection two) { if (one == two) return true; // If either list is null, return whether the other is empty if (one == null) return two.isEmpty(); if (two == null) return one.isEmpty(); // If lengths are not equal, they can't possibly match if (one.size() != two.size()) return false; // copy the second list, so it can be modified final List ctwo = new ArrayList<>(two); for (T itm : one) { Iterator it = ctwo.iterator(); boolean gotEq = false; while (it.hasNext()) { if (itm.equals(it.next())) { it.remove(); gotEq = true; break; } } if (!gotEq) return false; } // All elements in one were found in two, and they're the same size. return true; } 

C’est une autre façon de vérifier l’égalité des listes de tableaux pouvant contenir des valeurs nulles:

 List listA = Arrays.asList(null, "b", "c"); List listB = Arrays.asList("b", "c", null); System.out.println(checkEquality(listA, listB)); // will return TRUE private List getSortedArrayList(List arrayList) { Ssortingng[] array = arrayList.toArray(new Ssortingng[arrayList.size()]); Arrays.sort(array, new Comparator() { @Override public int compare(Ssortingng o1, Ssortingng o2) { if (o1 == null && o2 == null) { return 0; } if (o1 == null) { return 1; } if (o2 == null) { return -1; } return o1.compareTo(o2); } }); return new ArrayList(Arrays.asList(array)); } private Boolean checkEquality(List listA, List listB) { listA = getSortedArrayList(listA); listB = getSortedArrayList(listB); Ssortingng[] arrayA = listA.toArray(new Ssortingng[listA.size()]); Ssortingng[] arrayB = listB.toArray(new Ssortingng[listB.size()]); return Arrays.deepEquals(arrayA, arrayB); } 

Si vous vous souciez de l’ordre, utilisez simplement la méthode des égaux:

 list1.equals(list2) 

Dans ce cas, les listes {“a”, “b”} et {“b”, “a”} sont égales. Et {“a”, “b”} et {“b”, “a”, “c”} ne sont pas égaux. Si vous utilisez une liste d’objects complexes, n’oubliez pas de remplacer la méthode égale , car la propriété containsAll l’ utilise à l’intérieur.

 if (oneList.size() == secondList.size() && oneList.containsAll(secondList)){ areEqual = true; }