Wie ist die Größenoperation einer HashSet-Konstantenzeitoperation?
Ich habe gelesen, dass die enthält und Größe Operation ist konstante Zeit.
Obwohl ich verstehe, dass contains eine Operation mit konstanter Zeit ist, wäre die Operation nicht proportional zur Anzahl der Elemente (nicht linear)?Hashset-Größenoperation
Die kurze Antwort - es ist im Cache gespeichert.
Die längere Antwort: HashSet ist eine Set Implementierung, die eine HashMap hält, in dem alle Werte gleich „Blindwert“ sind. Es ist size() Methode gibt einfach die Karte size() zurück. Wenn Sie in die Implementierung von HashMap schauen, sehen Sie, dass es ein size Mitglied hat. Das Hinzufügen von Elementen zu der Karte (z. B. unter Verwendung von put oder putAll) erhöht die size und das Entfernen von Elementen daraus verringert die size. Auf diese Weise wird size immer auf dem neuesten Stand gehalten und kann einfach zurückgegeben werden, wenn size() aufgerufen wird, was eine konstante Zeitausführung garantiert.
HashSet intern speichert, wie viele Elemente es hat.
sollte Größe Betrieb nicht proportional sein (nicht linear) mit der Anzahl der Elemente?
Wenn dies nicht für die Aufzeichnung in einem Feld gespeichert wurde, Größe() würde auf die Größe der Träger Hash-Tabelle, nicht die Anzahl der Elemente verhältnismäßig sein, da man über scannen müss Alle Einträge, um zu sehen, ob etwas da ist. Diese sind in der Regel die gleichen (innerhalb von 2x), außer wenn die Hash-Tabelle entweder eindeutig zu groß oder viele Elemente gelöscht wurden.