Wie erfolgt die Suche nach einem Element innerhalb einer HashSet-Struktur und wie hoch ist ihre zeitliche Komplexität?

HashSet basiert auf einer Hashtabelle. Bei der Suche nach einem Element wird zunächst sein Hash-Code berechnet, dann wird der Index des Buckets im Array bestimmt. Danach wird das Element innerhalb dieses Buckets gesucht, meist durch Vergleich mit equals. Die durchschnittliche Zeitkomplexität der Suche in HashSet beträgt O(1), also konstante Zeit, vorausgesetzt, die Hashes sind gleichmäßig verteilt und Kollisionen sind gering.