FULL PRODUCT VERSION :
java version "1.5.0"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0-b64)
Java HotSpot(TM) Client VM (build 1.5.0-b64, mixed mode)


A DESCRIPTION OF THE PROBLEM :
In AbstractList v1.46 (which comes with J2SE 1.5.0), the equals() method doesn't bother checking if the two Lists are different sizes. This makes equals() massively inefficient for two Lists which are equal at the start (i.e. in the earlier elements).

For instance, if two Lists are identical except one has an extra element at the end, both Lists will be iterated right through.


STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
The following code creates 2 very similar lists of different lengths. The equals() call takes 120 microseconds on my 1.7Ghz Pentium 6. That's 200,000 cycles!!

ArrayList a = new ArrayList(Collections.nCopies(1000, "Same"));
ArrayList b = (ArrayList)a.clone();
b.add("Different");
boolean equal = a.equals(b);



REPRODUCIBILITY :
This bug can be reproduced always.

CUSTOMER SUBMITTED WORKAROUND :
Subclass ArrayList/LinkedList and write your own equals() method.

A proper fix would be just a couple of extra lines inserted in AbstractList.equals(), as shown below:

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

// Insert these lines:
// if (this.size() != ((List)o).size())
//	    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());
    }
###@###.### 2004-11-18 21:34:12 GMT