Habe aufgeschrieben: HashSets verwenden Hashtabelle (also ne HashMap), um Hashwerte und Elemente OHNE Duplikate zu speichern.
HashMaps enthalten Hashwerte der Schlüssel, um Elemente zu finden
Aber wie kommt man nun bei der contains()-Methode des HashSets auf O(1)?
Ich würde mir nämlich vorstellen, dass das folgende passiert:
Man übergibt als Parameter das Element, das überprüft werden soll, ob es sich im Set befindet. Dieses Element steht in einer Hashtabelle mit Hashwerten drin. Also wird nun die Hashtabelle durchsucht, ob das Element darin ist. Aber müsste dazu nicht die ganze Tabelle durchgegangen werden, Element für Element, bis das jeweilige Element gefunden wurde?
Wie kommt man dann zu O(1), also dass das Element quasi auf Anhieb angesteuert werden kann, falls es sich im Set befindet? Wie muss ich mir das vorstellen?
lg Kath