Was ist Hashing?

Im Kontext von Datenstrukturen und deren effizienter Verwaltung führt kein Weg am Begriff Hashing vorbei. Doch was genau ist eigentlich Hashing? Das Thema ist sehr umfassend und kann sehr komplex werden. Einige Grundbegriffe wie z.B. Hashfunktion, Hashwert oder Schlüsseluniversum sollte in Zeiten der Digitalisierung jeder kennen. Wenn man diese Begriffe beherrscht, hat man auch ein Grundverständnis dieser Datenstruktur. In diesem Artikel erhalten Sie grundlegendes Wissen zum Thema Hashing und kennen anschließend die wichtigsten Begriffe und Charakteristika. Vom Themenbereich IT Sicherheit weichen wir in diesem Artikel ausnahmsweise leicht ab, weil wir einem unserer Werksstudenten mit unserem IT Security Blog eine Plattform bieten möchten. 

Wozu braucht man Hashing?

Betrachten Sie einmal folgende Ausgangssituation: Sie haben eine Menge von Datenobjekten, die mithilfe eines Schlüssels identifiziert werden. Sie wollen diese Datenobjekte in eine Datenstruktur überführen, sodass Sie anschließend die drei wichtigen Operationen „Einfügen“, „Suchen“ und „Löschen“ effizient durchführen können. Das Problem liegt in der Größe des Schlüsseluniversums, welches wesentlich mehr Elemente enthält als es Datenobjekte gibt. Ein Beispiel wäre, dass Ihr Schlüsseluniversum aus den Zahlen 0 bis 1.000.000 besteht, Sie aber nur 10.000 Datenobjekte verwalten müssen. Damit ist Ihr Schlüsseluniversum 100 mal größer als die Menge der Datenobjekte, was zu einigen Problemen führt, wie Sie gleich sehen werden.

Für eine Datenstruktur, in der Suchen, Löschen und Einfügen möglich ist, gibt es natürlich die trivialen Lösungen „Liste“ und „Array“. Falls Sie mit diesen Begriffen nichts anfangen können, ist das nicht weiter schlimm. Wichtig zu wissen ist nur, dass sich bei der Implementierung als Feld eine enorme Speicherplatzverschwendung und bei der Implementierung als Liste lange Laufzeiten der Operationen „Suchen“ und „Löschen“ ergeben. Und um diesen Problemen entgegenzuwirken, gibt es das Hashing.

Was ist Hashing und wie funktioniert Hashing?

Beim Hashing benutzt man eine sogenannte Hashfunktion. Mit dieser Hashfunktion kann man dann eine Datenstruktur erzeugen, die sich bezüglich der zuvor genannten Operationen relativ effizient verwalten lässt. Um das Konzept einer Hashfunktion zu verstehen ist ein bisschen Mathematik erforderlich.

Für die interessierten Leser: Eine Hashfunktion ist eine Funktion die Elemente aus dem Schlüsseluniversum auf eine wesentlich kleinere Menge von sogenannten Hashwerten abbildet. Das heißt die Hashfunktion weist einem Schlüssel einen Hashwert zu. Für das gleich folgende Beispiel muss man wissen, was Modulo bedeutet. Die Modulo-Operation (abgekürzt „mod“) bedeutet Teilen mit Rest. Somit ergibt z.B. 10 mod 3 die Zahl 1, denn „die 3 passt 3 mal in die 10 und lässt den Rest 1 (da 10 – 3*3 = 10 – 9 = 1)“. Damit kann man sich schon eine sehr einfache Hashfunktion bauen. Nehmen wir als Beispiel die Funktion f:U-->{0,…,4} , f(x) = x mod 5 (wobei U das Schlüsseluniversum der Zahlen 0 bis 100 sei). Was Sie wissen müssen, ist, dass diese Funktion jede Zahl aus dem Schlüsseluniversum entweder 0, 1, 2, 3 oder 4 abbildet. Die Zahl 37 beispielsweise wird auf die Zahl 2 abgebildet (siehe Erklärung der Modulo-Operation).

Jetzt unseren IT Security Blog abonnieren!

Nun haben wir schon fast alles, was wir brauchen, um unsere Datenstruktur aufzubauen. Dem aufmerksamen Leser wird aufgefallen sein, dass es noch ein Problem zu lösen gibt. Nämlich die sogenannten Kollisionen. Diese kommen vor, wenn die Hashfunktion zwei oder mehr Schlüssel auf denselben Hashwert abbildet. Um diese Kollisionen in den Griff zu bekommen, gibt es verschiedene Hashing-Strategien wie z.B. „Hashing-by-Chaining“, welches sozusagen eine Kombination aus Array und Liste ist, oder „Offene Adressierung“. Um diese vollständig zu verstehen, muss man jedoch einige wahrscheinlichkeitstheoretische Vorbetrachtungen machen, was diesen Artikel übersteigen würde. Im Wesentlichen sollten Sie jetzt aber wissen, was die Grundidee von Hashing ist.

Fazit

Um nochmal zusammenzufassen, was Sie über Hashing wissen sollten: Mithilfe einer Hasfunktion (Sie kennen bereits eine sehr einfache Hashfunktion) werden die zu bestimmten Datenobjekten gehörigen Schlüssel aus einem sehr großen Schlüsseluniversum auf eine wesentlich kleinere Menge von Hashwerten abgebildet. Dadurch erhält man geringere Laufzeiten bzw. einen geringeren Speicherplatzbedarf im Vergleich zu den unpraktischen Lösungen „Liste“ und „Array“. Im Endeffekt hängt die Effizienz dann davon ab, welche Hashing-Strategie man verwendet, also wie man mit den erwähnten Kollisionen umgeht, und welche Hashfunktion man ausgewählt hat.