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. Sobald 70-75% gefüllt ist, baut die Hashtabelle automatisch eine neue Wand mit doppelt so vielen Postfächern und teilt alle Einträge neu auf. 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 alle Schlüssel im selben Postfach landen (schlechte Hash-Funktion) — in der Praxis quasi nie.
Faustregel zum Mitnehmen: Hashtabellen sind die einzige Datenstruktur, die konstante Zeit für Lookup, Insert und Delete schafft. Daher steckt sie in fast jeder Programmiersprache und in jedem zweiten Programm.
So sieht's im Code aus