如何使用现代Java比较数组列表的相等性？

Question

我有两个数组列表。

如何使用Java 8及其特性轻松比较它们的相等性，而不使用外部库？ 我正在寻找比类似于以下代码（未经测试的代码，可能包含拼写错误等问题，但不是问题的重点）更好的解决方案（更高级别，更短，更有效）：

boolean compare(List<String[]> list1, List<String[]> list2) 
{
    // tests for nulls etc omitted
    if(list1.size() != list2.size()) {
       return false;
    }
    for(i=0; i<list1.size(); ++i) {
        if(!Arrays.equals(list1.get(i), list2.get(i))) {
            return false;
        }
    }
    return true;
}

或者，如果没有更好的方法，那也是一个有效的答案。

奖励：如果Java 9提供了比Java 8更好的方法，请随意提及。

编辑：在查看评论并看到这个问题已经变得相当热门后，我认为"更好的方法"应该包括首先检查所有数组的长度，然后再检查数组内容，因为如果内部数组很长，这有可能更快地发现不等式。

- hyde

---

如果你只是使用List<List<String>>而不是List<String[]>，那么你就可以做到list1.equals(list2)。实际的比较（在底层）仍然是暴力的。 - marthursson

代码运行良好，速度快，易于阅读/理解和维护...为什么要修改它呢？为什么更短更好？ - Falco

请记住，较短的解决方案可能也会更慢。 - Pharap

什么是“更好”？速度更快？更易于维护？使用的内存更少？ - Martin Schröder

@MartinSchröder 我稍微澄清了一下问题。 - hyde

Answer 1

for循环至少可以转换为流的形式，从而导致：

return (list1.size()==list2.size() &&
        IntStream.range(0, list1.size())
                 .allMatch(i -> Arrays.equals(list1.get(i), list2.get(i)));

- khelwood

---

不错的解决方案。值得注意的是，对于非“RandomAccess”列表来说，效率较低。 - Jaroslaw Pawlak

一般情况下，无法比O(n)更快地比较两个包含n个元素的集合。 - ymbirtt

@ymbirtt：实际上，有一种方法，但需要您编写自己的集合或扩展现有的集合并进行修改。只需在集合上保留一个哈希码。每次添加一个项时，相应地调整哈希（例如，乘以一个质数并添加该项的哈希码）。然后，您只需要比较两个集合的哈希值，这是O(1)的。由于可能会发生冲突，当哈希匹配时可以选择仅进行完全比较，那么它就是O(n)，但其余时间更快。此外，删除或编辑集合中的项可能会很复杂。 - Darrel Hoffman

为了准确比较，如果哈希值匹配，你必须比较每个元素。 - user253751

@immibis：我想总的分摊性能取决于您有多频繁地比较匹配和不匹配的集合。但是，使用良好的哈希函数，两个不匹配的集合具有匹配的哈希的概率非常小，因此绝大多数的不匹配可以很快地确定。如果您经常期望获得匹配项（或者您打算定期更改/删除项目，这可能需要O（n）重新哈希），那么这种方法可能效果不佳。 - Darrel Hoffman

Answer 2

使用来自 https://dev59.com/VGMm5IYBdhLWcg3wZ-XQ#23529010 的 zip 函数（源自 lambda b93），代码可能如下所示：

boolean match = a.size() == b.size() && 
                zip(a.stream(), b.stream(), Arrays::deepEquals).
                allMatch(equal -> equal)

更新

为了先检查数组的大小，然后再检查内容，可以考虑以下解决方案。

final boolean match = a.size() == b.size() 
                   && zip(a.stream(), b.stream(), (as, bs) -> as.length == bs.length).
                      allMatch(equal -> equal)
                   && zip(a.stream(), b.stream(), Arrays::deepEquals).
                      allMatch(equal -> equal);

- hahn

Answer 3

1) 基于Java 8流的解决方案：

List<List<String>> first = list1.stream().map(Arrays::asList).collect(toList());
List<List<String>> second = list2.stream().map(Arrays::asList).collect(toList());
return first.equals(second);

2) 更简单的解决方案（适用于Java 5+）：

return Arrays.deepEquals(list1.toArray(), list2.toArray());

3) 关于您的新需求（首先检查包含的字符串数组长度），您可以编写一个通用的帮助方法，对转换后的列表进行等式检查：

<T, U> boolean equal(List<T> list1, List<T> list2, Function<T, U> mapper) {
    List<U> first = list1.stream().map(mapper).collect(toList());
    List<U> second = list2.stream().map(mapper).collect(toList());
    return first.equals(second);
}

