JDK对AbstractList::equals()方法的实现没有首先检查列表大小是否相等

Question

奇怪的是，JDK 6 默认实现的 AbstractList::equals() 方法似乎没有首先检查两个列表是否具有相同大小：

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

如果两个列表包含大量的项目，或者需要花费时间进行比较，它将在比较所有项目后才意识到其中一个列表比另一个短; 这似乎对我来说非常低效，因为相等性甚至可以在不调用一次比较的情况下就可以判断出来。

特别是对于很多情况，列表大小大多数时候可能会不同。此外，大多数Java List实现都具有O(1) size()性能（即使LinkedList也是如此，它将其大小保留在缓存中）。

这种默认实现是否有充分的理由？

- Laurent Grégoire

Answer 1

equals方法的操作在某些细节上有详细说明，并且需要O(n)的行为。虽然对于size方法为O(1)的子类来说，这可能不是最优的选择，但对于某些子类来说，size方法本身可能是O(n)，而请求的行为实际上是一种退化。无论如何，规范是清楚的，这个改变是不能被接受的。

请注意，如果需要，子类可以覆盖equals方法，并插入适当的大小比较。

参考链接：Reference.

- Sajal Dutta

---

所以，如果我理解得正确，这是因为它已被记录为低效的，对吗？ :) - Laurent Grégoire

不是因为“它已被记录为这样”，而是由于设计决策，原因是“对于某些子类，size方法本身可能是O（n），请求的行为实际上将是退化”。@Laurent - Sajal Dutta

我明白，但是因为“其中一些”可能更慢而在所有实现中首先降低性能，这对我来说似乎不是一个好决定。我会为大小为O(1)的列表制作一个优化的equals方法，并且对其他列表进行未优化的处理。特别是对于Java中的工作马ArrayList…… - Laurent Grégoire

@Laurent 你总是可以覆盖重写，保持一致性实际上对长远来说是有好处的。 :) - Sajal Dutta

List::size() 的性能在第一位目前 不 一致：O(n) 或 O(1)，因此我真的看不出尝试使不同 List 实现之间的 equals() 一致的意义所在... 另一个选择是假设甚至要求 size() 具有 O(1) 的性能（这是所有主要默认实现的情况），并始终优化 equals()。 - Laurent Grégoire