Hash-Tabelle-Visualizer

Gib Schlüssel ein und beobachte, wie sie auf Slots abgebildet werden. Sieh, was bei Kollisionen passiert.

Rechenbeispiel — Hash-Tabelle-Visualizer

Lastfaktor alpha	0.75
Aktuelles Verhalten	5 Kollision(en)
Zusätzliche Sondierungen	15
Durchschnittliche Sondierungen	3.5
Kollisionswahrscheinlichkeit	85%

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Die Voreinstellung „alle kollidieren“ hat keine kaputte Hash-Funktion — sie hat die falsche Tabellengröße 🖖

Deine Schlüssel sind 0, 8, 16, 24, 32 und 40, und die Tabelle hat 8 Plätze. Jeder dieser Schlüssel ist ein Vielfaches von 8, also schickt key mod 8 alle sechs auf Platz 0 und die Tabelle entartet zu einer einzigen Liste. An der Hash-Funktion ist nichts falsch: sie tut genau das, was sie verspricht. Der Fehler ist, dass die Tabellengröße einen Faktor mit dem Muster der Schlüssel teilt. Genau das ist das ganze Argument für Primzahl-Tabellengrößen — eine Größe von 8 ist wehrlos gegen Schlüssel, die in Achterschritten laufen, während eine Primzahl keinen Faktor bietet, auf dem sie landen könnten. Wechsle zu den Sondierungs-Voreinstellungen und sieh dieselbe Kollision auf zwei Wegen behandelt.

Direkt zum richtigen Platz springen 🖖

Eine Hashtabelle besteht aus einem Array und einer Regel: Die Hashfunktion ordnet jedem Schlüssel einen Platz zu. Statt alle Einträge nacheinander zu durchsuchen, berechnest du direkt, wohin ein Element gehört. Deshalb bleiben Suchvorgänge selbst bei Millionen von Schlüsseln schnell. Entscheidend ist, dass sich die Schlüssel gleichmäßig verteilen. Füge einige ein und beobachte, wie schnell zwei Schlüssel denselben Platz beanspruchen.

Wenn Kollisionen zur Waffe werden 🖖

Weil eine Hashtabelle zu einer langsamen linearen Suche verkommt, sobald zu viele Schlüssel in einem Slot landen — genau der Worst Case, den du oben auslösen kannst —, kann ein Angreifer, der deine Hashfunktion kennt, Tausende von Schlüsseln erzeugen, die absichtlich kollidieren. 2011 legte dieser 'Hash-Flooding'-Trick Webserver in PHP, Java, Python und Ruby mit einer einzigen präparierten Anfrage lahm. Die Lösung waren zufällig initialisierte Hashfunktionen wie SipHash, heute in vielen Sprachen Standard.

HASHTABELLEN — WO EIN SCHLÜSSEL LANDET UND WAS BEI EINER KOLLISION PASSIERT

Welchen Kollisionsfall behandelst du?

Eine Hashtabelle ist nur so lange O(1), wie sich die Schlüssel verteilen. Zwei Fragen entscheiden alles: Streut die Hashfunktion deine Schlüssel, und wenn zwei doch kollidieren — hängst du den zweiten an den Platz an oder suchst du einen anderen Platz? Der Füllgrad α = n/m bestimmt, wie oft Kollisionen auftreten; die Strategie bestimmt, was jede einzelne kostet.

Keine Kollisionen — der Fall, den das O(1)-Versprechen voraussetzt h(k) = k mod m, α = n/m

Alle Schlüssel in einem Platz — Verkettung wird zur Liste O(n)

Lineares Sondieren — offene Adressierung mit primärer Clusterbildung (h + i) mod m

Quadratisches Sondieren — keine Cluster, dafür Einfügefehler (h + i²) mod m

Keine Kollisionen — der Fall, den das O(1)-Versprechen voraussetzt

Was du weißt: Jeder Schlüssel landet in einem eigenen Platz. Der Füllgrad α = n/m liegt unter 1, und der Hash verteilt die Schlüssel gleichmäßig über die Tabelle.

Sondierregel: h(k) = k mod m, α = n/m

