Java ArrayList: ¿cómo puedo saber si dos listas son iguales, el orden no importa?

Tengo dos ArrayLists de tipo Answer (clase hecha a sí misma).

Me gustaría comparar las dos listas para ver si contienen los mismos contenidos, pero sin importar el orden.

Ejemplo:

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

List.equals establece que dos listas son iguales si contienen el mismo tamaño, contenido y orden de elementos. Quiero lo mismo, pero sin importar el orden.

¿Hay una manera simple de hacer esto? ¿O tendré que hacer un ciclo for nested y verificar manualmente cada índice de ambas listas?

Nota: No puedo cambiarlos de ArrayList a otro tipo de lista, deben permanecer así.

Puede ordenar ambas listas usando Collections.sort() y luego usar el método equals. Una solución un poco mejor es comprobar primero si son de la misma longitud antes de ordenar, si no lo son, entonces no son iguales, luego ordenar, luego usar iguales. Por ejemplo, si tuviera dos listas de cadenas, sería algo así como:

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

Probablemente la forma más fácil para cualquier lista sería:

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

Apache Commons Collections al rescate una vez más:

 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 

Documentos:

org.apache.commons.collections4.CollectionUtils

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

Devuelve true si la Collection dada contiene exactamente los mismos elementos con exactamente las mismas cardinalidades.

Es decir, si la cardinalidad de e en a es igual a la cardinalidad de e en b , para cada elemento e en a o b .

Parámetros:

  • a – la primera colección, no debe ser null
  • b – la segunda colección, no debe ser null

Devuelve: true si las colecciones contienen los mismos elementos con las mismas cardinalidades.

 // 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; } 

