抽象列表的 JDK 实现::equals() 不首先检查列表大小相等性

2022-09-03 07:30:27

奇怪的是,默认的 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实现都具有O(1)性能(甚至是LinkedList,它将其大小保持在缓存中)。Listsize()

此默认实现是否有充分的理由?


答案 1

equals 方法的操作已详细指定,并且需要 O(n) 行为。虽然对于大小方法为 O(1) 的子类来说,这可能是次优的,但对于某些子类,大小方法本身可能是 O(n),请求的行为实际上是一种降级。在任何情况下,规范都是明确的,无法进行此更改。

请注意,如果需要,子类可以覆盖 equals,并在适当的时候插入大小比较。

参考。


答案 2