Rechenbeispiel: Schlüssel 0–5 in m = 8 mit h(k) = k mod 8 → Plätze 0–5, je eine Sondierung: α = 0,75 und im Mittel exakt 1,00 Sondierungen

Diesen Fall öffnen: Keine Kollision

Keine Kollisionen — der Fall, den das O(1)-Versprechen voraussetzt. Sechs Schlüssel, sechs verschiedene Plätze, je eine Sondierung — nur der Füllgrad zählt. Jeder Schlüssel landet in einem eigenen Platz. Der Füllgrad α = n/m liegt unter 1, und der Hash verteilt die Schlüssel gleichmäßig über die Tabelle. — Sechs Schlüssel, sechs verschiedene Plätze, je eine Sondierung — nur der Füllgrad zählt.

Alle Schlüssel in einem Platz — Verkettung wird zur Liste

Was du weißt: Alle Schlüssel sind Vielfache der Tabellengröße, k mod m liefert also für jeden denselben Platz. Die Verkettung speichert sie weiterhin alle, aber in einer einzigen Kette.

Sondierregel: O(n)

Rechenbeispiel: Schlüssel 0, 8, 16, 24, 32, 40 in m = 8 → alle landen in Platz 0; das Einfügen kostet 1+2+3+4+5+6 = 21 Sondierungen, im Mittel 3,50

Diesen Fall öffnen: Alle kollidieren

Alle Schlüssel in einem Platz — Verkettung wird zur Liste. Alle sechs Schlüssel in Platz 0: eine Hashtabelle, die zur verketteten Liste geworden ist. Alle Schlüssel sind Vielfache der Tabellengröße, k mod m liefert also für jeden denselben Platz. Die Verkettung speichert sie weiterhin alle, aber in einer einzigen Kette. — Alle sechs Schlüssel in Platz 0: eine Hashtabelle, die zur verketteten Liste geworden ist.

Lineares Sondieren — offene Adressierung mit primärer Clusterbildung

Was du weißt: Keine Ketten: Bei einer Kollision geht man Platz für Platz vorwärts, bis ein freier auftaucht. Jeder Eintrag liegt in der Tabelle selbst.

Sondierregel: (h + i) mod m

Rechenbeispiel: Schlüssel 3, 11, 19, 6, 14, 22 in m = 8 → Plätze 3, 4, 5, 6, 7, 0 mit 1, 2, 3, 1, 2, 3 Sondierungen: im Mittel 2,00, und die sechs Einträge bilden einen durchgehenden Block

Diesen Fall öffnen: Lineare Sondierung

Lineares Sondieren — offene Adressierung mit primärer Clusterbildung. Belegte Plätze verschmelzen zu einem Block; ein Schlüssel darin muss bis ans Ende laufen. Keine Ketten: Bei einer Kollision geht man Platz für Platz vorwärts, bis ein freier auftaucht. Jeder Eintrag liegt in der Tabelle selbst. — Belegte Plätze verschmelzen zu einem Block; ein Schlüssel darin muss bis ans Ende laufen.

Quadratisches Sondieren — keine Cluster, dafür Einfügefehler

Was du weißt: Bei einer Kollision springt man i² Plätze weiter statt i. Das bricht die Cluster auf, aber die Sondierfolge besucht nicht mehr jeden Platz.

Sondierregel: (h + i²) mod m

Rechenbeispiel: dieselben Schlüssel in m = 8 → 3, 4, 7, 6, 2 — und dann scheitert 22 vollständig: Bei einer Zweierpotenz m nimmt i² mod 8 nur die Werte 0, 1 und 4 an, mehr als drei Plätze sind nicht erreichbar

Diesen Fall öffnen: Quadratische Sondierung

Quadratisches Sondieren — keine Cluster, dafür Einfügefehler. Die Sondierfolge springt und wiederholt sich: Plätze bleiben frei, der letzte Schlüssel findet keinen. Bei einer Kollision springt man i² Plätze weiter statt i. Das bricht die Cluster auf, aber die Sondierfolge besucht nicht mehr jeden Platz. — Die Sondierfolge springt und wiederholt sich: Plätze bleiben frei, der letzte Schlüssel findet keinen.

Aufgaben vollständig gelöst

