Erklär, wie HashMap intern funktioniert, inklusive dem, was passiert, wenn sie voll wird.

Eine HashMap hält ein Array von Buckets. Der Key-Hash wird gespreizt, indem seine höherwertigen Bits eingemischt werden, dann ist der Index dieser Hash maskiert gegen die Tabellenlänge, die immer eine Zweierpotenz ist. Kollisionen bilden eine verkettete Liste im Bucket, und ein Bin mit mindestens acht Einträgen in einer Tabelle mit mindestens vierundsechzig Plätzen wird in einen Rot-Schwarz-Baum umgebaut. Über dem Load Factor von 0,75 verdoppelt sich die Tabelle und die Einträge werden neu gehasht.

Intern ist das ein Array von Bins. Der hashCode des Keys wird gespreizt, indem die höherwertigen Bits per XOR nach unten gemischt werden, und das ist wichtig, weil der Index einfach der Hash maskiert mit Tabellenlänge minus eins ist, ohne dieses Mischen würden also nur die niederwertigen Bits jemals benutzt. Einträge, die kollidieren, hängen sich in diesem Bin aneinander, und seit Java 8 wird ein Bin, der über acht Einträge wächst, bei einer Tabelle mit mindestens vierundsechzig Plätzen zu einem Rot-Schwarz-Baum, damit das Lookup im schlimmsten Fall logarithmisch statt linear ist. Das war die Antwort auf Denial-of-Service-Angriffe über Hash-Kollisionen. Das Wachstum steuert der Load Factor, bei 0,75 Belegung verdoppelt sich die Tabelle also und alles wird umverteilt, weshalb es sich lohnt, die Map vorab zu dimensionieren, wenn ich weiß, dass eine Million Einträge reinkommen. Die praktischen Konsequenzen, die mich interessieren: Keys sollten immutable sein, ein schlechter hashCode lässt alles in einem einzigen Bin landen, und nebenläufige Schreibzugriffe können die Tabelle zerlegen, geteilte Maps bekommen also eine ConcurrentHashMap statt externem Locking.