Zum Inhalt
Alle Apps

Hashing & Kollisionen

Über diese App

Wie aus einem String ein Tabellenfach wird und wie man darin sucht: Das Rechenwerk rechnet Zeichen für Zeichen bis Hash mod m. Sieben Verfahren von absichtlich schlecht (Länge, erster Buchstabe, Zeichensumme) bis brauchbar (Polynom-Hash, djb2, FNV-1a) plus Zahl selbst. Suche mit Vergleichszähler: Nur ein Fach wird durchsucht, Liste und Suchbaum brauchen 14 und 7 statt 3 Vergleiche. Wachsen bei zwei Dritteln wie dict, Primzahl oder Zweierpotenz, Statistik gegen den Idealwert.

Hashfunktion und Hashtabelle

Eine Hashfunktion rechnet einen beliebig langen String Zeichen für Zeichen in eine Zahl h um, deterministisch, also jedes Mal gleich. Der Rest h mod m bestimmt das Fach einer Tabelle mit m Fächern. So findet man einen Eintrag wieder, ohne die ganze Tabelle zu durchsuchen. Kollisionen sind unvermeidbar, weil es unendlich viele Strings, aber nur m Fächer gibt. Eine gute Hashfunktion verhindert Kollisionen nicht, sie verteilt sie gleichmäßig. Selbst eine perfekt zufällige Verteilung erzeugt Kollisionen, wie das Geburtstagsparadoxon zeigt. Hashing ist keine Verschlüsselung: Zurückrechnen ist nicht möglich.

Was die App zeigt

Ein Rechenwerk berechnet den Hash Zeichen für Zeichen bis zum Fach h mod m, schrittweise oder abgespielt. Sieben Verfahren stehen zur Wahl: absichtlich schlechte (Länge, erster Buchstabe, Zeichensumme), brauchbare (Polynom-Hash mit Faktor 31, djb2, FNV-1a) und für Zahlen „Zahl selbst“. Die Tabellengröße ist wählbar, als Primzahl oder Zweierpotenz, mit automatischem Vergrößern ab einem Lastfaktor von 2/3. Beispiele wie Anagramme, Vornamen oder Seriennummern füllen die Tabelle. Eine Statistik vergleicht Kollisionen und längste Kette mit dem Idealwert.

Selbst ausprobieren

Lade die Anagramme und vergleiche „Summe“ mit „poly31“: Bei der Zeichensumme kollidieren Lager und Regal immer, beim Polynom-Hash nicht. Stelle m auf eine Zweierpotenz und auf eine Primzahl und beobachte die Verteilung. Suche dann ein Wort: Der Vergleichszähler zeigt, dass nur ein Fach durchsucht wird. Zum Vergleich nennt die App, wie viele Vergleiche eine Liste oder ein ausgeglichener Suchbaum brauchen würden.

Häufige Fragen

Wie funktioniert eine Hashtabelle?
Eine Hashtabelle berechnet aus dem Schlüssel mit einer Hashfunktion eine Zahl und daraus per mod m das Fach, in dem der Eintrag liegt. Beim Suchen wird dasselbe Fach berechnet und nur dort nachgesehen. Landen mehrere Schlüssel im selben Fach, werden sie etwa in einer Kette gespeichert.
Was ist eine Kollision beim Hashing?
Eine Kollision liegt vor, wenn zwei verschiedene Schlüssel im selben Fach landen. Kollisionen lassen sich nicht vermeiden, weil es mehr mögliche Schlüssel als Fächer gibt. Eine gute Hashfunktion verteilt die Schlüssel aber gleichmäßig, sodass die Ketten kurz bleiben.
Warum sollte die Größe einer Hashtabelle eine Primzahl sein?
Ist m eine Zweierpotenz, hängt h mod m nur von den unteren Bits von h ab. Bei einer Primzahl beeinflussen alle Bits das Fach. Das gleicht Schwächen der Hashfunktion besser aus; Faktor und m sollten zudem teilerfremd sein.
Welche Hashfunktionen kann ich in der App vergleichen?
Länge, erster Buchstabe, Zeichensumme, Polynom-Hash mit Faktor 31, djb2, FNV-1a und für Zahlenschlüssel „Zahl selbst“. Zu jeder erklärt die App, warum sie gut oder schlecht verteilt.

Fach: Kryptographie

Mehr aus Kryptographie

Eine VisuApp von heyprof: interaktiv, kostenlos im Browser, ohne Anmeldung. Was ist eine VisuApp? · Alle Apps