java.util.Arrays中equals()方法的运行时间是多少？

Question

正如标题所述，在java.util.Arrays中，equals()的运行时间是多少？例如，如果比较两个int[]，它是否循环遍历数组中的每个元素，因此为O(n)？对于所有Java中各个类中的equals()，我们可以假定运行时间始终为O(n)吗？谢谢。

- cinnamon toast

---

为什么不查看来源？ - PermGenError

通常情况下，这是未指定的（因为一个类可能有自己的“equals”方法）。但是，这是一种深度比较，因此比较两个int[]数组可能是O(n)的。 - Basile Starynkevitch

默认等于是什么意思？ - vishal_aim

@vishal_aim 默认Equals方法的定义是“如果两个数组包含相同数量的元素，并且两个数组中相应位置上的元素都相等，则这两个数组被认为是相等的。换句话说，如果两个数组以相同顺序包含相同的元素，则它们是相等的。同时，如果两个数组引用都为null，则它们被认为是相等的。” - cinnamon toast

Answer 1

从源代码中获取（源代码价值100字:P）：

/**
 * Returns <tt>true</tt> if the two specified arrays of ints are
 * <i>equal</i> to one another.  Two arrays are considered equal if both
 * arrays contain the same number of elements, and all corresponding pairs
 * of elements in the two arrays are equal.  In other words, two arrays
 * are equal if they contain the same elements in the same order.  Also,
 * two array references are considered equal if both are <tt>null</tt>.<p>
 *
 * @param a one array to be tested for equality
 * @param a2 the other array to be tested for equality
 * @return <tt>true</tt> if the two arrays are equal
 */
public static boolean equals(int[] a, int[] a2) {
    if (a==a2)
        return true;
    if (a==null || a2==null)
        return false;

    int length = a.length;
    if (a2.length != length)
        return false;

    for (int i=0; i<length; i++)
        if (a[i] != a2[i])
            return false;

    return true;
}

- Eng.Fouad

---

这不是默认的等于。 - Henry

抱歉，我指的是java.util.Array中的equals方法，而不是Object类中的默认equals方法。 - cinnamon toast

Answer 2

正如标题所述，java.util.Arrays中默认equals()的运行时间是多少？默认的equals可能意味着Object.equals。通常你真正想要的是Arrays.equals()。

例如，如果它正在比较两个int[]，它是否循环遍历数组中的每个元素，因此是O(n)的？

是的，这就是源代码所示的。

对于所有java中的默认equals()，我们可以假设运行时间始终为O(n)吗？

对于一些集合，这是正确的，但对于树集合，它可能是O(n log n)。HashMap的最坏情况是O(N^2)。对于非集合，n没有意义。

- Peter Lawrey

---

这是否在JVM规范中定义为如何实现Array.equals()，还是实现留给特定的JVM编写者。即，这对于IBM的JVM和Dalvik VM也是正确的吗？或者在未来的Oracle JVM中可能会发生变化？ - Megan Walker

@SamuelWalker 虽然我怀疑这不是规范的一部分，但长期存在的方法的行为基本上不会改变，因为你永远不知道它可能会破坏什么。在这种情况下，很难想象为什么你会以另一种方式实现它，特别是考虑到你已经有了一个参考实现。 - Peter Lawrey

一棵树怎么可能是O(n log n)呢？不应该是O(n*n log n)吗？ - soandos

@soandos 一棵树需要进行N个查找，每个查找的时间复杂度为O(log N)，因此总时间复杂度为O(N log N)。 - Peter Lawrey

对于哈希映射，如果你非常不幸（或者有一个恶意用户），并且你所有对象的哈希值都相同，那么你将得到最坏情况下的O(n^2)行为。在这种情况下，你最终没有其他选择，只能进行n x n比较。哈希映射相等通常具有O(n)的平均运行时间，但是明显的相等检查实现的最坏情况是O(n^2)。 - Edward Loper

Answer 3

首先检查长度，如果相等，则循环遍历所有元素并调用 equals。

因此，如果要忽略单个 equals 的成本，那么它将是 O(n)。但是，如果条目是字符串，例如，随着字符串变长，它的长度也会变长，不仅仅是随着元素数量增加（因为比较本身也是 O(m)）。

- Thilo

Answer 4

javadoc指出：如果两个数组包含相同的元素并且顺序相同，则它们相等。因此，很明显这将是一个O(n)操作，因为它需要遍历所有项（至少如果它们都相等）。

默认的equals（即Object#equals）是一个O(1)操作，它是一个简单的引用比较：

对于任何非空引用值x和y，当且仅当x和y引用同一个对象（x == y的值为true）时，此方法返回true

- assylias