Eine zu 75% volle Tabelle mit durchschnittlich 3,5 Sondierungen pro Suche 5 Schritte
Die Tabelle ist zu 75% gefüllt und benötigt durchschnittlich 3,5 Sondierungen pro Suche. Die Standardformel für lineares Sondieren sagt bei dieser Belegung 2,5 voraus. Finden Sie heraus, welche von beiden falsch ist.
1. Keines von beiden ist falsch, und der Grund liegt in den Schlüsseln. Hasht man jeden der sechs mit der tabelleneigenen Funktion, gibt jeder von ihnen 3 zurück — sie bilden eine arithmetische Folge mit der Differenz 8, und die Tabelle besitzt genau 8 Plätze.
  
  $h (k) = k mod 8 : 3, 11, 19, 27, 35, 43 ⟼ 3, 3, 3, 3, 3, 3$
2. Der Ladefaktor beträgt nach wie vor ehrliche 0,75: sechs Schlüssel in acht Plätzen. Er sagt bloß nichts darüber aus, wohin sie geraten sind.
  
  $α = \frac{n}{m} = \frac{6}{8} = 0.75$
3. Die Sondierungssequenz ist somit die denkbar schlechteste. Der erste Schlüssel landet frei; der zweite rückt einen Platz weiter; der dritte zwei. Sechs Schlüssel kosten 1 + 2 + … + 6 = 21 Sondierungen, von denen 15 den Zusatzaufwand darstellen, den das Panel meldet.
  
  $probes = 1, 2, 3, 4, 5, 6 ⟹ \sum = 21, extra = 21 - 6 = 15$
4. Das ergibt durchschnittlich 3,5 Sondierungen pro Suche.
  
  $\overset{p}{ˉ} = \frac{21}{6} = 3.5$
5. Die Schätzung aus dem Lehrbuch nimmt an, dass die Schlüssel gleichmäßig gestreut sind, und ergibt bei α = 0,75 den Wert 2,5. Die Differenz zwischen 2,5 und 3,5 ist kein Fehler — sie ist der Preis einer Hashfunktion, die einen gemeinsamen Teiler mit der Tabellengröße hat, angewendet auf Schlüssel, die diesen ebenfalls teilen.
  
  $\frac{1}{2} (1 + \frac{1}{1 - α}) = \frac{1}{2} (1 + 4) = 2.5 (random keys) < 3.5$
Antwort

Das Werkzeug gibt α = 0,75, 15 Sondierungen Zusatzaufwand und einen Durchschnitt von 3,5 aus. Die Lehre daraus ist, dass der Ladefaktor zwar die berühmte Kennzahl ist, aber die falsche, um sie allein zu betrachten: Er ist hier identisch mit einer Tabelle, die sechs gut gestreute Schlüssel enthält, was 2,5 kosten würde. Was sich geändert hat, ist das Zusammenspiel zwischen der Schlüsselmenge und dem Modulus. Aus diesem Grund wählt man Tabellengrößen prim, und deshalb verwandelt das Hashing eines Structs über ein Feld, das zufällig ein Vielfaches der Kapazität ist, O(1) in O(n), während jede Kennzahl weiterhin gesund aussieht. Ändern Sie die Größe von 8 auf 7 und beobachten Sie, wie der Durchschnitt einbricht.

$\overset{p}{ˉ} = 3.5 observed vs 2.5 predicted : α is not the whole story$
Eine echte Hashmap, deren Größe sich bei Auslastungsfaktor 0,75 anpasst 6 Schritte
Die Tafel legt 6 Schlüssel in 8 Plätze, Füllgrad 0,75, und meldet 3,5 Sondierungen. Eine erfolgreiche Suche kostet bei diesem Füllgrad etwa 2,5 — bequem. Warum also vergrößert sich jede reale Hash-Map bei genau 0,75, statt sich vollzufüllen?
1. Beginne dort, wo die Tafel steht. Zu drei Vierteln gefüllt, was nach vernünftiger Speichernutzung klingt.
  
  $α = \frac{n}{m} = \frac{6}{8} = 0.75$
