JDK-Implementierung von AbstractList :: equals() überprüft nicht für Listengröße Gleichheit ersten

Question

Seltsamer den Standard JDK 6 Implementierung von AbstractList::equals()nicht erst zu prüfen scheint, wenn die beiden Listen die gleiche Größe haben:

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

Wenn beide Listen viele Elemente enthalten oder Elemente, die Zeit zum Vergleichen benötigen, werden alle verglichen, bevor erkannt wird, dass eine Liste kürzer ist als die andere. Das scheint mir wirklich ineffizient zu sein, da die Gleichheit ohne einen einzigen Vergleich zustande gekommen wäre.

Insbesondere, dass für viele Situationen Listen Größen würden die meiste Zeit unterscheiden. Darüber hinaus haben die meisten Java List Implementierungen O (1) size() Performance (sogar LinkedList, die ihre Größe im Cache behalten).

Gibt es einen guten Grund für diese Standardimplementierung?

Answer 1

Der Betrieb der Gleichheits Methode wird im Detail angegeben, und es erfordert das O (n) Verhalten. Obwohl dies für Unterklassen, deren Größenmethode O (1) ist, möglicherweise suboptimal ist, kann für einige Unterklassen die Methode der Größe selbst O (n) sein, und das angeforderte Verhalten wäre tatsächlich . In jedem Fall ist die Spezifikation klar und diese Änderung kann nicht vorgenommen werden.

Beachten Sie, dass eine Unterklasse bei Bedarf den Wert "equals" überschreiben kann, indem Sie bei Bedarf einen Vergleich der Größe einfügen.

Reference.