在java.util. array中的equals()运行时是什么?

As title stated, what's the runtime of equals() in java.util.Arrays ?

如标题所述，在java.util中equals()的运行时是什么。数组?

For example if it's comparing two int[] , does it loop through every element in the array, so O(n)? And for all equals() in individual classes' equals() in java, can we assume that the runtime is always O(n) ?

例如，如果它在比较两个int[]，它是否循环遍历数组中的每个元素，所以O(n)?在java中，对于单个类的equals()中的all equals()，我们能假设运行时总是O(n)吗?

Thanks.

谢谢。

4 个解决方案

#1

As title stated, what's the runtime of default equals() in java.util.Arrays?

如标题所述，在java.util. array中默认=()的运行时是什么?

The default equals could mean Object.equals. The Arrays.equals() is usually what you really want.

默认的等号可以表示Object.equals。等号通常是你真正想要的。

For example if it's comparing two int[], does it loop through every element in the array, so O(n)?

例如，如果它比较两个int[]，它是否会遍历数组中的每个元素，所以O(n)?

yes, thats what the source suggests.

是的，消息来源是这么说的。

And for all default equals() in java, can we assume that the runtime is always O(n)?

对于java中的所有默认值=()，我们是否可以假设运行时总是O(n)?

For some collections this is true, but for Tree collections it can be O(n log n). The worst case for HashMap is O(N^2) For non-collections n has no meaning.

对于一些收藏这是真的,但对于树集合可以是O(n log n)。HashMap的最坏情况是O(n ^ 2)non-collections n没有意义。

#2

Grabbed from the source code (source code is worth 100 words :P):

从源代码(源代码值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;
}

#3

It first checks the length, and if equal, loops over all elements and calls equals on them.

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

So, if you want to ignore the cost of the individual equals, yes, that would be O(n). But if the entries are Strings, for example, it will also get longer as the Strings get longer, not just as they get more (because the comparisons themselves are O(m) as well).

所以，如果你想忽略个体的成本等于，是的，那就是O(n)但是，如果条目是字符串，那么它也会随着字符串的变长而变长，而不是因为它们得到的更多(因为比较本身也是O(m))。

#4

The javadoc states: two arrays are equal if they contain the same elements in the same order. So it is clear that this is going to be an O(n) operation as it will need to loop over all the items (at least if they are all equal).

javadoc声明:如果两个数组以相同的顺序包含相同的元素，那么它们是相等的。所以很明显，这将是一个O(n)操作，因为它需要对所有的项进行循环(至少如果它们都是相等的)。

The default equals (i.e. Object#equals) is an O(1) operation, it is a simple reference comparison:

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

for any non-null reference values x and y, this method returns true if and only if x and y refer to the same object (x == y has the value true)

对于任何非空引用值x和y，该方法返回true，当且仅当x和y引用相同的对象时(x = y值为true)

#1