On Tue, Dec 8, 2015 at 10:17 PM, Nicholas Cull <run2...@gmail.com> wrote:
> Yes, the time performance of size() appears to be unspecified by the whole > Collections framework: the implementation of equals() in AbstractSet uses > size() as an optimization, though AbstractCollection does not. Naively it > seems > odd that we don't perform this check inside AbstractList. What contract is > AbstractList implying that would be broken by doing so? Using size in AbstracList is not unreasonable. size is rather likely to be O(1) because the List interface is concurrency-hostile. OTOH creating ListIterators and each check of equality for an index is also O(1), so this is a significant optimization only for lists that generally share a common prefix. And sorry, but that's not a good enough reason to change AbstractList. Especially given that the current implementation is specified! It's easier adding optimized equals methods to subclasses. It's more reasonable for AbstractSet to call size() because you cannot have O(1) element by element comparison. You have to call set.contains which is much more likely to be O(N).
