Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the runtime of equals() in java.util.Arrays?

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

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

Thanks.

like image 429
cinnamon toast Avatar asked Dec 27 '12 10:12

cinnamon toast


People also ask

Does equals work on array in Java?

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 null. Arrays class in java provide the method Arrays. equals() to check whether two arrays are equal or not.

What is equal method in Java?

Java String equals() Method The equals() method compares two strings, and returns true if the strings are equal, and false if not. Tip: Use the compareTo() method to compare two strings lexicographically.

What is Java Util arrays?

The Arrays class in java. util package is a part of the Java Collection Framework. This class provides static methods to dynamically create and access Java arrays. It consists of only static methods and the methods of Object class. The methods of this class can be used by the class name itself.

What is arrays stream () in Java?

The stream(T[] array) method of Arrays class in Java, is used to get a Sequential Stream from the array passed as the parameter with its elements. It returns a sequential Stream with the elements of the array, passed as parameter, as its source.


2 Answers

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

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

For example if it's comparing two int[], does it loop through every element in the array, so 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)?

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.

like image 43
Peter Lawrey Avatar answered Nov 04 '22 10:11

Peter Lawrey


Grabbed from the source code (source code is worth 100 words :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;
}
like image 92
Eng.Fouad Avatar answered Nov 04 '22 12:11

Eng.Fouad