Недавно я был удивлен тем фактом, что некоторые коллекции Java не имеют постоянной операции с размером метода ().

Хотя я узнал, что параллельные реализации коллекций сделали некоторые компромиссы в качестве компромисса для увеличения параллелизма (размер равен O (n) в ConcurrentLinkedQueue, ConcurrentSkipListSet, LinkedTransferQueue и т. Д.), Хорошей новостью является то, что это надлежащим образом задокументировано в документации API.

Меня беспокоит производительность размера метода для представлений, возвращаемых методами некоторых коллекций. Например,TreeSet.tailSet возвращает представление части резервного набора, элементы которого больше или равны fromElement. Что меня удивило, так это то, что размер вызова возвращаемого SortedSet является линейным по времени, то есть O (n). По крайней мере, это то, что мне удалось выкопать из исходного кода OpenJDK: в TreeSet реализован в виде оболочки над TreeMap, а внутри TreeMap есть класс EntrySetView, метод размера которого выглядит следующим образом:

abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
    private transient int size = -1, sizeModCount;

    public int size() {
        if (fromStart && toEnd)
            return m.size();
        if (size == -1 || sizeModCount != m.modCount) {
            sizeModCount = m.modCount;
            size = 0;
            Iterator i = iterator();
            while (i.hasNext()) {
                size++;
                i.next();
            }
        }
        return size;
    }

    ....
}

Это означает, что в первый раз вызывается размер O (n), а затем он кешируется, пока резервная карта не изменяется. Я не смог найти этот факт в документации API. Более эффективной реализацией была бы O (log n) с компромиссом памяти при кэшировании размеров поддеревьев. Поскольку такие компромиссы создаются для того, чтобы избежать дублирования кода (TreeSet как обертка над TreeMap), я не вижу причины, по которой они не должны создаваться по соображениям производительности.

Несмотря на то, что я был прав или не прав с моим (очень кратким) анализом реализации TreeJet в OpenJDK, я хотел бы знать, есть ли подробная и полная документация по выполнению многих таких операций, особенно совершенно неожиданных?