那么解决方案可能是：

return equal(list1, list2, s -> s.length)
    && equal(list1, list2, Arrays::asList);

- Dragan Bozanovic

---

#2更简单，但也会创建每个列表的副本... - Holger

@Holger 确实，第一个解决方案也涉及到复制列表。但是在这两个解决方案中，包含的字符串数组并没有被复制，只有对它们的引用被复制了。 - Dragan Bozanovic

我稍微编辑了一下这个问题，如果你想要检查一下的话... 我觉得 deepEquals 不会做到这个，对吗？ - hyde

@hyde deepEquals 确实会检查长度。从 javadoc 中可以看到：如果两个数组引用都为 null，或者它们引用的数组包含相同数量的元素，并且这两个数组中所有对应的元素对都是深度相等的，则认为它们是深度相等的。 - SpaceTrucker

@SpaceTrucker 是的，但我的意思是，它可能不会首先检查所有数组的长度等，只有在这之后才开始检查它们的内容。它会假设在检查第一个遇到的数组的内容之前，会先检查第二个数组的长度。 - hyde

@hyde，源代码是可访问的，为什么不自己检查一下呢？这是一些旧的open-jdk版本。在我看来，由于第二点，这应该是被接受的答案。 - zloster

Answer 4

如果列表是随机访问列表（这样调用get的速度很快——通常是常数时间），则可以使用流进行操作：

//checks for null and size before
boolean same = IntStream.range(0, list1.size()).allMatch(i -> Arrays.equals(list1.get(i), list2.get(i)));

然而，您可能会将一些未实现迭代器的实现作为参数传递（例如LinkedLists）。在这种情况下，最好的方法是明确使用迭代器。像这样：

boolean compare(List<String[]> list1, List<String[]> list2) {

    //checks for null and size

    Iterator<String[]> iteList1 = list1.iterator();
    Iterator<String[]> iteList2 = list2.iterator();

    while(iteList1.hasNext()) {
        if(!Arrays.equals(iteList1.next(), iteList2.next())) {
            return false;
        }
    }
    return true;
}

- Alexis C.

---

第一个解决方案将在第二个列表具有更多元素时返回true。第二个解决方案对于不同大小的大型列表效率低下，因为它只会在迭代完它们后才返回false。 - Jaroslaw Pawlak

@JaroslawPawlak 第一种解决方案假设已经进行了空引用和大小检查（只需替换for循环）。我为第二种解决方案进行了编辑。 - Alexis C.

好的。在这种情况下，我们可以将第二个解决方案中的最终返回语句简化为 return true; :) - Jaroslaw Pawlak

@JaroslawPawlak 是的，我们甚至可以在条件中省略 && iteList2.hasNext() - Alexis C.

Answer 5

您可以使用迭代器遍历其中一个列表，然后与另一个列表的每个元素进行比较：

Iterator<String[]> it = list1.iterator();
boolean match = list1.size() == list2.size() &&
                list2.stream().allMatch(a -> Arrays.equals(a, it.next()));

使用迭代器而不是第一个列表上的get(index)方法更好，因为它不会影响列表是否为RandomAccess。

注意：这仅适用于sequential流。使用并行流将导致错误的结果。

---

编辑：根据最后一次编辑的问题，表明提前检查每对数组的长度会更好，我认为可以对我的先前代码进行轻微修改来实现这一点。

Iterator<String[]> itLength = list1.iterator();
Iterator<String[]> itContents = list1.iterator();

boolean match = 
        list1.size() == list2.size()
    && 
        list2.stream()
            .allMatch(a -> {
                String[] s = itLength.next();
                return s == null ? a == null :
                       a == null ? s == null :
                       a.length == s.length;
            })
    && 
        list2.stream()
            .allMatch(a -> Arrays.equals(a, itContents.next()));

在这里，我使用两个迭代器，并且对list2进行了两次流处理，但我没有找到其他检查所有长度以在检查第一对数组内容之前的方法。长度检查是空安全的，而内容检查则委托给Arrays.equals(array1, array2)方法。

- fps

---

我要警告说，如果有人调用.parallelStream()，这将会产生意想不到的结果。 - Alexis C.

是的，我知道。但我已经想象过有人会复制粘贴这段代码并说：“嘿，我试着使用并行流来加速它。” - Alexis C.

你可以进一步简化它为：list2.stream() .allMatch(a -> Arrays.equals(a, it.next()))。 - Dragan Bozanovic