java.util.Arrays中equals()的运行时是什么？

Question

正如标题所说,什么的运行equals()中java.util.Arrays？

例如,如果它比较两个int[],它是否循环遍历数组中的每个元素,那么O(n)？对于Java equals()中各个类的所有类equals(),我们可以假设运行时总是O(n)吗？

谢谢.

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

Answer 2

正如标题所述,java.util.Arrays中默认的运行时是什么等于()？

默认等于可能意味着Object.equals.Arrays.equals()通常是你真正想要的.

例如,如果它比较两个int [],它是否循环遍历数组中的每个元素,那么O(n)？

是的,这就是消息来源所暗示的.

对于java中的所有默认equals(),我们可以假设运行时总是O(n)吗？

对于某些集合,这是正确的,但对于Tree集合,它可以是O(n log n).HashMap的最坏情况是O(N ^ 2)对于非集合n没有任何意义.

Answer 3

它首先检查长度,如果相等,则遍历所有元素并且调用等于它们.

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