Esto se basa en la solución @cHao. Incluí varias correcciones y mejoras de rendimiento. Esto funciona aproximadamente dos veces más rápido que la solución equals-ordered-copy. Funciona para cualquier tipo de colección. Las colecciones vacías y nulas se consideran iguales. Use para su ventaja;)

 /** * 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; }

Piensa cómo lo harías tú mismo, sin una computadora o un lenguaje de progtwigción. Te doy dos listas de elementos, y tienes que decirme si contienen los mismos elementos. ¿Como lo harias?

Un enfoque, como se mencionó anteriormente, es ordenar las listas y luego ir elemento por elemento para ver si son iguales (que es lo que hace List.equals ). Esto significa que puede modificar las listas o puede copiarlas, y sin conocer la asignación, no puedo saber si se permiten ambas o ambas cosas.

Otro enfoque sería revisar cada lista, contando cuántas veces aparece cada elemento. Si ambas listas tienen los mismos recuentos al final, tienen los mismos elementos. El código para eso sería traducir cada lista a un mapa de elem -> (# of times the elem appears in the list) y luego llamar a equals en los dos mapas. Si los mapas son HashMap , cada una de esas traducciones es una operación O (N), como lo es la comparación. Eso te dará un algoritmo bastante eficiente en términos de tiempo, a costa de algo de memoria adicional.

Tuve el mismo problema y se me ocurrió una solución diferente. Este también funciona cuando hay duplicados involucrados:

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

Ventajas en comparación con algunas otras soluciones:

  • menos de O (N²) complejidad (aunque no he probado su rendimiento real en comparación con las soluciones en otras respuestas aquí);
  • sale temprano;
  • comprueba nulo;
  • funciona incluso cuando hay duplicados: si tiene una matriz [1,2,3,3] y otra matriz [1,2,2,3] mayoría de las soluciones le dicen que son las mismas al no considerar el orden. Esta solución evita esto al eliminar elementos iguales de las listas temporales;
  • usa igualdad semántica ( equals ) y no igualdad de referencia ( == );
  • no ordena itens, por lo que no necesitan ser ordenables (mediante implement Comparable ) para que esta solución funcione.

Yo diría que estas respuestas pierden un truco.

Bloch, en su esencial, maravillosa y concisa Java efectiva , dice, en el ítem 47, título “Conozca y use las bibliotecas”, “Para resumir, no reinvente la rueda”. Y él da varias razones muy claras por las que no.

Aquí hay algunas respuestas que sugieren métodos de CollectionUtils en la biblioteca de colecciones de Apache Commons, pero ninguno ha detectado la forma más bella y elegante de responder a esta pregunta :

 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. } 

Culpables : es decir, los elementos que no son comunes a ambas Lists . Determinar qué culpables pertenecen a list1 y cuál a list2 es relativamente sencillo usando CollectionUtils.intersection( list1, culprits ) y CollectionUtils.intersection( list2, culprits ) .
Sin embargo, tiende a desmoronarse en casos como {“a”, “a”, “b”} disjunction con {“a”, “b”, “b”} … excepto que esto no es un error del software, pero inherente a la naturaleza de las sutilezas / ambigüedades de la tarea deseada.


NB Al principio me decepcionó que ninguno de los métodos de CollectionUtils proporciona una versión sobrecargada que le permite imponer su propio Comparator (para que pueda redefinir equals para que se adapte a sus propósitos).

Pero desde collections4 4.0 hay una nueva clase, Equator que “determina la igualdad entre los objetos de tipo T”. Al examinar el código fuente de collections4 CollectionUtils.java, parecen estar usando esto con algunos métodos, pero por lo que puedo ver, esto no es aplicable a los métodos en la parte superior del archivo, usando la clase CardinalityHelper … que incluyen disjunction e intersection .

Supongo que la gente Apache aún no ha llegado a esto porque no es trivial: tendría que crear algo así como una clase “AbstractEquatingCollection”, que en lugar de utilizar los elementos equals inherentes de los elementos y los métodos hashCode tendrían que utilice los de Equator para todos los métodos básicos, como add , contains , etc. NB, de hecho, cuando mira el código fuente, AbstractCollection no implementa add , ni sus subclases abstractas, como AbstractSet … tiene que esperar hasta que se implementen las clases concretas como HashSet y ArrayList before add . Un gran dolor de cabeza

Mientras tanto, mira este espacio, supongo. La solución obvia provisional sería envolver todos sus elementos en una clase contenedora personalizada que use equals y hashCode para implementar el tipo de igualdad que desea … luego manipule las Collections de estos objetos contenedoras.

Convertir las listas a Guava’s Multiset funciona muy bien. Se comparan independientemente de su orden y también se tienen en cuenta los elementos duplicados.

 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 cardinalidad de los elementos no importa (es decir, los elementos repetidos se consideran como uno), entonces hay una forma de hacerlo sin tener que ordenar:

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

Esto creará un Set de cada List , y luego usará el HashSet de HashSet equals que (por supuesto) ignora el orden.

Si la cardinalidad es importante, entonces debe limitarse a las instalaciones proporcionadas por List ; La respuesta de @jschoen sería más apropiada en ese caso.

Solución que aprovecha el método de resta 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 no espera ordenar las colecciones y necesita el resultado de que [“A” “B” “C”] no es igual a [“B” “B” “A” “C”],

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

no es suficiente, probablemente necesites verificar el tamaño:

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

Lo mejor de ambos mundos [@DiddiZ, @Chalkos]: este se basa principalmente en el método @Chalkos, pero corrige un error (ifst.next ()) y mejora los controles iniciales (tomados de @DiddiZ) y elimina la necesidad de copie la primera colección (simplemente elimina elementos de una copia de la segunda colección).

Al no requerir una función de hashing o clasificación, y permitir una existencia temprana en la falta de igualdad, esta es la implementación más eficiente hasta el momento. Eso es a menos que tenga una longitud de recostackción de miles o más, y una función de hashing muy 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; } 

Es una forma alternativa de verificar la igualdad de las listas de matrices que pueden contener valores nulos:

 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) { String[] array = arrayList.toArray(new String[arrayList.size()]); Arrays.sort(array, new Comparator() { @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 listA, List 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); } 

Si te importa el orden, simplemente usa el método igual:

 list1.equals(list2) 

En ese caso, las listas {“a”, “b”} y {“b”, “a”} son iguales. Y {“a”, “b”} y {“b”, “a”, “c”} no son iguales. Si usa una lista de objetos complejos, recuerde anular el método de iguales , ya que containsAll lo usa dentro.

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