Aus den JavaDocs von HashSet :
Diese Klasse bietet eine konstante Zeitleistung für die Grundoperationen (hinzufügen, entfernen, enthalten und Größe), unter der Annahme, dass die Hash-Funktion zerstreut die Elemente richtig unter den Eimern. Iteriere über diesen Satz benötigt Zeit proportional zur Summe der Größe der HashSet-Instanz (die Anzahl der Elemente) plus die "Kapazität" der Backing HashMap Instanz (die Anzahl der Buckets). Daher ist es sehr wichtig, nicht zu setzen die Anfangskapazität zu hoch (oder der Lastfaktor zu niedrig) wenn Iterationsleistung ist wichtig
Warum benötigt die Iteration Zeit proportional zur Summe (Anzahl der Elemente im Set + Kapazität der Backing Map) und nicht nur zur Anzahl der Elemente im Set selbst?
.
Die Verwendung von LinkedHashSet folgt der "verknüpften" Liste von Einträgen, so dass die Anzahl der Leerzeichen keine Rolle spielt. Normalerweise hätte man kein HashSet, bei dem die Kapazität viel mehr als doppelt so groß ist wie die tatsächliche Größe. Selbst wenn Sie eine Million Einträge scannen, benötigt null nicht viel Zeit (Millisekunden)
Warum dauert die Iteration Zeit proportional zur Summe (Anzahl von Elemente im Set + Kapazität der Backing Map) und nicht nur auf die Nummer von Elementen im Set selbst?
Die Elemente sind innerhalb des zugrunde liegenden HashMap verteilt, das von einem Array unterstützt wird.
So ist nicht bekannt, welche Eimer besetzt sind (aber es ist bekannt, wie viele Elemente vollständig verfügbar sind).
Um also über alle Elemente zu iterieren, müssen alle Buckets aktiviert sein
Tags und Links algorithm java time-complexity hashmap hashtable