Ich habe die Javadocs auf HashSet gelesen, als ich auf die interessante Aussage stieß:

Diese Klasse bietet eine konstante Zeitleistung für die Grundoperationen (Hinzufügen, Entfernen, Enthalten und Größe)

Das verwirrt mich sehr, da ich nicht verstehe, wie man eine konstante Zeit, O (1), Leistung für eine Vergleichsoperation erhalten könnte. Hier sind meine Gedanken:

Wenn dies zutrifft, kann ich unabhängig davon, wie viele Daten ich in mein HashSet kopiere, in konstanter Zeit auf jedes Element zugreifen. Das heißt, wenn ich 1 Element in mein HashSet lege, dauert es genauso lange, bis ich es gefunden habe, als hätte ich einen Googolplex von Elementen.

Dies wäre jedoch nicht möglich, wenn ich eine konstante Anzahl von Buckets oder eine konsistente Hash-Funktion hätte, da für jede feste Anzahl von Buckets die Anzahl der Elemente in diesem Bucket linear wächst (wenn auch langsam, wenn die Anzahl gleich ist groß genug) mit der Anzahl der Elemente in der Menge.

Dann funktioniert dies nur, wenn Sie bei jedem Einfügen eines Elements (oder alle paar Male) eine sich ändernde Hash-Funktion verwenden. Eine einfache Hash-Funktion, die niemals irgendwelche Kollisionen befriedigen würde. Ein Spielzeugbeispiel für Zeichenfolgen könnte sein: Nehmen Sie den ASCII-Wert der Zeichenfolgen und verknüpfen Sie sie miteinander (da das Hinzufügen zu einem Konflikt führen kann).

Diese Hash-Funktion und jede andere Hash-Funktion dieser Art schlägt jedoch wahrscheinlich fehl, wenn die Zeichenfolgen oder Zahlen groß genug sind usw. Die Anzahl der Eimer, die Sie bilden können, wird sofort durch die Größe des Stapel- / Heap-Speicherplatzes usw. begrenzt. Das Überspringen von Speicherorten im Speicher kann daher nicht auf unbestimmte Zeit zugelassen werden, sodass Sie die Lücken eventuell ausfüllen müssen.

Aber wenn es irgendwann eine Neuberechnung der Hash-Funktion gibt, kann dies nur so schnell sein, wie ein Polynom zu finden, das durch N Punkte geht, oder O (nlogn).

So kommt meine Verwirrung. Ich glaube zwar, dass das HashSet in O (n / B) auf Elemente zugreifen kann, wobei B die Anzahl der von ihm ausgewählten Buckets ist, aber ich sehe nicht, wie ein HashSet möglicherweise Add- oder Get-Funktionen in O ausführen kann ( 1) Zeit.

Hinweis:Dieser Beitra unddieser Beitra Beide gehen nicht auf die aufgeführten Probleme ein.