Java ArrayList-comment savoir si deux listes sont égales, l'ordre ne compte pas?

j'ai deux tableaux de type Answer(self-made class).

j'aimerais comparer les deux listes pour voir si elles contiennent le même contenu, mais sans ordre et sans compter.

exemple:

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

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

est-il une façon simple de faire cette? Ou vais-je devoir faire une boucle emboîtée, et vérifier manuellement chaque index des deux listes?

Note: Je ne peux pas les changer d'ArrayList à un autre type de liste, ils doivent le rester.

96
demandé sur iaacp 2012-11-22 00:01:36

16 réponses

vous pouvez trier les deux listes en utilisant Collections.sort() et ensuite utiliser la méthode égal. Une solution légèrement meilleure est de vérifier d'abord si elles sont de la même longueur Avant de commander, si elles ne le sont pas, alors elles ne sont pas égales, puis de trier, puis d'utiliser des égaux. Par exemple, si vous aviez deux listes de Chaînes, ce serait quelque chose comme:

public  boolean equalLists(List<String> one, List<String> 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 A. R. S.
    one = new ArrayList<String>(one); 
    two = new ArrayList<String>(two);   

    Collections.sort(one);
    Collections.sort(two);      
    return one.equals(two);
}
103
répondu Jacob Schoen 2012-11-21 20:30:23

probablement la façon la plus facile pour n'importe quelle "liste serait:

listA.containsAll(listB) && listB.containsAll(listA)
108
répondu 2012-11-21 20:33:58

Apache Commons Collections à la rescousse une fois de plus:

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

List<String> listC = Arrays.asList("a", "b", "c");
List<String> 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)

Les retours true iff le donné Collection s contiennent exactement le même éléments avec exactement le même cardinalités.

C'est-à-dire, iff le la cardinalité de e dans un est égal à la cardinalité de e dans b , pour chaque l'élément e dans un ou b .

paramètres:

  • a - la première collection, ne doit pas être null
  • b - la seconde collection, ne doit pas être null

Renvoie: true iff les collections contiennent les mêmes éléments avec le même cardinalités.

68
répondu acdcjunior 2016-02-16 18:36:44
// 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<String> list1, final List<String> 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<String, Count> 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<String, Count> entry : counts.entrySet()) {
        if (entry.getValue().count != 0) return false;
    }

    return true;
}
8
répondu cHao 2017-08-21 06:32:10

c'est basé sur la solution @cHao. J'ai inclus plusieurs corrections et améliorations de performances. Cela va environ deux fois plus vite que la solution égale-commandé-copie. Fonctionne pour tout 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.
 * <p>
 * Empty collections and {@code null} are regarded as equal.
 */
public static <T> boolean haveSameElements(Collection<T> col1, Collection<T> 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<T, Count> 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;
}
5
répondu DiddiZ 2014-02-02 14:56:56

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), alors il y a un moyen de le faire sans avoir à trier:

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

cela créera un Set de chaque List , et puis utiliser HashSet 's equals méthode qui (bien sûr) ne tient pas compte de la commande.

si la cardinalité est importante, alors vous devez vous limiter aux installations fournies par List ; la réponse de @jschoen serait plus appropriée dans ce cas.

5
répondu Isaac 2018-06-06 00:40:09

pensez à la façon 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 avez à me dire s'ils contiennent les mêmes éléments. Comment le feriez-vous?

l'une des approches, mentionnée ci-dessus, consiste à trier les listes puis à aller élément par élément pour voir si elles sont égales (ce que fait List.equals ). Cela signifie que soit vous êtes autorisé à modifier les listes ou vous êtes autorisé à les copier-et sans connaître les affectation, Je ne peux pas savoir si l'un ou l'autre / les deux sont autorisés.

