Hash-Funktionen

Was sind Hash-Funktionen und wozu dienen sie?

Das Grundprinzip: Vom großen Ganzen zum kleinen Fingerabdruck

Stell dir vor, du hast eine riesige Menge an unterschiedlichen Daten – das können Büchertitel, Produktcodes, Passwörter oder ganze Textdokumente sein. Eine Hash-Funktion ist wie eine spezielle mathematische "Maschine", die jede dieser Eingaben, egal wie lang oder komplex sie ist, in einen vergleichsweise kurzen, oft eindeutig erscheinenden Wert fester Länge umwandelt. Diesen resultierenden Wert nennt man Hash-Wert, Hash-Code oder einfach Hash. Man kann ihn sich wie einen digitalen Fingerabdruck der ursprünglichen Daten vorstellen. Wichtige Eigenschaften guter Hash-Funktionen sind:

• Sie liefern für dieselbe Eingabe immer denselben Hash-Wert.
• Schon eine winzige Änderung in der Eingabe führt in der Regel zu einem komplett anderen Hash-Wert (Lawineneffekt).
• Es ist praktisch unmöglich, aus dem Hash-Wert die ursprünglichen Eingabedaten zurückzurechnen (Einwegfunktion).

Ein wichtiger Anwendungsfall von Hash-Funktionen ist es, einen schnellen und effizienten Zugriff auf Daten zu ermöglichen. Ein Alltagsbeispiel: In einer großen Bibliothek könnte eine Hash-Funktion den Titel eines Buches (Eingabe) nehmen und daraus eine spezifische "Regalnummer" berechnen. Anstatt alle Regale (alle Einträge) durchsuchen zu müssen, kann man direkt zur berechneten Nummer gehen, um das Buch (oder Informationen darüber) schnell zu finden.

Kollisionen: Wenn zwei Schlüssel ins selbe Schloss passen

Obwohl gute Hash-Funktionen darauf ausgelegt sind, für unterschiedliche Eingaben auch unterschiedliche Hash-Werte zu erzeugen, ist es prinzipiell unvermeidbar, dass manchmal zwei verschiedene Eingaben denselben Hash-Wert produzieren. Diesen Fall nennt man eine Kollision. Das liegt daran, dass die Menge der möglichen Eingabedaten (z.B. alle denkbaren Zeichenketten) oft viel größer ist als die Menge der möglichen Hash-Werte (die durch die feste Länge des Hash-Wertes begrenzt ist). Man kann sich das wie das Schubfachprinzip vorstellen: Wenn du mehr Briefe (Eingabedaten) hast, als du Schubfächer (mögliche Hash-Werte) besitzt, müssen zwangsläufig mindestens zwei Briefe im selben Fach landen.

Ein stark vereinfachtes Beispiel: Eine Hash-Funktion für Wörter könnte die Buchstabenwerte (A=1, B=2, …) addieren und das Ergebnis modulo 10 nehmen (d.h. den Rest bei Division durch 10).

• "BAD" (2+1+4 = 7) -> Hash-Wert: 7
• "GUT" (7+21+20 = 48) -> 48 mod 10 = 8 -> Hash-Wert: 8
• "KATZE" (11+1+20+26+5 = 63) -> 63 mod 10 = 3 -> Hash-Wert: 3
• "TOR" (20+15+18 = 53) -> 53 mod 10 = 3 -> Hash-Wert: 3
  Hier hätten "KATZE" und "TOR" denselben Hash-Wert 3 – eine Kollision!

Umgang mit Kollisionen: Strategien für Ordnung im Chaos

Da Kollisionen nicht vollständig vermieden werden können, bedarf es Strategien für ihre Behandlung. Kollisionen können die Effizienz von Suchoperationen erheblich beeinträchtigen, da man bei einem berechneten Hash-Wert möglicherweise mehrere unterschiedliche Originaldaten vorfindet. Ziel ist es immer, Kollisionen so selten wie möglich auftreten zu lassen und sie, wenn sie auftreten, schnell und effizient aufzulösen. Die wichtigsten Strategien sind:

• Verkettung (Chaining): Stell dir vor, jedes "Schubfach" ist nicht nur ein einzelner Platz, sondern der Anfang einer Liste (einer Kette). Wenn mehrere Eingaben denselben Hash-Wert ergeben, werden sie einfach in dieser Liste hintereinander gespeichert. Suchst du ein Element, berechnest du seinen Hash-Wert, gehst zum entsprechenden Index in der Tabelle und durchsuchst dann die dortige (hoffentlich kurze) Liste.
• Offene Adressierung (Open Addressing): Bei dieser Methode wird, wenn ein berechneter Platz (Index) in der Hash-Tabelle bereits durch ein anderes Element belegt ist, systematisch (z.B. einfach den nächsten) nach einem alternativen, freien Platz in der Tabelle gesucht. Ein Alltagsbeispiel: Wenn dein zugewiesener Parkplatz in einem Parkhaus besetzt ist, fährst du weiter (z.B. immer zum nächsten Platz in der Reihe), bis du einen freien Parkplatz findest.

Lernziele

• die Bedeutung von Kollisionsbehandlung in Hash-Tabellen interpretieren, indem die Auswirkungen von Kollisionen auf die Effizienz von Suchoperationen erläutert und verschiedene Strategien zur Kollisionsbehandlung (z.B. Verkettung, offene Adressierung) anhand von Beispielen verglichen werden.
• das grundlegende Konzept und den Zweck von Hash-Funktionen erklären, indem erläutert wird, wie sie Eingabedaten potenziell beliebiger Größe auf einen Ausgabewert fester Größe (Hash-Wert) in einem definierten Wertebereich abbilden und warum diese Abbildung für einen potenziell effizienten Datenzugriff, beispielsweise in Hash-Tabellen, von zentraler Bedeutung ist.
• das Konzept von Kollisionen bei Hashfunktionen und deren prinzipielle Unvermeidbarkeit erklären, indem erklärt wird, wie Kollisionen unvermeidbar entstehen, wenn eine größere Menge von möglichen Eingabewerten auf eine kleinere Menge von möglichen Hash-Werten abgebildet wird (analog zum Schubfachprinzip).