Kürzlich war ich von der Tatsache überrascht, dass einige Java-Sammlungen keine konstante zeitliche Operation der Methodengröße () haben.

Während ich erfuhr, dass gleichzeitige Implementierungen von Auflistungen einige Kompromisse eingingen, um den Gewinn an Parallelität auszugleichen (Größe O (n) in ConcurrentLinkedQueue, ConcurrentSkipListSet, LinkedTransferQueue usw.), ist die gute Nachricht, dass dies in der API-Dokumentation ordnungsgemäß dokumentiert ist.

Was mich beschäftigte, war die Leistung der Methodengröße bei Ansichten, die von den Methoden einiger Sammlungen zurückgegeben wurden. Zum Beispiel,TreeSet.tailSet Gibt eine Ansicht des Teils des Sicherungssatzes zurück, dessen Elemente größer oder gleich fromElement sind. Was mich sehr überrascht hat, ist, dass der Aufruf von size bei zurückgegebenem SortedSet zeitlich linear ist, also O (n). Zumindest das ist es, was ich aus dem Quellcode von OpenJDK herausgegraben habe: In TreeSet ist als Wrapper über TreeMap implementiert, und in einer TreeMap gibt es eine EntrySetView-Klasse, deren Größenmethode wie folgt lautet:

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

    ....
}

Dies bedeutet, dass die Größe beim ersten Aufruf O (n) ist und dann zwischengespeichert wird, solange die Backing-Map nicht geändert wird. Ich konnte diese Tatsache in der API-Dokumentation nicht finden. Eine effizientere Implementierung wäre O (log n) mit einem Speicher-Kompromiss beim Zwischenspeichern von Teilbaumgrößen. Da solche Kompromisse zur Vermeidung von Code-Duplikationen gemacht werden (TreeSet als Wrapper über TreeMap), sehe ich keinen Grund, warum sie aus Leistungsgründen nicht gemacht werden sollten.

Abgesehen davon, dass ich mit meiner (sehr kurzen) Analyse der OpenJDK-Implementierung von TreeSet Recht oder Unrecht habe, würde ich gerne wissen, ob es eine detaillierte und vollständige Dokumentation zur Leistung vieler solcher Vorgänge gibt, insbesondere solcher Vorgänge, die völlig unerwartet sind.