Why does not ArrayList override equals() for better performance?

Question

ArrayList inherits equals implementation from its parent class AbstractList which is not very effective.

It could first check the size of the two ArrayLists and then return false immediately if these sizes are different. Why does not ArrayList do that?

Answer 1

As noted in this answer, this is not done because some implementations has O(n) complexity of their size method, so this can be indeed a degradation.

I agree that making equals consistent in all lists implementations can affect collections that has O(1) size complexity, but maybe Java developers thought that it's much easier to insert it when you need than removing it when you don't (you'll have to re-implement the whole method!). For example, you can easily add this optimization with something like:

public boolean equals(Object o) {
    // here it is
    if (o instanceof List && this.size() != ((List)o).size())
        return false;

    // call the parent equals
    return super.equals(o);

But if it was originally implemented with the size check (in the abstract class), you had to re-implement the whole method and remove the size check:

public boolean equals(Object o) {
    if (o == this)
        return true;
    if (!(o instanceof List))
        return false;

    ListIterator<E> e1 = listIterator();
    ListIterator<?> e2 = ((List<?>) o).listIterator();
    while (e1.hasNext() && e2.hasNext()) {
        E o1 = e1.next();
        Object o2 = e2.next();
        if (!(o1==null ? o2==null : o1.equals(o2)))
            return false;
    }
    return !(e1.hasNext() || e2.hasNext());
}

Answer 2

Finally, a decision to override ArrayList.equals() and ArrayList.indexOf() was made: https://bugs.openjdk.java.net/browse/JDK-8196340. Benchmarks show a tangible performance gain.