So, jetzt wird zum ersten Mal hier im Blog (?) ein „informatisches“ Thema angesprochen. Doch dafür müssen wir zunächst mit einer kleinen Lehrstunde anfangen:
Was bedeutet Hashing / was ist eine Hashing-Funktion?
Eine Hash-Funktion ist eine Vorschrift, die befolgt werden muss, um aus einer großen Eingabemenge Werte kleinerer Größe (den sog. Hash) zu erzeugen. Wenn ihr jetzt nur noch „Hääääh?“ denkt, kann ich das durchaus verstehen. Deswegen gleich mal ein Beispiel: Eine Hashing-Funktion könnte z.B. sein: „Verwende nur die letzte Ziffer einer Zahl“. Diese Hashing-Funktion kann ich auf alle möglichen Zahlen anwenden (von denen es ja bekanntermaßen unendlich viele gibt), und erhalte nur einen von zehn möglichen Werten zurück (eine der Zahlen von 0 bis 9).
Daraus folgt natürlich, dass ich aus einem Hashwert normalerweise nicht den Originalwert wiederherstellen kann. Wenn ich eine Zahl suche, von der ich nur weiß, dass ihr Hashwert mit der obigen Vorschrift 7 ist, bringt mir das gar nichts, da sehr viele Zahlen den Hashwert 7 ergeben können (z.B. 7, 17, 167 oder auch 2136504640654684013168463107).
Andere Beispiele wären z.B. die Bildung der Quersumme einer Zahl oder bei Texten z.B. die Anzahl der im Text vorhandenen Wörter.
Wahrscheinlich wundert ihr euch jetzt, warum man solche Hash-Funktionen überhaupt verwendet. Ein Beispiel wäre beispielsweise die Speicherung von langen Texten: Nehmen wir mal an, ich verwalte ein Archiv mit tausenden von Texten. Dann will ich evtl. keine Texte doppelt haben. Das würde für mich bedeuten, dass ich immer, wenn ich einen neuen Text in die Datenbank eintragen möchte, zunächst nachschauen muss, ob dieser exakte Text schon vorhanden ist. Eine Möglichkeit wäre natürlich, den ersten Text aus der Datenbank auszulesen und diesen dann Buchstabe für Buchstabe mit dem neuen Text zu vergleichen. Stimmen alle Buchstaben überein, sind die Texte gleich. Ansonsten lese ich den zweiten Text aus der Datenbank aus und fange hier wieder mit dem Vergleich an. Das ist natürlich ziemlich aufwändig – ich (mein PC) müsste bei einer großen Datenbank tausende von Buchstaben vergleichen, eine Aufgabe, die auch moderne PCs durchaus eine gewisse Zeit beschäftigen kann.
Aber zum Glück gibt es ja Hashing-Funktionen: Einige von ihnen (mit so tollen Namen wie MD5, SHA1 oder CRC32) erzeugen zu beliebig langen Texten Hashwerte von fester Länge, im Fall von MD5 z.B. 32 Zeichen lang. Also könnte ich als Datenbankverwalter einen Trick anwenden: Da ich weiß, dass ein Hashwert eines bestimmten Textes immer gleich bleibt, speichere ich zu einem Text einfach noch den dazugehörigen MD5-Hash mit ab. Wenn ich dann einen neuen Text speichern möchte, berechne ich den zu diesem Text gehörenden MD5-Hash und schaue in der Datenbank nur noch nach, ob dieser Hash-Wert dort schon gespeichert ist. Dieses Vorgehen ist natürlich viel schneller, als die ganzen Texte einzeln zu vergleichen.
Eine Hashing-Funktion wie die oben von mir erdachte „Anzahl aller Wörter“-Funktion würde prinzipiell natürlich auch klappen – allerdings ist die Wahrscheinlichkeit recht hoch, dass irgendwann einmal zwei Texte die genau gleiche Anzahl an Wörtern haben werden und daher durch den reinen Vergleich dieser Hash-Werte als „gleich“ angesehen werden, was natürlich unerwünscht ist. Dabei spricht der Informatiker dann von einer Kollision. Die „richtigen“ Hashing-Verfahren sind natürlich extra für diesen Fall optimiert, möglichst wenige Kollisionen zu erzeugen.
Jetzt kommen wir aber mal wieder zurück zum Bezug zur Uni. Es ist an einer Uni bekannte Tatsache, dass die Anzahl der Hörer einer Vorlesung nach der ersten Woche rapide abnimmt – viele Studenten kommen zur ersten Vorlesung, hören sich den organisatorischen Schnick-Schnack an und kommen dann erst zur Klausur wieder. Der Fachbereich möchte nun gerne die Gründe für dieses Verhalten ergründen. Also wurden Fragebögen verteilt. Da man jedoch die Verändeurng über eine gewisse Zeit beobachten möchte, werden in ein paar Wochen wohl nochmal Fragebögen verteilt (die dann natürlich nur von den noch anwesenden Studenten ausgefüllt werden können). Um jetzt jedoch aus den Bögen ablesen zu können, *welche* Studenten denn noch da sind (und welche halt nicht mehr), muss es da ein Feld geben, welches jeder Student mit einem einzigartigen und bei jedem Fragebogen gleichen Wert füllen soll. Da die Umfrage jedoch anonym stattfinden soll, kann man die Studenten schlecht bitten, ihren Namen oder die Matrikelnummer in dieses Feld einzutragen. Das ist die Stelle, an der eine Hashing-Funktion ins Spiel kam: Auf dem Zettel stand in etwas folgende Anweisung:
1.: Zweiter Buchstabe im Namen des Haustieres
2.: Dritte Ziffer des Geburtsdatums
3.: Fünfte Ziffer der Handynummer
4.: Zweiter Buchstabe des Mädchennamens der Mutter
In meinem Fall und mit dieser Hashing-Funktion würde ich z.B. A02E in dieses Feld schreiben – und beim nächsten Fragebogen, der die gleiche Anweisung enthalten wird, auf genau den gleichen Wert kommen. Dennoch kann man lediglich aus A02E absolut keine Infos über mich gewinnen – oder wer könnte mir jetzt den Mädchennamen meiner Mutter nennen? Um herauszufinden, welcher Fragebogen meiner ist, bräuchte man den Namen meines Haustieres, mein Geburtsdatum, meine Handynummer und den Geburtsnamen meiner Mutter, müsste daraus meinen Hash-Wert bestimmen und den Stapel danach durchsuchen. Und all diesen Aufwand fabrizieren, nur um festzustellen, dass ich meinen Zettel nicht abgegeben habe? 😉
========
Falls es euch noch interessiert: Der MD5-Hash des Textes oberhalb der „Linie“ ist übrigens: 547c5c6a7d8be7b786d7ea29f59e8f6e
Update: Ich habe mal kurz mein Blog als „Testdatenbank“ genommen und die Anzahl der Wörter pro Artikel gemessen (um genau zu sein habe ich es mir einfacher gemacht und die Leerzeichen pro Artikel gezählt). Ergebnis: Es gäbe sehr viele Kollisionen – 15 verschiedene Artikel haben z.B. genau 55 Wörter, je 14 Artikel haben 49 und 53 Wörter usw. Meine spontan erdachte Hashing-Funktion wäre also in diesem Fall nicht allzu sinnvoll anwendbar. 😉
