Erklären Sie, was eine Kollision von Schlüsseln in der Datenstruktur HashMap bedeutet und wie sie damit umgeht.

Kollisionen von Schlüsseln (Hash-Kollision) in HashMap treten auf, wenn zwei verschiedene Schlüssel beim Berechnen der Hash-Funktion denselben Indexwert für die Speicherung im Array ergeben.

So geht HashMap damit um:

• In Java verwendet HashMap Verkettungen (verkettete Listen oder balancierte Bäume), um mehrere Elemente zu speichern, die in denselben Bucket fallen.
• Beim Hinzufügen eines neuen Elements mit einem Schlüssel, dessen Hash mit einem bestehenden übereinstimmt, wird das neue Element in die Verkettung dieses Buckets eingefügt.
• Bei der Suche nach einem Schlüssel durchläuft HashMap die Elemente in der Verkettung und vergleicht die Schlüssel mit equals(), um das richtige zu finden.

Seit Java 8 wird, wenn die Verkettung zu lang wird, diese in einen balancierten Baum (TreeNode) umgewandelt, was die Suchleistung von O(n) auf O(log n) verbessert.