Hashfunktionen Teil 1: Definition und Qualitätskriterien
Wenn Sie sich etwas intensiver mit der Informatik befassen, sind Sie sicherlich bereits einmal auf den Begriff Hashfunktion gestoßen. Dieser spielt für viele aktuelle Techniken eine wichtige Rolle – beispielsweise für die Datenspeicherung oder für Blockchains. Doch auch in vielen weiteren Bereichen sind Hashfunktionen von großer Bedeutung.
Dieser zweiteilige Artikel stellt Ihnen die Hashfunktion vor. Der erste Teil erklärt, was eine Hashfunktion genau ist und nennt die wichtigsten Qualitätskriterien. Der zweite Teil befasst sich dann mit den Anwendungsmöglichkeiten und stellt eine häufig verwendete Hashfunktion vor.
Was ist eine Hashfunktion?
Die Hashfunktion – auf Deutsch häufig auch als Streufunktion bezeichnet – dient dazu, einen Wert aus einer Eingabemenge auf eine Zielmenge abzubilden. Die Zielmenge ist dabei in der Regel deutlich kleiner, sodass hierfür weniger Speicherplatz notwendig ist.
Um dies an einem Beispiel aufzuzeigen, entwickeln wir eine ganz einfache Hashfunktion. Die Eingabemenge stellt hierbei die Klassenliste einer Schule dar. Dabei ziehen wir jedoch nur die Vornamen heran. Unsere Hashfunktion besteht nun darin, die Buchstaben der einzelnen Namen zu zählen. Dieser Wert stellt dann das Ergebnis der Hashfunktion dar und wird den einzelnen Namen zugeordnet. Das kann dann beispielsweise so aussehen:
Katharina → 9
Michael → 7
Nina → 4
Tim → 3
Wenn wir jetzt davon ausgehen, dass wir in einer Tabelle die Anwesenheit der Schüler eintragen wollen, können wir statt der Namen, die vergleichsweise viel Speicherplatz benötigen, einfach die zugehörigen Zahlen eintragen. Dafür ist wesentlich weniger Speicherplatz erforderlich.
Probleme können nun jedoch auftreten, wenn die Namen mehrerer Schüler die gleiche Länge aufweisen. Dazu nehmen wir an, dass auch noch Susanne die Klasse besucht. Ihr Hashwert beträgt 7 – genau wie beim Schüler Michael. Gehen wir davon aus, dass Susanne an einem Tag in der Schule fehlt, tragen wir den Wert 7 in unsere Tabelle ein. Wenn wir später eine Benachrichtigung an die Eltern schreiben wollen und hier nur den Wert 7 vorfinden, wissen wir jedoch nicht, ob an diesem Tag Michael oder Susanne gefehlt hat. Eine eindeutige Zuordnung ist in diesem Fall nicht möglich. In diesem Fall spricht man von einer Kollision, da mehrere Ausgangswerte den gleichen Hashwert erzeugen.
Um dieses Problem zu lösen, ist es sinnvoll, möglichst kollisionsarme Hashfunktionen zu verwenden. Beispielsweise könnten wir auch den Nachnamen hinzuziehen und die Buchstaben ihrer Position im Alphabet entsprechend gewichten. Das würde die Wahrscheinlichkeit für Kollisionen bereits deutlich senken. Für die meisten Schulen wäre auf diese Weise wahrscheinlich bereits eine eindeutige Zuordnung möglich. Es gibt jedoch noch viele weitere Hashfunktionen, die so gestaltet sind, dass die Wahrscheinlichkeit für Kollisionen so gering ist, dass diese bei der praktischen Anwendung keine Rolle spielen.
Darüber hinaus gibt es Anwendungsfälle, bei denen die Verwendung einer Hashfunktion trotz möglicher Kollisionen sinnvoll ist. Um dies zu zeigen, gehen wir einmal davon aus, dass wir einen Schüler bestimmen wollen, der einen Vortrag halten soll. Uns ist eigentlich egal, welchen Schüler wir hierfür auswählen. Die einzige Bedingung besteht darin, dass er an einem bestimmten Schultag, an dem die grundlegenden Informationen für den Vortrag besprochen wurden, anwesend war. Nun können wir zufällig einen Schüler aus der Klassenliste auswählen. Wenn sein Hashwert nicht in der Tabelle erscheint, können wir sicher davon ausgehen, dass er an diesem Tag nicht gefehlt hat. Daher können wir ihn für den Vortrag auswählen.
Ist die entsprechende Nummer hingegen vorhanden, können wir keine sichere Aussage treffen. Es ist möglich, dass der Schüler an diesem Tag gefehlt hat. Es kann aber auch sein, dass ein anderer Schüler gefehlt hat, dessen Name zufällig die gleiche Anzahl an Buchstaben aufweist. In unserem Beispiel ist eine genaue Zuordnung jedoch nicht notwendig. Da wie anfangs ausgeführt jeder beliebige Schüler für den Vortrag infrage kommt, solange er nicht gefehlt hat, können wir einfach einen anderen auswählen und den Test wiederholen – so lange, bis unsere Überprüfung sicherstellt, dass die ausgewählte Person nicht gefehlt hat. Dieses Beispiel wirkt nun sicherlich etwas konstruiert. In der Statistik – und damit im extrem wichtigen Bereich Big Data – bestehen jedoch viele Anwendungsfälle, bei denen der Hashwert alle benötigten Informationen bereitstellt und den erforderlichen Speicherplatz dennoch stark reduzieren kann.
Welche Eigenschaften sollten gute Hashfunktionen aufweisen?
Es gibt unzählige Möglichkeiten, um Hashfunktionen zu erstellen. Allerdings ist es dabei wichtig, auf bestimmte Qualitätskriterien zu achten. Bei unserer oben vorgestellten Funktion, die nur die Buchstaben zählt, handelt es sich zwar um eine Hashfunktion. Diese weist jedoch so hohe Defizite auf, dass sie in der Praxis kaum zum Einsatz kommen wird. In den folgenden Abschnitten stellen wir Ihnen vor, welche Merkmale eine gute Hashfunktion aufweisen sollte.
Geringe Wahrscheinlichkeit für Kollisionen
Die Wahrscheinlichkeit für Kollisionen sollte möglichst gering sein. Insbesondere wenn eine eindeutige Zuordnung notwendig ist, sollte die Wahrscheinlichkeit für solche Kollisionen so gering sein, dass sie statistisch keine Rolle spielt.
Alle Hashwerte sollen möglich sein
Innerhalb des vorgegebenen Wertebereichs sollten alle Hashwerte möglich sein. Wenn die Funktion so gestaltet ist, dass ein bestimmter Wert nicht vorkommen kann, obwohl er zum vorgesehenen Wertebereich gehört, ist die Hashfunktion nicht optimal gewählt. Außerdem sollten die Werte möglichst gleichmäßig über den Wertebereich verteilt sein.
Effiziente Berechnung
Bei der Arbeit mit Hashfunktionen ist es normalerweise notwendig, die entsprechenden Berechnungen sehr häufig durchzuführen. Deshalb ist es wichtig, dass diese effizient ablaufen.
Weitere Anforderungen je nach Anwendungsfall
In manchen Anwendungsfällen bestehen noch weitere Anforderungen an die Hashfunktion. Bei Hashfunktionen, die im Bereich der Kryptographie zum Einsatz kommen, ist beispielsweise eine feste Länge der Hashwerte wichtig. Hashfunktionen sind grundsätzlich nicht umkehrbar – es ist also nicht möglich, den ursprünglichen Wert aus dem Hashwert genau zu berechnen. Bei kryptografischen Hashfunktionen ist es darüber hinaus wichtig, dass der Hashwert auch keine näherungsweisen Rückschlüsse auf den Ausgangswert ermöglicht. Darüber hinaus sollte hierbei selbst eine geringfügige Änderung der ursprünglichen Eingabe zu einem ganz anderen Ergebnis führen. Man spricht hierbei davon, dass die Funktion eine hohe Diffusion aufweist. Bei anderen Anwendungen kann es auch wichtig sein, dass die Hashfunktion ordnungserhaltend ist. Das bedeutet, dass die sortierten Hashwerte die gleiche Reihenfolge aufweisen wie die sortierten Ausgangswerte.
Hashfunktionen bieten vielfältige Anwendungsmöglichkeiten
Nachdem wir herausgearbeitet haben, was eine Hashfunktion genau ist und welche Qualitätskriterien sie aufweisen sollte, stellt sich die Frage, welche Anwendungsmöglichkeiten solche Funktionen in der Praxis bieten. Die Antwort darauf lesen Sie im zweiten Teil dieses Artikels.