Die Fachbegriffe
Jetzt die offiziellen Wörter:
| Im Bild | Im Code | Bedeutung |
|---|
| Postfächer | Buckets | das Array das die Einträge speichert |
| Buchstaben-Zahl | Hash | die Zahl die aus dem Schlüssel berechnet wird |
| Regel | Hash-Funktion | das was Schlüssel zu Hash macht |
| Schüler-Name | Key | womit du suchst |
| Schüler-Note | Value | was du speicherst und zurückbekommst |
| Postfach-Nummer | Bucket-Index | Hash modulo Bucket-Anzahl |
Was wenn zwei Schüler dasselbe Postfach kriegen?
Beispiel: Anna und Eva haben beide eine Buchstaben-Zahl, die durch 10 geteilt Rest 4 ergibt. Beide wollen Postfach 4. Was tun?
→ Kollision.
Lösung: Im Postfach steht nicht ein einziger Eintrag, sondern eine kleine Liste. Anna kommt rein, Eva kommt dazu. Wenn du nach "Eva" suchst:
- Postfach 4 öffnen
- In der Liste nach "Eva" suchen (1-2 Vergleiche)
- Note gefunden
Solange wenige Schüler dasselbe Postfach kriegen, geht's immer noch fast genauso schnell wie ohne Kollision. Genau deshalb sind Hashtabellen praktisch immer O(1): weil gute Hash-Funktionen die Schüler gleichmäßig auf alle Postfächer verteilen.
Was wenn die Postfächer voll werden?
Wenn ich 100 Schüler in 10 Postfächern habe, sind im Schnitt 10 Schüler pro Postfach, und Suchen wird wieder linear (O(n)).
Lösung: Größere Wand bauen. Java HashMap resized automatisch, sobald die Anzahl der Einträge den Schwellwert capacity · loadFactor überschreitet (standardmäßig capacity · 0,75). Es geht also um die Anzahl Einträge im Verhältnis zur Kapazität, nicht um den Anteil belegter Buckets, durch Kollisionen kann die Zahl belegter Buckets deutlich anders sein. Beispiel: 15 Einträge in 20 Buckets → Load Factor α = 15/20 = 0,75, auch wenn z. B. nur 12 Buckets tatsächlich belegt sind (3 davon haben je 2 Einträge durch Kollisionen). Konkrete Rechnung: capacity=16, entries=12 → Load Factor 12/16 = 0,75 → bei nächstem put wird auf 32 Buckets resized und alle 12+1 Einträge re-hashed. Beim Resize verdoppelt sich die Bucket-Anzahl, alle Einträge werden neu verteilt. Das passiert intern, du merkst nichts davon.
Komplexität (das, was in der Klausur drankommt)
| Operation | Normal | Worst Case |
|---|
| put (Eintrag speichern) | O(1) | O(n) |
| get (Eintrag holen) | O(1) | O(n) |
| remove (Eintrag löschen) | O(1) | O(n) |
Worst Case tritt auf wenn viele Schlüssel im selben Postfach landen (schlechte Hash-Funktion oder bewusst schlecht gewählte Keys). Bei guter Hash-Funktion und kontrolliertem Load Factor sind put/get/remove durchschnittlich/amortisiert O(1).
Faustregel zum Mitnehmen: Hashtabellen sind die wichtigste allgemeine Datenstruktur für durchschnittlich konstante Key-Lookups, Inserts und Deletes. Direkte Adressierung (Arrays mit Integer-Index) liefert auch O(1), perfektes Hashing kann sogar Worst-Case-Konstantzeit garantieren, Hashtabellen sind die universelle Lösung für allgemeine Keys.
So sieht's im Code aus