2. Die erfolgreiche Suche ist die beruhigende Zahl: im Mittel prüfst du etwa zweieinhalb Plätze, bis der gesuchte Schlüssel auftaucht.
  
  $S (α) \approx \frac{1}{2} (1 + \frac{1}{1 - α}) = \frac{1}{2} (1 + 4) = 2.5$
3. Die erfolglose Suche folgt einer anderen Formel, und in diesem Unterschied steckt die ganze Antwort. Ein Fehlschlag muss bis ans Ende einer Kette belegter Plätze laufen, um die Abwesenheit zu beweisen — deshalb geht der Restterm quadratisch ein, nicht linear.
  
  $U (α) \approx \frac{1}{2} (1 + \frac{1}{( 1 - α ) ^{2}}) = \frac{1}{2} (1 + 16) = 8.5$
4. Treibe den Füllgrad ein wenig höher und lies ab, was das Quadrat anrichtet. Von 0,75 auf 0,90 klingt nach einer bescheidenen Änderung der Belegung.
  
  $U (0.90) = \frac{1}{2} (1 + 100) = 50.5, U (0.95) = \frac{1}{2} (1 + 400) = 200.5$
5. Vergleiche über denselben Schritt die beiden Wachstumsraten. Die Trefferkosten verdoppeln sich gut; die Fehlschlagkosten versechsfachen sich.
  
  $α : 0.75 \to 0.90 ⟹ S : 2.5 \to 5.5 (\times 2.2), U : 8.5 \to 50.5 (\times 5.9)$
6. Also verdoppelt die Tabelle sich stattdessen. Jeder Schlüssel wird neu gehasht, was m Operationen kostet, aber m weitere Einfügungen erkauft, bis es wieder passiert.
  
  $m \to 2 m ⟹ α \to \frac{α}{2}, \frac{m}{m} = O (1)$
Antwort

Ein Fehlschlag kostet bei 0,75 8,5 Sondierungen, bei 0,90 schon 50,5 und bei 0,95 ganze 200,5. Deshalb ist 0,75 in einer Standardbibliothek nach der anderen die Schwelle zum Vergrößern — weniger ein Kompromiss zwischen Speicher und Tempo als der letzte Punkt vor der Klippe. Und maßgeblich ist der Fehlschlag, denn mit einem Fehlschlag beginnt jede Einfügung, und aus nichts anderem besteht jede erfolglose Suche. Die beruhigenden 2,5 beschreiben den Fall, um den man sich ohnehin keine Sorgen machte.

$U (α) = \frac{1}{2} (1 + \frac{1}{( 1 - α ) ^{2}}) : 2.5 (0.50), 8.5 (0.75), 50.5 (0.90), 200.5 (0.95)$

Lernpfad

Wenn zwei Dinge auf demselben Wert landen

Quellen (1)

Hashing, collision resolution and why table size matters, at length: Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edition, §6.4. Addison-Wesley, 1998. ISBN 978-0-201-89685-5.

Vom 42Math-Team · Aktualisiert 2026-07-27

Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen. Redaktionsrichtlinie · Korrekturen

Alle Lektionen: Informatik →

Beispielaufgaben

Keine Kollision - Die Schlüssel 0 bis 5 in einer Tabelle mit 8 Plätzen: 6 verschiedene Plätze, jeweils 1 Sondierung und keine einzige Kollision. Der Belegungsfaktor beträgt bereits 0,75.
Alle kollidieren - Jeder Schlüssel ist ein Vielfaches von 8. Daher werden alle 6 auf Platz 0 abgebildet, und die Kette ist 6 Einträge lang. Im Mittel sind das 3,5 Sondierungen; mit diesem Wert beginnt die durchgerechnete Aufgabe.
Lineare Sondierung - 3, 11 und 19 beanspruchen Platz 3; 6, 14 und 22 Platz 6. Lineares Sondieren bringt alle 6 unter: mit 1, 2, 3, 1, 2 und 3 Sondierungen, also durchschnittlich 2.
Quadratische Sondierung - Bei denselben 6 Schlüsseln lässt sich der letzte durch quadratisches Sondieren nicht mehr einfügen. Quadrate modulo 8 ergeben nur 0, 1 und 4. Von Platz 6 aus erreicht die Sondierungsfolge daher nur 6, 7 und 2; die Plätze 0, 1 und 5 bleiben frei.