une autre approche serait de passer en revue chaque liste, en comptant combien de fois chaque élément apparaît. Si deux listes ont le même compte à la fin, ils ont les mêmes éléments. Le code pour ce qui serait de traduire chaque liste à une carte de elem -> (# of times the elem appears in the list) et ensuite appeler equals sur les deux cartes. Si les cartes sont HashMap , chacune de ces traductions est une opération O(N), comme l'est la comparaison. Qui va pour vous donner une jolie algorithme efficace en termes de temps, au prix d'un peu plus de mémoire.

4
répondu yshavit 2012-11-21 23:16:17

j'ai eu ce même problème et est venu avec une solution différente. Celui-ci fonctionne aussi 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<Object>(fst);
      List<?> csnd = new ArrayList<Object>(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:

  • moins de O(N2) complexité (bien que je n'ai pas testé c'est de la vraie performance en comparaison des solutions dans d'autres réponses ici);
  • sort tôt;
  • vérifie null;
  • fonctionne même lorsque les doublons sont impliqués: si vous avez un tableau [1,2,3,3] et un autre tableau [1,2,2,3] la plupart des solutions ici vous disent qu'elles sont les mêmes lorsque vous ne considérez pas l'ordre. Cette solution permet d'éviter cela en retirant des éléments égaux des listes temporaires;
  • utilise l'égalité sémantique ( equals ) et non l'égalité de référence ( == );
  • ne fait pas de tri, de sorte qu'ils n'ont pas besoin d'être sortable (par implement Comparable ) pour cette solution travailler.
4
répondu Chalkos 2015-08-13 00:07:33

je dirais que ces réponses manquent une astuce.

Bloch, dans son essentiel, merveilleux, concis Java efficace , dit, dans le point 47, titre "connaître et utiliser les bibliothèques", "pour résumer, ne pas réinventer la roue". Et il donne plusieurs raisons très claires pour ne pas le faire.

il y a quelques réponses ici qui suggèrent des méthodes de CollectionUtils dans la bibliothèque des collections communes Apache mais aucune n'a repéré le plus belle, élégante façon de répondre à cette question :

Collection<Object> 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.

}

coupables : c'est-à-dire les éléments qui ne sont pas communs aux deux Lists . Il est relativement simple de déterminer quels sont les coupables de list1 et de list2 en utilisant les Termes CollectionUtils.intersection( list1, culprits ) et CollectionUtils.intersection( list2, culprits ) .

Cependant, il a tendance à tomber en morceaux dans des cas comme { "a", "a", "b" } disjunction avec { "a", "b", "b" } ... sauf ce n'est pas un défaut du logiciel, mais inhérente à la nature de l'subtilités/ambiguïtés de la tâche souhaitée.


NB j'ai d'abord été déçu qu'aucune des méthodes CollectionUtils ne fournisse une version surchargée vous permettant d'imposer votre propre Comparator (pour que vous puissiez redéfinir equals en fonction de vos besoins).

mais à partir de collections4 4.0 il y a une nouvelle classe, Equator qui " détermine égalité entre les objets de type T". Sur l'examen du code source de collections4 CollectionUtils.java ils semblent l'utiliser avec certaines méthodes, mais pour autant que je puisse en juger, ce n'est pas applicable aux méthodes en haut du fichier, en utilisant la classe CardinalityHelper ... qui comprennent disjunction et intersection .

je suppose que le peuple Apache n'a pas encore eu le temps de le faire parce que c'est non-trivial: il faudrait créer quelque chose comme Classe " AbstractEquatingCollection "qui, au lieu d'utiliser ses éléments" inhérents equals et hashCode méthodes devrait plutôt utiliser ceux de Equator pour toutes les méthodes de base, tels 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 ... vous devez attendre jusqu'à ce que les classes concrètes telles que HashSet et ArrayList avant add est mis en œuvre. Un véritable casse-tête.

dans le temps, regardez cet espace, je suppose. La solution provisoire évidente serait d'envelopper tous vos éléments dans une classe d'emballage sur mesure qui utilise equals et hashCode pour mettre en œuvre le genre d'Égalité que vous voulez... puis manipulez Collections de ces objets d'emballage.

4
répondu mike rodent 2017-01-01 20:36:02

convertissant les listes en Multiset de Guava fonctionne très bien. Ils sont comparés indépendamment de leur ordre et les éléments dupliqués sont également pris en compte.

static <T> boolean equalsIgnoreOrder(List<T> a, List<T> 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));
3
répondu Natix 2016-05-13 16:34:41

Solution qui utilise la méthode de soustraction des collectes:

import static org.apache.commons.collections15.CollectionUtils.subtract;

public class CollectionUtils {
  static public <T> boolean equals(Collection<? extends T> a, Collection<? extends T> 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;
  }
}
2
répondu maxdanilkin 2014-01-28 11:12:04

si vous n'espérez pas trier les collections et vous avez besoin du résultat que ["A" "B" "C"] n'est pas égal à ["B" "B" A" C"],

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

n'est pas suffisant, vous devez probablement vérifier la taille aussi:

    List<String> l1 =Arrays.asList("A","A","B","C");
    List<String> l2 =Arrays.asList("A","B","C");
    List<String> 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<String> l1, List<String> l2) {
        return l1.size()==l2.size() && l1.containsAll(l2)&&l2.containsAll(l1);
}
1
répondu Jaskey 2017-02-20 08:54:25

Le Meilleur des deux mondes [@DiddiZ, @Chalkos]: celui-ci s'appuie principalement sur la méthode @Chalkos, mais corrige un bug (ifst.next()), et améliore les contrôles initiaux (pris de @DiddiZ) ainsi que 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 une fonction de hachage ou de tri, et permettant une existence précoce sur un-égalité, il s'agit de la mise en œuvre la plus efficace à ce jour. Sauf si vous avez une collection longueur dans les milliers ou plus, et une fonction de hachage très simple.

public static <T> boolean isCollectionMatch(Collection<T> one, Collection<T> 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<T> ctwo = new ArrayList<>(two);

    for (T itm : one) {
        Iterator<T> 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;
}
0
répondu jazzgil 2016-01-08 23:45:07

c'est une alternative pour vérifier l'égalité des listes de tableaux qui peuvent 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<String> getSortedArrayList(List<String> arrayList)
{
    String[] array = arrayList.toArray(new String[arrayList.size()]);

    Arrays.sort(array, new Comparator<String>()
    {
        @Override
        public int compare(String o1, String 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<String> listA, List<String> listB)
{
    listA = getSortedArrayList(listA);
    listB = getSortedArrayList(listB);

    String[] arrayA = listA.toArray(new String[listA.size()]);
    String[] arrayB = listB.toArray(new String[listB.size()]);

    return Arrays.deepEquals(arrayA, arrayB);
}
0
répondu Sa Qada 2016-08-02 14:28:10

si vous vous souciez de l'ordre, alors utilisez juste la méthode égale:

list1.equals(list2)
0
répondu Ramesh Kumar 2016-11-24 13:13:10

Dans ce cas, les listes {"a", "b"} et {"b",""} sont égaux. Et {"a", "b"} et {"b","a","c"} ne sont pas égaux. Si vous utilisez la liste des objets complexes, n'oubliez pas de remplacer égale "méthode 151930920", comme containsAll l'utilise à l'intérieur.

if (oneList.size() == secondList.size() && oneList.containsAll(secondList)){
        areEqual = true;
}
-1
répondu Andrew 2016-12-12 14:39:22