Java ArrayList - 如何判断两个列表是否相等,顺序无关紧要？

Question

我有两种ArrayList类型Answer(自制类).

我想比较两个列表,看看它们是否包含相同的内容,但是没有订单问题.

例:

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

List.equals声明如果两个列表包含相同的大小,内容和元素顺序,则它们是相等的.我想要同样的事情,但没有订单问题.

有一个简单的方法吗？或者我是否需要执行嵌套for循环,并手动检查两个列表的每个索引？

注意:我无法将它们更改ArrayList为其他类型的列表,它们需要保留它.

Answer 1

对任何列表来说,最简单的方法可能是:

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

Answer 2

您可以使用Collections.sort()然后使用equals方法对两个列表进行排序.一个更好的解决方案是首先检查它们在订购前是否长度相同,如果不是,则它们不相等,然后排序,然后使用等于.例如,如果您有两个字符串列表,它将类似于:

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

Answer 3

Apache Commons Collections再次拯救:

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

文档:

org.apache.commons.collections4.CollectionUtils

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

true如果给定的Collections包含具有完全相同基数的完全相同的元素,则 返回iff .

也就是说,当且仅当的基数Ë在一个等于的基数ë在b,对于每个元件é在一个或b.

参数:

• a - 第一个集合,绝对不能 null
• b - 第二个集合,绝对不能 null

返回: trueiff集合包含具有相同基数的相同元素.

Answer 4

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

Answer 5

如果项目的基数无关紧要(意思是:重复的元素被认为是一个),那么有一种方法可以做到这一点而无需排序:

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

这将创建一个Setout List,然后使用HashSet的equals方法(当然)忽略排序.

如果基数很重要,那么你必须将自己局限于所提供的设施List; 在这种情况下,@ jschoen的答案会更合适.

Answer 6

我会说这些答案错过了一个窍门。

Bloch在他的必不可少的，精妙的，简洁的有效Java中说，在项目47中，标题为“了解并使用库”，“总而言之，不要重新发明轮子”。他给出了几个非常清楚的理由说明为什么不这样做。

这里有一些答案建议使用CollectionUtilsApache Commons Collections库中的方法，但没有一个发现最美丽，优雅的方法来回答这个问题：

Collection<Object> culprits = CollectionUtils.disjunction( list1, list2 );
if( ! culprits.isEmpty() ){
  // ... do something with the culprits, i.e. elements which are not common

}

罪魁祸首：即两者都不共同的元素Lists。确定哪些罪犯属于list1，哪些list2是相对简单的使用CollectionUtils.intersection( list1, culprits )和CollectionUtils.intersection( list2, culprits )。
但是，在诸如{“ a”，“ a”，“ b”} disjunction和{“ a”，“ b”，“ b”}的情况下，它趋于崩溃……除了这不是软件的故障，而是所需任务的微妙/模糊性的本质所固有的。

注意：最初，我很失望，没有一种CollectionUtils方法提供了一个重载的版本，使您可以使用自己的版本Comparator（因此您可以重新定义equals以适合您的目的）。

但是在collections4 4.0中有一个新类，Equator“确定类型T的对象之间的相等性”。在检查collections4 CollectionUtils.java的源代码时，似乎使用了某些方法，但是据我所知，这不适用于文件顶部使用CardinalityHelper类的方法。包括disjunction和intersection。

我猜想Apache人还没有解决这个问题，因为它是不平凡的：您将不得不创建类似“ AbstractEquatingCollection”类的类，该类不使用其元素的内在equals和hashCode方法，而必须使用那些的Equator所有基本方法，如add，contains等NB其实当你看到的源代码，AbstractCollection不执行add，也没有它的抽象子类，如AbstractSet...你必须要等到具体的类，如HashSet和ArrayList前add被实施。很头疼。

同时，我想同时观察这个空间。显而易见的临时解决方案是将您的所有元素包装在一个定制的包装器类中，该类使用equals并hashCode实现您想要的等式...然后操纵Collections这些包装器对象。

Answer 7

这是基于@cHao解决方案.我包括了一些修复和性能改进.这相当于等份复制解决方案的两倍.适用于任何集合类型.空集合和null被视为相等.利用你的优势;)

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

    // At this point, both collections are equal.
    // Both have the same length, and for any counter to be unequal to zero, there would have to be an element in col2 which is not in col1, but this is checked in the second loop, as @holger pointed out.
    return true;
}

Answer 8

想一想在没有计算机或编程语言的情况下如何自己做。我给您提供了两个元素列表，您必须告诉我它们是否包含相同的元素。你会怎么做？

如上所述，一种方法是对列表进行排序，然后逐个元素查看它们是否相等（这是正确的List.equals）。这意味着您要么被允许修改列表，要么被允许复制它们-在不知道分配的情况下，我不知道是否允许其中一个/两个。

另一种方法是遍历每个列表，计算每个元素出现多少次。如果两个列表的末尾计数相同，则它们具有相同的元素。这样做的代码是将每个列表转换为的映射，elem -> (# of times the elem appears in the list)然后equals在两个映射上调用。如果map是HashMap，则每个翻译都是O（N）操作，比较也是如此。就时间而言，这将为您提供一种非常有效的算法，但会消耗一些额外的内存。

Answer 9

我遇到了同样的问题，并提出了不同的解决方案。当涉及重复项时，此选项也适用：

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

与其他解决方案相比的优势：

• 小于O（N²）复杂度（尽管与此处其他答案中的解决方案相比，我还没有测试它的真实性能）；
• 提早退出；
• 检查是否为空；
• 即使涉及重复项也可以使用：如果您有一个数组[1,2,3,3]和另一个数组，则[1,2,2,3]此处大多数解决方案告诉您，不考虑顺序时它们是相同的。该解决方案通过从临时列表中删除相等的元素来避免这种情况。
• 使用语义相等（equals）而不是引用相等（==）；
• 不会对itens进行排序，因此它们不需要可排序（按implement Comparable）即可运行此解决方案。

Answer 10

将列表转换为Guava的Multiset效果很好。比较它们的顺序如何，并考虑重复元素。

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