Hashfunktion

Eine Hashfunktion, die Namen auf Ganzzahlen abbildet. Für die Namen „John Smith“ und „Sandra Dee“ gibt es eine Kollision. ⓘ

Eine Hashfunktion oder Streuwertfunktion ist eine Abbildung, die eine große Eingabemenge, die Schlüssel, auf eine kleinere Zielmenge, die Hashwerte, abbildet. Eine Hashfunktion ist daher im Allgemeinen nicht injektiv. Die Eingabemenge kann Elemente unterschiedlicher Längen enthalten, die Elemente der Zielmenge haben dagegen meist eine feste Länge. ⓘ

Der Name Hashfunktion stammt vom englischen Verb to hash, das sich mit „zerhacken“ übersetzen lässt. Der deutsche Name lautet Streuwertfunktion. Beide Namen deuten darauf hin, dass diese Funktionen normalerweise darauf angelegt sind, die Daten zu „verstreuen“ und zu „zerhacken“ (siehe auch Zerhacker in der Funktechnik). Speziell in der Informatik verwendet man auch den Begriff Hash-Algorithmus (englisch hash algorithm), da Hashfunktionen oftmals in Form eines Algorithmus spezifiziert werden, der die Berechnung der mathematischen Funktion beschreibt. ⓘ

Die Hash- oder Streuwerte sind meist skalare Werte aus einer begrenzten Teilmenge der natürlichen Zahlen. Eine gute Hashfunktion liefert dabei für die Eingabedaten Werte derart, dass zwei unterschiedliche Eingaben auch zu unterschiedlichen Ausgabewerten führen. ⓘ

Eine Kollision tritt dann auf, wenn unterschiedlichen Eingabedaten derselbe Hashwert zugeordnet wird. Da die Menge der möglichen Hashwerte meist kleiner ist als die der möglichen Eingaben, sind solche Kollisionen dann prinzipiell unvermeidlich, weshalb es Verfahren zur Kollisionserkennung geben muss. Eine gute Hashfunktion zeichnet sich dadurch aus, dass sie für die Eingaben, für die sie entworfen wurde, möglichst wenige Kollisionen erzeugt. Für bekannte und beschränkte Eingabemengen können auch perfekte (kollisionsfreie) Hashfunktionen gefunden werden. ⓘ

In der Datenspeicherung kann ein Hashwert verwendet werden, um die Speicherstelle der angefragten Daten zu berechnen, z. B. in einer Hashtabelle. Bei Prüfsummen verwendet man Hashwerte, um Übertragungsfehler zu erkennen. Ein Hashwert wird deshalb auch als englisch Fingerprint bezeichnet, da er eine nahezu eindeutige Kennzeichnung einer größeren Datenmenge darstellt, so wie ein Fingerabdruck einen Menschen nahezu eindeutig identifiziert. In der Kryptologie werden spezielle kryptographische Hashfunktionen verwendet, bei denen zusätzlich gefordert wird, dass es praktisch unmöglich ist, Kollisionen absichtlich zu finden. ⓘ

Hash-Funktionen und die dazugehörigen Hash-Tabellen werden in Datenspeicher- und -abrufanwendungen verwendet, um auf Daten in einer geringen und nahezu konstanten Zeit pro Abruf zuzugreifen. Sie benötigen nur einen Bruchteil des Speicherplatzes, der für die Daten oder Datensätze selbst erforderlich ist. Hashing ist eine rechen- und speicherplatzeffiziente Form des Datenzugriffs, die die nicht konstante Zugriffszeit von geordneten und ungeordneten Listen und strukturierten Bäumen und den oft exponentiellen Speicherbedarf des direkten Zugriffs auf Zustandsräume mit großen oder variablen Schlüsseln vermeidet. ⓘ

Die Verwendung von Hash-Funktionen beruht auf statistischen Eigenschaften der Interaktion von Schlüssel und Funktion: Das Verhalten im schlimmsten Fall ist mit verschwindend geringer Wahrscheinlichkeit untragbar schlecht, und das Verhalten im mittleren Fall kann nahezu optimal sein (minimale Kollision). ⓘ

Hash-Funktionen sind verwandt mit (und werden oft verwechselt mit) Prüfsummen, Prüfziffern, Fingerabdrücken, verlustbehafteter Kompression, Zufallsfunktionen, fehlerkorrigierenden Codes und Chiffren. Obwohl sich die Konzepte bis zu einem gewissen Grad überschneiden, hat jedes von ihnen seine eigenen Verwendungszwecke und Anforderungen und wird auf unterschiedliche Weise entworfen und optimiert. Die Hash-Funktion unterscheidet sich von diesen Konzepten vor allem in Bezug auf die Datenintegrität. ⓘ

Überblick

Eine Hash-Funktion nimmt eine Eingabe als Schlüssel entgegen, der mit einem Datum oder einem Datensatz verknüpft ist und dazu verwendet wird, diesen für die Anwendung zum Speichern und Abrufen von Daten zu identifizieren. Der Schlüssel kann eine feste Länge haben, wie eine ganze Zahl, oder eine variable Länge, wie ein Name. In einigen Fällen ist der Schlüssel das Datum selbst. Die Ausgabe ist ein Hash-Code, der zur Indizierung einer Hash-Tabelle verwendet wird, die die Daten oder Datensätze oder Zeiger auf sie enthält. ⓘ

Eine Hash-Funktion kann drei Funktionen erfüllen:

• Konvertierung von Schlüsseln variabler Länge in Werte fester Länge (in der Regel Maschinenwortlänge oder weniger), indem sie mit einem paritätserhaltenden Operator wie ADD oder XOR in Wörter oder andere Einheiten gefaltet werden.
• Verwürfeln der Bits des Schlüssels, so dass die resultierenden Werte gleichmäßig über den Schlüsselraum verteilt sind.
• Abbildung der Schlüsselwerte in Werte, die kleiner oder gleich der Größe der Tabelle sind

Eine gute Hash-Funktion erfüllt zwei grundlegende Eigenschaften: 1) sie sollte sehr schnell zu berechnen sein; 2) sie sollte die Duplizierung von Ausgabewerten (Kollisionen) minimieren. Die Wirksamkeit von Hash-Funktionen beruht auf der Erzeugung günstiger Wahrscheinlichkeitsverteilungen, die die Zugriffszeit auf nahezu konstant reduzieren. Hohe Tabellenbelastungsfaktoren, pathologische Schlüsselsätze und schlecht konzipierte Hash-Funktionen können zu Zugriffszeiten führen, die sich der Anzahl der Elemente in der Tabelle linear annähern. Hash-Funktionen können so entworfen werden, dass sie im schlimmsten Fall die beste Leistung erbringen, eine gute Leistung bei hohen Tabellenbelastungsfaktoren bieten und in speziellen Fällen eine perfekte (kollisionsfreie) Abbildung von Schlüsseln in Hash-Codes ermöglichen. Die Implementierung basiert auf paritätserhaltenden Bitoperationen (XOR und ADD), Multiplikation oder Division. Eine notwendige Ergänzung zur Hash-Funktion ist eine Methode zur Kollisionsauflösung, die eine Hilfsdatenstruktur wie verknüpfte Listen oder eine systematische Untersuchung der Tabelle verwendet, um einen leeren Slot zu finden. ⓘ

Hash-Tabellen

Hash-Funktionen werden in Verbindung mit Hash-Tabellen zum Speichern und Abrufen von Datenelementen oder Datensätzen verwendet. Die Hash-Funktion übersetzt den mit den einzelnen Daten oder Datensätzen verbundenen Schlüssel in einen Hash-Code, der zur Indizierung der Hash-Tabelle verwendet wird. Wenn ein Element zur Tabelle hinzugefügt werden soll, kann der Hash-Code einen leeren Slot (auch Bucket genannt) indizieren, in welchem Fall das Element der Tabelle dort hinzugefügt wird. In diesem Fall wird das Element dort der Tabelle hinzugefügt. Wenn der Hash-Code einen vollen Slot indiziert, ist eine Art von Kollisionsauflösung erforderlich: Das neue Element kann ausgelassen (nicht der Tabelle hinzugefügt) werden oder das alte Element ersetzen, oder es kann der Tabelle an einer anderen Stelle durch ein bestimmtes Verfahren hinzugefügt werden. Dieses Verfahren hängt von der Struktur der Hashtabelle ab: Beim verketteten Hashing ist jeder Slot der Kopf einer verketteten Liste oder Kette, und Elemente, die am Slot kollidieren, werden der Kette hinzugefügt. Die Ketten können in zufälliger Reihenfolge gehalten und linear durchsucht werden, oder in serieller Reihenfolge, oder als sich selbst ordnende Liste nach Häufigkeit, um den Zugriff zu beschleunigen. Beim Hashing mit offener Adresse wird die Tabelle ab dem belegten Steckplatz auf eine bestimmte Weise durchsucht, in der Regel durch lineares, quadratisches oder doppeltes Hashing, bis ein offener Steckplatz gefunden oder die gesamte Tabelle durchsucht wurde (Überlauf). Die Suche nach dem Element erfolgt nach demselben Verfahren, bis das Element gefunden wird, ein offener Steckplatz gefunden wird oder die gesamte Tabelle durchsucht wurde (Element nicht in der Tabelle). ⓘ

Spezialisierte Verwendungen

Hash-Funktionen werden auch zum Aufbau von Caches für große, auf langsamen Medien gespeicherte Datensätze verwendet. Ein Cache ist im Allgemeinen einfacher als eine Hash-Suchtabelle, da jede Kollision durch Verwerfen oder Zurückschreiben des älteren der beiden kollidierenden Elemente aufgelöst werden kann. ⓘ

Hash-Funktionen sind ein wesentlicher Bestandteil des Bloom-Filters, einer platzsparenden probabilistischen Datenstruktur, mit der geprüft werden kann, ob ein Element Mitglied einer Menge ist. ⓘ

Ein spezieller Fall von Hashing ist als geometrisches Hashing oder die Gittermethode bekannt. Bei diesen Anwendungen ist die Menge aller Eingaben eine Art metrischer Raum, und die Hashing-Funktion kann als Partition dieses Raums in ein Gitter von Zellen interpretiert werden. Bei der Tabelle handelt es sich häufig um ein Array mit zwei oder mehr Indizes (genannt Grid-Datei, Grid-Index, Bucket-Grid und ähnliche Bezeichnungen), und die Hash-Funktion gibt ein Index-Tupel zurück. Dieses Prinzip wird in der Computergrafik, der rechnergestützten Geometrie und vielen anderen Disziplinen häufig verwendet, um zahlreiche Probleme der Annäherung in der Ebene oder im dreidimensionalen Raum zu lösen, wie z. B. das Auffinden von nahe beieinander liegenden Paaren in einer Reihe von Punkten, von ähnlichen Formen in einer Liste von Formen, von ähnlichen Bildern in einer Bilddatenbank, und so weiter. ⓘ

Hash-Tabellen werden auch verwendet, um assoziative Arrays und dynamische Mengen zu implementieren. ⓘ

Eigenschaften

Einheitlichkeit

Eine gute Hash-Funktion sollte die erwarteten Eingaben so gleichmäßig wie möglich auf ihren Ausgabebereich abbilden. Das heißt, jeder Hash-Wert im Ausgabebereich sollte mit ungefähr der gleichen Wahrscheinlichkeit erzeugt werden. Der Grund für diese letzte Anforderung ist, dass die Kosten von Hash-basierten Methoden stark ansteigen, wenn die Anzahl der Kollisionen - Paare von Eingaben, die auf denselben Hash-Wert abgebildet werden - zunimmt. Wenn das Auftreten einiger Hash-Werte wahrscheinlicher ist als das anderer, muss ein größerer Teil der Nachschlageoperationen eine größere Menge von kollidierenden Tabelleneinträgen durchsuchen. ⓘ

Beachten Sie, dass dieses Kriterium nur voraussetzt, dass der Wert gleichmäßig verteilt ist, nicht zufällig in irgendeinem Sinne. Eine gute Zufallsfunktion ist (außer aus Gründen der Recheneffizienz) im Allgemeinen eine gute Wahl für eine Hash-Funktion, aber das Umgekehrte muss nicht der Fall sein. ⓘ

Hash-Tabellen enthalten oft nur eine kleine Teilmenge der gültigen Eingaben. Zum Beispiel kann eine Mitgliederliste eines Vereins nur etwa hundert Namen von der sehr großen Menge aller möglichen Namen enthalten. In diesen Fällen sollte das Kriterium der Einheitlichkeit für fast alle typischen Teilmengen von Einträgen gelten, die in der Tabelle gefunden werden können, und nicht nur für die globale Menge aller möglichen Einträge. ⓘ

Mit anderen Worten: Wenn eine typische Menge von m Datensätzen in n Tabellenplätze gehasht wird, sollte die Wahrscheinlichkeit, dass ein Bucket viel mehr als m/n Datensätze erhält, verschwindend gering sein. Insbesondere, wenn m kleiner als n ist, sollten nur sehr wenige Buckets mehr als einen oder zwei Datensätze enthalten. Eine kleine Anzahl von Kollisionen ist praktisch unvermeidlich, selbst wenn n viel größer als m ist - siehe das Geburtstagsproblem. ⓘ

In speziellen Fällen, in denen die Schlüssel im Voraus bekannt sind und der Schlüsselsatz statisch ist, kann eine Hash-Funktion gefunden werden, die absolute (oder kollisionsfreie) Einheitlichkeit erreicht. Eine solche Hash-Funktion wird als perfekt bezeichnet. Es gibt keine algorithmische Möglichkeit, eine solche Funktion zu konstruieren - die Suche nach einer solchen Funktion ist eine faktorielle Funktion der Anzahl der zuzuordnenden Schlüssel gegenüber der Anzahl der Tabellenplätze, in die sie eingefügt werden. Die Suche nach einer perfekten Hash-Funktion über mehr als eine sehr kleine Menge von Schlüsseln ist in der Regel rechnerisch nicht machbar; die resultierende Funktion ist wahrscheinlich rechnerisch komplexer als eine Standard-Hash-Funktion und bietet nur einen marginalen Vorteil gegenüber einer Funktion mit guten statistischen Eigenschaften, die eine minimale Anzahl von Kollisionen ergibt. Siehe universelle Hash-Funktion. ⓘ

Eine Abbildung $h\colon K\rightarrow S$ heißt Hashfunktion, wenn $|K|\geq \ |S|$ gilt. Insbesondere liefert $h$ eine Hashtabelle der Größe $|S|$. Die Menge $K$ repräsentiert die Daten, die gehasht werden sollen, und wird auch die Menge der Schlüssel genannt; die Menge $S$ ist die Menge der möglichen Hashwerte. Typischerweise wird die Menge der Hashwerte als Anfangsstück der natürlichen Zahlen gewählt: $S\subseteq \left\{0,\dotsc ,m-1\right\}$. Diese Menge heißt dann auch Adressraum. ⓘ

Typischerweise wird in der Praxis immer nur eine kleine Teilmenge der Schlüssel $K'{}\subseteq {}K$ mit $h$ abgebildet. Die Menge $S':=\{h(k)|k\in K'\}$ sind dann die tatsächlich genutzten Hashwerte. ⓘ

Das Verhältnis $\beta ={\frac {\left|S'\right|}{\left|S\right|}}$ liefert den Belegungsfaktor. ⓘ

Der Fall $k\not =k'\land h(k)=h(k')$ wird als Kollision bezeichnet. Eine injektive Hashfunktion heißt perfekt, u. a. weil sie keine Kollisionen erzeugt. ⓘ

Testen und Messen

Beim Testen einer Hash-Funktion kann die Gleichmäßigkeit der Verteilung der Hash-Werte mit dem Chi-Quadrat-Test bewertet werden. Dieser Test ist ein Maß für die Anpassungsgüte: Er vergleicht die tatsächliche Verteilung der Elemente in den Buckets mit der erwarteten (oder einheitlichen) Verteilung der Elemente. Die Formel lautet: ${\frac {\sum _{j=0}^{m-1}(b_{j})(b_{j}+1)/2}{(n/2m)(n+2m-1)}}$ ⓘ

wobei: $n$ die Anzahl der Schlüssel ist, $m$ die Anzahl der Bereiche ist, $b_{j}$ die Anzahl der Elemente im Bereich ist $j$ ⓘ

Ein Verhältnis innerhalb eines Konfidenzintervalls (0,95 - 1,05) ist ein Hinweis darauf, dass die bewertete Hash-Funktion eine erwartete Gleichverteilung aufweist. ⓘ

Hash-Funktionen können einige technische Eigenschaften haben, die es wahrscheinlicher machen, dass sie eine gleichmäßige Verteilung haben, wenn sie angewendet werden. Eine davon ist das strenge Avalanche-Kriterium: Wenn ein einzelnes Eingabebit ergänzt wird, ändert sich jedes der Ausgabebits mit einer Wahrscheinlichkeit von 50 %. Der Grund für diese Eigenschaft ist, dass ausgewählte Teilmengen des Schlüsselraums eine geringe Variabilität aufweisen können. Damit die Ausgabe gleichmäßig verteilt ist, sollte eine geringe Variabilität, auch nur ein Bit, zu einer hohen Variabilität (d. h. Verteilung über den Tablespace) in der Ausgabe führen. Jedes Bit sollte sich mit einer Wahrscheinlichkeit von 50 % ändern, denn wenn sich einige Bits nur ungern ändern, gruppieren sich die Schlüssel um diese Werte. Wenn sich die Bits zu leicht ändern, nähert sich das Mapping einer festen XOR-Funktion eines einzelnen Bits. Standardtests für diese Eigenschaft sind in der Literatur beschrieben. Die Relevanz des Kriteriums für eine multiplikative Hash-Funktion wird hier bewertet. ⓘ

Effizienz

Bei Anwendungen zur Datenspeicherung und -abfrage ist die Verwendung einer Hash-Funktion ein Kompromiss zwischen Suchzeit und Speicherplatz. Wäre die Suchzeit unbegrenzt, wäre eine sehr kompakte ungeordnete lineare Liste das beste Mittel; wäre der Speicherplatz unbegrenzt, wäre eine zufällig zugängliche Struktur, die durch den Schlüsselwert indiziert werden kann, sehr groß, sehr spärlich, aber sehr schnell. Eine Hash-Funktion benötigt eine endliche Zeit, um einen potenziell großen Schlüsselraum auf eine machbare Menge an Speicherplatz abzubilden, der unabhängig von der Anzahl der Schlüssel in einer begrenzten Zeit durchsuchbar ist. In den meisten Anwendungen sollte die Hash-Funktion mit minimaler Latenzzeit und in zweiter Linie mit einer minimalen Anzahl von Anweisungen berechenbar sein. ⓘ

Die Rechenkomplexität hängt von der Anzahl der erforderlichen Anweisungen und der Latenzzeit der einzelnen Anweisungen ab, wobei die einfachsten die bitweisen Verfahren (Faltung) sind, gefolgt von den multiplikativen Verfahren, und die komplexesten (langsamsten) sind die auf Division basierenden Verfahren. ⓘ

Da Kollisionen selten vorkommen sollten und nur eine geringe Verzögerung verursachen, ansonsten aber harmlos sind, ist es in der Regel besser, eine schnellere Hash-Funktion zu wählen als eine, die mehr Berechnungen erfordert, aber ein paar Kollisionen erspart. ⓘ

Divisionsbasierte Implementierungen können besonders problematisch sein, da die Division auf fast allen Chip-Architekturen mikroprogrammiert ist. Die Division (modulo) durch eine Konstante kann in eine Multiplikation mit der wortgroßen multiplikativen Inverse der Konstante umgewandelt werden. Dies kann durch den Programmierer oder durch den Compiler geschehen. Die Division kann auch direkt in eine Reihe von Schiebe-Subtraktionen und Schiebe-Additionen reduziert werden, obwohl die Minimierung der Anzahl solcher Operationen ein gewaltiges Problem darstellt; die Anzahl der daraus resultierenden Assembler-Anweisungen kann mehr als ein Dutzend betragen und die Pipeline überfordern. Wenn die Architektur über Hardware-Multiplikations-Funktionseinheiten verfügt, ist die Multiplikation mit der Inversen wahrscheinlich ein besserer Ansatz. ⓘ

Wir können zulassen, dass die Tabellengröße n keine Potenz von 2 ist, und müssen trotzdem keine Rest- oder Divisionsoperationen durchführen, da diese Berechnungen manchmal kostspielig sind. Nehmen wir an, n sei deutlich kleiner als 2b. Betrachten wir eine Pseudozufallszahlengeneratorfunktion P(key), die gleichmäßig auf dem Intervall [0, 2b - 1] ist. Eine auf dem Intervall [0, n-1] einheitliche Hash-Funktion ist n P(key)/2b. Wir können die Division durch eine (möglicherweise schnellere) Bitverschiebung nach rechts ersetzen: nP(key) >> b. ⓘ

Wenn Schlüssel wiederholt gehasht werden und die Hash-Funktion kostspielig ist, kann Rechenzeit gespart werden, indem die Hash-Codes vorberechnet und zusammen mit den Schlüsseln gespeichert werden. Übereinstimmende Hash-Codes bedeuten fast sicher, dass die Schlüssel identisch sind. Diese Technik wird für die Transpositionstabelle in Spielprogrammen verwendet, die eine 64-Bit-Hash-Darstellung der Brettposition speichert. ⓘ

Universalität

Ein universelles Hash-Verfahren ist ein Zufallsalgorithmus, der eine Hash-Funktion h aus einer Familie solcher Funktionen so auswählt, dass die Wahrscheinlichkeit einer Kollision zweier beliebiger Schlüssel 1/m beträgt, wobei m die Anzahl der gewünschten unterschiedlichen Hash-Werte ist - unabhängig von den beiden Schlüsseln. Universelles Hashing gewährleistet (in einem probabilistischen Sinne), dass sich die Hash-Funktion für jede Verteilung der Eingabedaten genauso gut verhält wie eine Zufallsfunktion. Es kommt jedoch zu mehr Kollisionen als beim perfekten Hashing und erfordert möglicherweise mehr Operationen als eine spezielle Hash-Funktion. ⓘ

Anwendbarkeit

Eine Hash-Funktion ist in einer Vielzahl von Situationen anwendbar. Eine Hash-Funktion, die nur bestimmte Tabellengrößen oder Zeichenketten bis zu einer bestimmten Länge zulässt oder keinen Seed akzeptiert (d. h. doppeltes Hashing erlaubt), ist nicht so nützlich wie eine, die dies tut. ⓘ

Deterministisch

Ein Hash-Verfahren muss deterministisch sein, d. h. es muss für einen bestimmten Eingabewert immer denselben Hash-Wert erzeugen. Mit anderen Worten, es muss eine Funktion der zu hashenden Daten sein, im mathematischen Sinne des Wortes. Diese Anforderung schließt Hash-Funktionen aus, die von externen variablen Parametern abhängen, wie z. B. Pseudo-Zufallszahlengeneratoren oder die Tageszeit. Sie schließt auch Funktionen aus, die von der Speicheradresse des zu hashenden Objekts abhängen, wenn sich die Adresse während der Ausführung ändern kann (wie es bei Systemen der Fall sein kann, die bestimmte Methoden der Garbage Collection verwenden), obwohl manchmal ein Rehashing des Objekts möglich ist. ⓘ

Der Determinismus steht im Zusammenhang mit der Wiederverwendung der Funktion. Python bietet zum Beispiel die Möglichkeit, dass Hash-Funktionen einen zufälligen Seed verwenden, der einmal beim Start des Python-Prozesses zusätzlich zur zu hashenden Eingabe erzeugt wird. Der Python-Hash (SipHash) ist immer noch eine gültige Hash-Funktion, wenn er in einem einzigen Durchlauf verwendet wird. Werden die Werte jedoch persistiert (z. B. auf die Festplatte geschrieben), können sie nicht mehr als gültige Hash-Werte behandelt werden, da sich der Zufallswert beim nächsten Durchlauf ändern könnte. ⓘ

Definierter Bereich

Oft ist es wünschenswert, dass die Ausgabe einer Hash-Funktion eine feste Größe hat (siehe aber unten). Wenn die Ausgabe beispielsweise auf 32-Bit-Integer-Werte beschränkt ist, können die Hash-Werte als Index in einem Array verwendet werden. Ein solches Hashing wird häufig verwendet, um die Datensuche zu beschleunigen. Die Erzeugung von Ausgaben fester Länge aus Eingaben variabler Länge kann durch Aufteilung der Eingabedaten in Stücke bestimmter Größe erreicht werden. Hash-Funktionen für die Datensuche verwenden einen arithmetischen Ausdruck, der iterativ Teile der Eingabe (z. B. die Zeichen in einer Zeichenkette) verarbeitet, um den Hash-Wert zu erzeugen. ⓘ

Variabler Bereich

In vielen Anwendungen kann der Bereich der Hash-Werte bei jedem Programmlauf unterschiedlich sein oder sich während desselben Laufs ändern (z. B. wenn eine Hash-Tabelle erweitert werden muss). In solchen Situationen benötigt man eine Hash-Funktion, die zwei Parameter benötigt - die Eingabedaten z und die Anzahl n der zulässigen Hash-Werte. ⓘ

Eine gängige Lösung besteht darin, eine feste Hash-Funktion mit einem sehr großen Bereich (z. B. 0 bis 2³² - 1) zu berechnen, das Ergebnis durch n zu teilen und den Rest der Division zu verwenden. Wenn n selbst eine Potenz von 2 ist, kann dies durch Bitmaskierung und Bitverschiebung erreicht werden. Bei diesem Ansatz muss die Hash-Funktion so gewählt werden, dass das Ergebnis eine ziemlich gleichmäßige Verteilung zwischen 0 und n - 1 aufweist, und zwar für jeden Wert von n, der in der Anwendung auftreten kann. Je nach Funktion kann der Rest nur für bestimmte Werte von n einheitlich sein, z. B. für ungerade oder Primzahlen. ⓘ

Variabler Bereich mit minimaler Bewegung (dynamische Hash-Funktion)

Wenn die Hash-Funktion zur Speicherung von Werten in einer Hash-Tabelle verwendet wird, die die Laufzeit des Programms überdauert, und die Hash-Tabelle vergrößert oder verkleinert werden muss, wird die Hash-Tabelle als dynamische Hash-Tabelle bezeichnet. ⓘ

Eine Hash-Funktion, die bei einer Größenänderung der Tabelle die minimale Anzahl von Datensätzen verschiebt, ist wünschenswert. Benötigt wird eine Hash-Funktion H(z,n) - wobei z der Schlüssel ist, der gehasht wird, und n die Anzahl der zulässigen Hash-Werte ist -, so dass H(z,n + 1) = H(z,n) mit einer Wahrscheinlichkeit nahe n/(n + 1). ⓘ

Lineares Hashing und spiralförmige Speicherung sind Beispiele für dynamische Hash-Funktionen, die in konstanter Zeit ausgeführt werden, aber die Eigenschaft der Einheitlichkeit lockern, um die Eigenschaft der minimalen Bewegung zu erreichen. Bei der erweiterbaren Hash-Funktion wird eine dynamische Hash-Funktion verwendet, die zur Berechnung der Hash-Funktion Platz benötigt, der proportional zu n ist, und die eine Funktion der zuvor eingefügten Schlüssel ist. Es wurden mehrere Algorithmen entwickelt, die die Gleichmäßigkeitseigenschaft beibehalten, aber eine zu n proportionale Zeit für die Berechnung des Wertes von H(z,n) benötigen. ⓘ

Eine Hash-Funktion mit minimaler Bewegung ist besonders in verteilten Hash-Tabellen nützlich. ⓘ

Normalisierung von Daten

In einigen Anwendungen können die Eingabedaten Merkmale enthalten, die für Vergleichszwecke irrelevant sind. Bei der Suche nach einem Personennamen kann es zum Beispiel wünschenswert sein, die Unterscheidung zwischen Groß- und Kleinbuchstaben zu ignorieren. Für solche Daten muss eine Hash-Funktion verwendet werden, die mit dem verwendeten Datenäquivalenzkriterium kompatibel ist, d. h. zwei Eingaben, die als äquivalent angesehen werden, müssen denselben Hash-Wert ergeben. Dies kann erreicht werden, indem die Eingabe vor dem Hashing normalisiert wird, z. B. indem alle Buchstaben großgeschrieben werden. ⓘ

Hashing ganzer Datentypen

Es gibt mehrere gängige Algorithmen zum Hashing ganzer Zahlen. Welche Methode die beste Verteilung ergibt, hängt von den Daten ab. Eine der einfachsten und in der Praxis am häufigsten verwendeten Methoden ist die Modulo-Divisionsmethode. ⓘ

Identitäts-Hash-Funktion

Wenn die zu hashenden Daten klein genug sind, kann man die Daten selbst (uminterpretiert als Ganzzahl) als Hashwert verwenden. Die Kosten für die Berechnung dieser Identitäts-Hash-Funktion sind praktisch gleich Null. Diese Hash-Funktion ist perfekt, da sie jede Eingabe auf einen eindeutigen Hash-Wert abbildet. ⓘ

Die Bedeutung von "klein genug" hängt von der Größe des Typs ab, der als Hash-Wert verwendet wird. In Java zum Beispiel ist der Hash-Code eine 32-Bit-Ganzzahl. Daher können die 32-Bit-Integer- und 32-Bit-Fließkomma-Float-Objekte den Wert einfach direkt verwenden, während die 64-Bit-Integer-Long- und 64-Bit-Fließkomma-Double-Objekte diese Methode nicht nutzen können. ⓘ

Auch andere Datentypen können dieses Hashing-Schema verwenden. Bei der Zuordnung von Zeichenketten zwischen Groß- und Kleinschreibung kann zum Beispiel die binäre Kodierung jedes Zeichens, interpretiert als Ganzzahl, verwendet werden, um eine Tabelle zu indizieren, die die alternative Form dieses Zeichens enthält ("A" für "a", "8" für "8" usw.). Wenn jedes Zeichen in 8 Bits gespeichert wird (wie im erweiterten ASCII oder ISO Latin 1), hat die Tabelle nur 2⁸ = 256 Einträge; im Falle von Unicode-Zeichen hätte die Tabelle 17×2¹⁶ = 1114112 Einträge. ⓘ

Die gleiche Technik kann verwendet werden, um zweistellige Ländercodes wie "us" oder "za" auf Ländernamen abzubilden (26² = 676 Tabelleneinträge), 5-stellige Postleitzahlen wie 13083 auf Städtenamen (100000 Einträge) usw. Ungültige Datenwerte (wie z. B. der Ländercode "xx" oder die Postleitzahl 00000) können in der Tabelle undefiniert bleiben oder auf einen geeigneten "Null"-Wert abgebildet werden. ⓘ

Triviale Hash-Funktion

Wenn die Schlüssel gleichmäßig oder hinreichend gleichmäßig über den Schlüsselraum verteilt sind, so dass die Schlüsselwerte im Wesentlichen zufällig sind, können sie als bereits "gehasht" betrachtet werden. In diesem Fall kann eine beliebige Anzahl beliebiger Bits des Schlüssels gewählt und als Index in der Hash-Tabelle zusammengestellt werden. Eine einfache Hash-Funktion könnte zum Beispiel die niedrigstwertigen m Bits ausblenden und das Ergebnis als Index in einer Hash-Tabelle der Größe 2m verwenden. ⓘ

Faltung

Ein gefalteter Hash-Code wird erzeugt, indem die Eingabe in n Abschnitte von m Bits unterteilt wird, wobei 2m die Tabellengröße ist, und eine paritätserhaltende bitweise Operation wie ADD oder XOR verwendet wird, um die Abschnitte zu kombinieren, gefolgt von einer Maske oder einer Verschiebung, um überschüssige Bits am oberen oder unteren Ende abzuschneiden. Bei einer Tabellengröße von 15 Bit und einem Schlüsselwert von 0x0123456789ABCDEF gibt es beispielsweise fünf Abschnitte, die aus 0x4DEF, 0x1357, 0x159E, 0x091A und 0x8 bestehen. Addiert man sie, erhält man 0x7AA4, einen 15-Bit-Wert. ⓘ

Mittlere Quadrate

Ein Mid-Squares-Hash-Code wird durch Quadrieren der Eingabe und Extrahieren einer entsprechenden Anzahl von mittleren Ziffern oder Bits erzeugt. Ist die Eingabe beispielsweise 123.456.789 und die Hash-Tabelle 10.000 groß, ergibt die Quadrierung des Schlüssels 15.241.578.750.190.521, so dass der Hash-Code als die mittleren 4 Ziffern der 17-stelligen Zahl (ohne die hohe Ziffer) 8750 angenommen wird. Die Methode der mittleren Quadrate ergibt einen vernünftigen Hash-Code, wenn der Schlüssel nicht viele führende oder nachfolgende Nullen enthält. Dies ist eine Variante des multiplikativen Hashings, aber nicht so gut, weil ein beliebiger Schlüssel kein guter Multiplikator ist. ⓘ

Divisions-Hashing

Eine Standardtechnik besteht darin, eine Modulo-Funktion auf den Schlüssel anzuwenden, indem ein Divisor gewählt wird $M$ der eine Primzahl nahe der Tabellengröße ist, also $h(K)=K{\bmod {M}}$. Die Tabellengröße ist normalerweise eine Potenz von 2. Dies ergibt eine Verteilung von $\{0,M-1\}$. Dies führt zu guten Ergebnissen bei einer großen Anzahl von Schlüsselsätzen. Ein erheblicher Nachteil des Divisions-Hashings ist, dass die Division auf den meisten modernen Architekturen, einschließlich x86, mikroprogrammiert ist und 10 Mal langsamer sein kann als die Multiplikation. Ein weiterer Nachteil besteht darin, dass geclusterte Schlüssel nicht aufgelöst werden können. Die Schlüssel 123000, 456000, 789000 usw. modulo 1000 sind zum Beispiel alle auf dieselbe Adresse abgebildet. Diese Technik funktioniert in der Praxis gut, da viele Schlüsselsätze bereits ausreichend zufällig sind und die Wahrscheinlichkeit, dass ein Schlüsselsatz durch eine große Primzahl zyklisch ist, gering ist. ⓘ

Algebraische Kodierung

Algebraische Kodierung ist eine Variante der Divisionsmethode des Hashings, bei der die Division durch ein Polynom modulo 2 anstelle einer ganzen Zahl verwendet wird, um n Bits auf m Bits abzubilden. Bei diesem Ansatz $M=2^{m}$ und wir postulieren ein $m$Polynom dritten Grades $\mathrm {Z} (x)=x^{m}+\zeta _{m-1}x^{m-1}+...+\zeta _{0}$. Ein Schlüssel $K=(k_{n-1}...k_{1}k_{0})_{2}$ kann als das Polynom angesehen werden $K(x)=k_{n-1}x^{n-1}+...+k_{1}x+k_{0}$. Der Rest mit Polynomarithmetik modulo 2 ist $K(x){\bmod {Z}}(x)=h_{m-1}x^{m-1}+...+h_{1}x+h_{0}$. Dann ist $h(K)=(h_{m-1}...h_{1}h_{0})_{2}$. Wenn $Z(x)$ so konstruiert ist, dass es t oder weniger Nicht-Null-Koeffizienten hat, dann sind Schlüssel, die weniger als t Bits gemeinsam haben, garantiert kollisionsfrei. ⓘ

Z eine Funktion von k, t und n, ein Teiler von 2k-1, wird aus dem Feld GF(2k) konstruiert. Knuth gibt ein Beispiel: für n=15, m=10 und t=7, $Z(x)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1$. Die Herleitung ist wie folgt: ⓘ

Sei $S$ sei die kleinste Menge von ganzen Zahlen, so dass $\{1,2,...,t\}\subseteq S$ und $(2j{\bmod {n}})\in S\quad \forall j\in S$. ⓘ

Definieren Sie $P(x)=\prod _{j\in S}(x-\alpha ^{j})$ wobei $\alpha \in ^{n}GF(2^{k})$ und wobei die Koeffizienten von $P(x)$ in diesem Feld berechnet werden. Dann ist der Grad von $P(x)=|S|$. Da $\alpha ^{2j}$ eine Wurzel von $P(x)$ ist, wenn $\alpha ^{j}$ eine Wurzel ist, folgt daraus, dass die Koeffizienten $p^{i}$ von $P(x)$ erfüllen $p_{i}^{2}=p_{i}$ also sind sie alle 0 oder 1. Wenn $R(x)=r_{(n-1)}x^{n-1}+...+r_{1}x+r_{0}$ ein beliebiges ungleichnamiges Polynom modulo 2 mit höchstens t ungleichnamigen Koeffizienten ist, dann $R(x)$ nicht ein Vielfaches von $P(x)$ modulo 2. Daraus folgt, dass die entsprechende Hash-Funktion Schlüssel, die weniger als t Bits gemeinsam haben, auf eindeutige Indizes abbilden wird. ⓘ

Das übliche Ergebnis ist, dass entweder n oder t oder beides groß wird, damit das Verfahren rechnerisch machbar ist. Daher eignet es sich eher für eine Hardware- oder Mikrocode-Implementierung. ⓘ

Eindeutiges Permutations-Hashing

Siehe auch Unique Permutation Hashing, das eine garantierte Best-Worst-Case-Einfügezeit hat. ⓘ

Multiplikatives Hashing

Das standardmäßige multiplikative Hashing verwendet die Formel $h_{a}(K)=\lfloor (aK{\bmod {W}})/(W/M)\rfloor$ die einen Hash-Wert in $\{0,\ldots ,M-1\}$. Der Wert $a$ ist ein geeignet gewählter Wert, der eine relative Primzahl zu $W$sein sollte; er sollte groß sein und seine binäre Darstellung sollte eine zufällige Mischung aus 1en und 0en sein. Ein wichtiger praktischer Sonderfall tritt auf, wenn $W=2^{w}$ und $M=2^{m}$ Potenzen von 2 sind und $w$ die Wortgröße der Maschine ist. In diesem Fall wird diese Formel zu $h_{a}(K)=\lfloor (aK{\bmod {2}}^{w})/2^{w-m}\rfloor$. Dies ist ein Sonderfall, weil die Arithmetik modulo $2^{w}$ in einfachen Programmiersprachen standardmäßig durchgeführt wird und die Division ganzer Zahlen durch eine Potenz von 2 einfach eine Rechtsverschiebung ist, so dass diese Funktion in C z. B. zu

unsigned hash(unsigned K)
{ 
   return (a*K) >> (w-m);
}

und für feste $m$ und $w$ entspricht dies einer einzigen ganzzahligen Multiplikation und Rechtsverschiebung, was diese Funktion zu einer der am schnellsten zu berechnenden Hash-Funktionen macht. ⓘ

Multiplikatives Hashing ist anfällig für einen "allgemeinen Fehler", der zu einer schlechten Verbreitung führt - höherwertige Eingabebits wirken sich nicht auf niederwertige Ausgabebits aus. Dies wird durch eine Transmutation der Eingabe korrigiert, bei der die Spanne der beibehaltenen oberen Bits nach unten verschoben und vor dem Multiplikationsschritt mit dem Schlüssel XOR- oder ADD-verknüpft wird. Die resultierende Funktion sieht also wie folgt aus:

unsigned hash(unsigned K)
{
   K ^= K >> (w-m); 
   return (a*K) >> (w-m);
} ⓘ

Fibonacci-Hashing

Fibonacci-Hashing ist eine Form des multiplikativen Hashings, bei der der Multiplikator $2^{w}/\phi$ist, wobei $w$ die Wortlänge der Maschine ist und $\phi$ (phi) der Goldene Schnitt ist (ungefähr 5/3). Eine Eigenschaft dieses Multiplikators ist, dass er Blöcke aufeinanderfolgender Schlüssel in Bezug auf einen beliebigen Block von Bits im Schlüssel gleichmäßig über den Tabellenraum verteilt. Aufeinanderfolgende Schlüssel innerhalb der hohen oder niedrigen Bits des Schlüssels (oder eines anderen Feldes) sind relativ häufig. Die Multiplikatoren für verschiedene Wortlängen $^{w}$ sind:

• 16: a=40503₁₀
• 32: a=2654435769₁₀
• 48: a=173961102589771₁₀
• 64: a=11400714819323198485_{10 ⓘ}

Zobrist-Hashing

Tabulation Hashing, allgemeiner bekannt als Zobrist Hashing nach Albert Zobrist, einem amerikanischen Informatiker, ist eine Methode zur Konstruktion universeller Familien von Hash-Funktionen durch die Kombination von Tabellennachschlagen mit XOR-Operationen. Dieser Algorithmus hat sich als sehr schnell und qualitativ hochwertig für Hash-Zwecke erwiesen (insbesondere Hashing von ganzzahligen Schlüsseln). ⓘ

Das Zobrist-Hashing wurde ursprünglich als Mittel zur kompakten Darstellung von Schachpositionen in Computerspielprogrammen eingeführt. Jeder Figurentyp (jeweils sechs für Schwarz und Weiß) wurde auf jedem Feld des Brettes eine eigene Zufallszahl zugewiesen. Zu Beginn des Programms wird also eine Tabelle mit 64x12 solcher Zahlen initialisiert. Die Zufallszahlen konnten beliebig lang sein, aber 64 Bits waren aufgrund der 64 Felder auf dem Brett naheliegend. Eine Position wurde transkribiert, indem die Figuren in einer Position durchlaufen wurden, die entsprechenden Zufallszahlen indiziert wurden (leere Felder wurden nicht in die Berechnung einbezogen) und sie miteinander XOR-verknüpft wurden (der Startwert konnte 0, der Identitätswert für XOR oder ein Zufallswert sein). Der resultierende Wert wurde durch Modulo, Faltung oder eine andere Operation reduziert, um einen Hash-Tabellenindex zu erzeugen. Die ursprüngliche Zobrist-Hashtabelle wurde in der Tabelle als Darstellung der Position gespeichert. ⓘ

Später wurde die Methode auf das Hashing ganzer Zahlen erweitert, indem jedes Byte an jeder der 4 möglichen Positionen im Wort durch eine eindeutige 32-Bit-Zufallszahl dargestellt wurde. Auf diese Weise wird eine Tabelle mit 2⁸x4 solcher Zufallszahlen erstellt. Eine gehashte 32-Bit-Ganzzahl wird transkribiert, indem die Tabelle nacheinander mit dem Wert jedes Bytes der Klartext-Ganzzahl indiziert und die geladenen Werte miteinander XOR-verknüpft werden (auch hier kann der Startwert der Identitätswert oder ein Zufallswert sein). Die natürliche Erweiterung auf 64-Bit-Ganzzahlen ist die Verwendung einer Tabelle mit 2⁸x8 64-Bit-Zufallszahlen. ⓘ

Diese Art von Funktion hat einige nette theoretische Eigenschaften, eine davon ist die so genannte 3-Tupel-Unabhängigkeit, d. h., dass jedes 3-Tupel von Schlüsseln mit gleicher Wahrscheinlichkeit auf jedes 3-Tupel von Hash-Werten abgebildet wird. ⓘ

Maßgeschneiderte Hash-Funktion

Eine Hash-Funktion kann so gestaltet werden, dass sie die vorhandene Entropie in den Schlüsseln ausnutzt. Wenn die Schlüssel führende oder abschließende Nullen oder bestimmte Felder aufweisen, die nicht verwendet werden, immer Null oder eine andere Konstante sind oder im Allgemeinen wenig variieren, dann führt das Ausblenden nur der flüchtigen Bits und das Hashing mit diesen zu einer besseren und möglicherweise schnelleren Hash-Funktion. Ausgewählte Divisoren oder Multiplikatoren in den Divisions- und Multiplikationsverfahren können einheitlichere Hash-Funktionen ergeben, wenn die Schlüssel zyklisch sind oder andere Redundanzen aufweisen. ⓘ

Hashing von Daten mit variabler Länge

Wenn es sich bei den Datenwerten um lange (oder variable) Zeichenketten handelt - wie z. B. Personennamen, Webseitenadressen oder E-Mail-Nachrichten - ist ihre Verteilung in der Regel sehr ungleichmäßig und weist komplizierte Abhängigkeiten auf. So weist beispielsweise Text in einer natürlichen Sprache eine sehr ungleichmäßige Verteilung von Zeichen und Zeichenpaaren auf, die für die Sprache charakteristisch sind. Für solche Daten ist es ratsam, eine Hash-Funktion zu verwenden, die von allen Zeichen der Zeichenkette abhängt - und zwar von jedem Zeichen auf unterschiedliche Weise. ⓘ

Mitte und Ende

Einfache Hash-Funktionen können die ersten und letzten n Zeichen einer Zeichenfolge zusammen mit der Länge addieren oder einen wortgroßen Hash aus den mittleren 4 Zeichen einer Zeichenfolge bilden. Dies erspart die Iteration über die (potenziell lange) Zeichenkette, aber Hash-Funktionen, die nicht alle Zeichen einer Zeichenkette hashen, können aufgrund von Redundanzen, Clusterbildung oder anderen Pathologien im Schlüsselsatz leicht linear werden. Solche Strategien können als benutzerdefinierte Hash-Funktionen effektiv sein, wenn die Struktur der Schlüssel so ist, dass entweder die Mitte, die Enden oder andere Felder Null sind oder eine andere unveränderliche Konstante, die die Schlüssel nicht unterscheidet; dann können die unveränderlichen Teile der Schlüssel ignoriert werden. ⓘ

Zeichenfaltung

Das paradigmatische Beispiel für die Faltung nach Zeichen ist die Addition der ganzzahligen Werte aller Zeichen in der Zeichenkette. Eine bessere Idee ist es, die Hash-Summe mit einer Konstanten zu multiplizieren, typischerweise einer großen Primzahl, bevor das nächste Zeichen hinzugefügt wird, wobei ein Überlauf ignoriert wird. Die Verwendung von exklusivem 'oder' anstelle von addieren ist ebenfalls eine plausible Alternative. Die letzte Operation wäre ein Modulo, eine Maske oder eine andere Funktion, um den Wortwert auf einen Index in der Größe der Tabelle zu reduzieren. Die Schwäche dieses Verfahrens besteht darin, dass sich die Informationen in den oberen oder unteren Bits der Bytes häufen können, was im Hash-Ergebnis verbleibt und mehr Kollisionen verursacht als ein richtiger zufälliger Hash. ASCII-Byte-Codes haben z. B. ein oberes Bit von 0, und druckbare Zeichenketten verwenden nicht die ersten 32 Byte-Codes, so dass die Informationen (95-Byte-Codes) in den verbleibenden Bits auf nicht offensichtliche Weise gebündelt werden. ⓘ

Der klassische Ansatz, der als PJW-Hash bezeichnet wird und auf die Arbeit von Peter. J. Weinberger bei ATT Bell Labs in den 1970er Jahren, wurde ursprünglich für das Hashing von Bezeichnern in Compiler-Symboltabellen entwickelt, wie sie im "Dragon Book" angegeben sind. Diese Hash-Funktion versetzt die Bytes um 4 Bits, bevor sie zusammenaddiert werden. Wenn die Menge umgewandelt wird, werden die hohen 4 Bits herausgeschoben und, falls sie nicht Null sind, mit XOR in das niedrige Byte der kumulativen Menge zurückgeschrieben. Das Ergebnis ist ein wortgroßer Hash-Code, auf den ein Modulo oder eine andere Reduktionsoperation angewendet werden kann, um den endgültigen Hash-Index zu erhalten. ⓘ

Heutzutage, insbesondere mit dem Aufkommen von 64-Bit-Wortgrößen, ist ein sehr viel effizienteres Hashing von Zeichenketten variabler Länge nach Wortteilen möglich. ⓘ

Wortlängen-Faltung

Moderne Mikroprozessoren ermöglichen eine wesentlich schnellere Verarbeitung, wenn 8-Bit-Zeichenketten nicht durch Verarbeitung eines Zeichens nach dem anderen gehasht werden, sondern durch Interpretation der Zeichenkette als Array von 32-Bit- oder 64-Bit-Ganzzahlen und Hashing/Akkumulation dieser "wortweiten" Ganzzahlwerte mittels arithmetischer Operationen (z. B. Multiplikation mit Konstanten und Bit-Shifting). Das letzte Wort, das unbesetzte Byte-Positionen haben kann, wird mit Nullen oder einem bestimmten "Zufallswert" aufgefüllt, bevor es in den Hash-Code eingefügt wird. Der akkumulierte Hash-Code wird durch eine abschließende Modulo- oder andere Operation reduziert, um einen Index in der Tabelle zu erhalten. ⓘ

Radix-Konvertierungs-Hashing

Analog zu der Art und Weise, wie eine ASCII- oder EBCDIC-Zeichenkette, die eine Dezimalzahl darstellt, in eine numerische Größe für die Berechnung umgewandelt wird, kann eine Zeichenkette variabler Länge als (x₀ak-1+x₁ak-2+...+xk-2a+xk-1) umgewandelt werden. Dies ist einfach ein Polynom in einer von Null verschiedenen Radix a!=1, das die Komponenten (x₀,x₁,...,xk-1) als die Zeichen der Eingabezeichenfolge der Länge k annimmt. Der Wert von a ist in der Regel eine Primzahl, die mindestens groß genug ist, um die Anzahl der verschiedenen Zeichen im Zeichensatz der potenziellen Schlüssel aufzunehmen. Das Hashing von Zeichenketten durch Radix-Konvertierung minimiert die Anzahl der Kollisionen. Die verfügbaren Datengrößen können die maximale Länge der Zeichenfolge, die mit dieser Methode gehasht werden kann, einschränken. Bei einem 128-Bit-Doppellangwort kann beispielsweise nur eine alphabetische Zeichenkette mit 26 Zeichen (ohne Groß- und Kleinschreibung) mit einem Radix von 29 gehasht werden; eine druckbare ASCII-Zeichenkette ist bei Radix 97 und einem 64-Bit-Langwort auf 9 Zeichen begrenzt. Alphabetische Schlüssel sind jedoch in der Regel von bescheidener Länge, da die Schlüssel in der Hashtabelle gespeichert werden müssen. Numerische Zeichenketten sind in der Regel kein Problem; 64 Bit können bis zu 10¹⁹ oder 19 Dezimalziffern mit Radix 10 zählen. ⓘ

Rollierender Hash

In einigen Anwendungen, z. B. bei der Teilzeichensuche, kann man eine Hash-Funktion h für jede k-Zeichen-Teilzeichenkette einer gegebenen n-Zeichenkette berechnen, indem man ein Fenster mit einer Breite von k Zeichen entlang der Zeichenkette vorschiebt, wobei k eine feste ganze Zahl ist und n größer als k. Die einfache Lösung, eine solche Teilzeichenkette an jeder Zeichenposition im Text zu extrahieren und h separat zu berechnen, erfordert eine Anzahl von Operationen proportional zu k-n. Bei richtiger Wahl von h kann man jedoch die Technik des Rolling Hash verwenden, um alle diese Hashes mit einem Aufwand proportional zu mk + n zu berechnen, wobei m die Anzahl der Vorkommen der Teilzeichenkette ist. ⓘ

Der bekannteste Algorithmus dieser Art ist Rabin-Karp mit einer Leistung im besten und mittleren Fall von O(n+mk) und im schlimmsten Fall von O(n-k) (fairerweise muss man sagen, dass der schlimmste Fall hier sehr pathologisch ist: Sowohl die Textzeichenfolge als auch die Teilzeichenfolge bestehen aus einem einzigen, sich wiederholenden Zeichen, z. B. t="AAAAAAAAAAA" und s="AAA"). Die für den Algorithmus verwendete Hash-Funktion ist in der Regel der Rabin-Fingerprint, der zur Vermeidung von Kollisionen in 8-Bit-Zeichenketten entwickelt wurde, aber auch andere geeignete Hash-Funktionen werden verwendet. ⓘ

Analyse

Das Worst-Case-Ergebnis für eine Hash-Funktion kann auf zwei Arten bewertet werden: theoretisch und praktisch. Das theoretische Worst-Case-Ergebnis ist die Wahrscheinlichkeit, dass alle Schlüssel auf einen einzigen Slot abgebildet werden. Der praktisch ungünstigste Fall ist die erwartete längste Prüfsequenz (Hash-Funktion + Kollisionsauflösungsmethode). Bei dieser Analyse wird ein einheitliches Hashing berücksichtigt, d. h. jeder Schlüssel wird mit einer Wahrscheinlichkeit von 1/m auf einen bestimmten Slot abgebildet, was für universelle Hash-Funktionen charakteristisch ist. ⓘ

Während Knuth sich Sorgen über gegnerische Angriffe auf Echtzeitsysteme macht, hat Gonnet gezeigt, dass die Wahrscheinlichkeit eines solchen Falles "lächerlich gering" ist. Er stellte dar, dass die Wahrscheinlichkeit, dass k von n Schlüsseln auf einen einzigen Slot abgebildet werden, wie folgt ist ${\frac {e^{-\alpha }\alpha ^{k}}{k!}}$ wobei α der Auslastungsfaktor, n/m, ist. ⓘ

Geschichte

Der Begriff Hash bietet eine natürliche Analogie zu seiner nicht-technischen Bedeutung (etwas zerhacken oder durcheinander bringen), da Hash-Funktionen ihre Eingabedaten verschlüsseln, um ihre Ausgabe abzuleiten. Bei seinen Nachforschungen über den genauen Ursprung des Begriffs stellt Donald Knuth fest, dass Hans Peter Luhn von IBM das Konzept der Hash-Funktion in einem Memo vom Januar 1953 als Erster verwendet zu haben scheint, der Begriff selbst aber erst in den späten 1960er Jahren in Herbert Hellermans Digital Computer System Principles in der veröffentlichten Literatur auftauchte, obwohl er zu diesem Zeitpunkt bereits weit verbreiteter Jargon war. ⓘ

Anwendungen

Hashfunktionen werden typischerweise angewendet, um

• einem komplexen Objekt eine Speicheradresse zuzuweisen. Zum Beispiel könnte „Max Mustermann“ im Ordner M abgelegt werden, dem ersten Buchstaben des Nachnamens.
• eine kurze Prüfsumme zu dem Objekt zu berechnen. Beispiel sind die Prüfsumme einer ISBN und die zyklische Redundanzprüfung zur Erkennung von Übertragungsfehlern von Dateien.
• einen Inhalt nahezu eindeutig, aber mit wenig Speicherplatz zu identifizieren, ohne etwas über den Inhalt zu verraten, zum Beispiel in der Kryptographie. ⓘ

Je nach Anwendung hat man unterschiedliche Anforderungen an die Funktion. Gruppiert man beispielsweise eine Adresskartei nach dem ersten Buchstaben des Nachnamens, so spart man sich offensichtlich bei der Suche viel Zeit, denn man braucht nur einen von 26 Teilen zu durchsuchen. Diese Hashfunktion ist für den Menschen sehr praktisch, da sie sehr einfach zu berechnen ist, jedoch würde ein Computerprogramm andere Verfahren verwenden, um ein Adressbuch zu organisieren. Für das Programm ist es nämlich wichtig, möglichst wenige Kollisionen zu haben. Es gibt aber offenbar viele Namen, die mit demselben Anfangsbuchstaben beginnen, und sie kommen ungleichmäßig oft vor. Legt man also beispielsweise Personalakten nach diesem Prinzip ab, so hat man oftmals viele Akten im Ordner mit dem Buchstaben S, während der Ordner Q leer bleibt. ⓘ

Die einstellige Quersumme ist eine sehr einfache Hashfunktion. Sie ordnet einer beliebigen Zahl eine einstellige Zahl zu, so wird beispielsweise 25 auf 2 + 5 = 7 abgebildet. Als Prüfsumme ist diese Quersumme aber nicht gut geeignet, da die Vertauschung von Ziffern – ein typischer Fall beim Abtippen von langen Zahlen – nicht erkannt wird. So hat auch die Zahl 52 dieselbe Quersumme 5 + 2 = 7. Prüfsummen wie bei der ISBN eines Buches oder die CRC-32-Prüfsumme einer Datei, z. B. beim Prüfen einer aus dem Internet heruntergeladenen Datei auf Übertragungsfehler, eignen sich besser, derartige Fehler zu erkennen. ⓘ

Bei der Identifikation von Inhalten mit kryptographischen Hashfunktionen ist es nicht nur wichtig, dass sich der gesamte Hashwert mit allen Bits bei jeder kleinen Modifikation scheinbar zufällig ändert und dass es fast unmöglich ist, einen zweiten Inhalt mit demselben Hashwert zu erzeugen, um einen Komplettaustausch des Inhaltes zu vermeiden. Ebenso wichtig ist es, dass der Inhalt nicht aus dem Hashwert rekonstruiert werden kann. Hat man zwei Dokumente ausgetauscht und möchte beispielsweise am Telefon die erfolgreiche Übertragung überprüfen, so reicht es, am Telefon die Korrektheit des Hashwertes zu überprüfen. Wird das Gespräch abgehört, so wird dabei nichts über den Inhalt der Nachricht verraten, selbst falls Teile des Inhalts bereits bekannt sein sollten. ⓘ

Datenbanken

Datenbankmanagementsysteme verwenden Hashfunktionen, um Daten in großen Datenbeständen mittels Hashtabellen zu suchen. Darüber wird ein Datenbankindex realisiert. ⓘ

Mittels Hashfunktionen kann zudem die Fragmentierung von Datensätzen realisiert werden. Dabei wird die Hashfunktion auf den Primärschlüssel des betreffenden Objektes angewandt. Das Ergebnis referenziert dann seinen Speicherort. ⓘ

Auch für vergleichsweise kleine Datenmengen werden Hashfunktionen benutzt, beispielsweise in Kompressionsalgorithmen wie LZW. ⓘ

Prüfsummen

Prüfsummen sind ein einfaches Mittel, um die Plausibilität zur Erkennung von Veränderungen an übertragenen Daten zu erhöhen. Nur die Teilmenge der Datenvarianten, die bei Berechnung der Prüfsumme das gleiche Ergebnis wie das der Original-Daten erzeugen, kann noch als Verfälschung unerkannt bleiben. Mit mehreren verschiedenen passend erzeugten Prüfsummen kann die Wahrscheinlichkeit einer Kollision stark reduziert werden. ⓘ

Ein Fehler ist immer feststellbar, wenn die berechnete Prüfsumme der empfangenen Daten sich von der übertragenen Prüfsumme, also der der Originaldaten, unterscheidet. Falls ein Fehler festgestellt wird, kann die Verfälschung auch ausschließlich in der Prüfsumme enthalten sein. Die Eignung verschiedener Hashfunktionen zur Prüfsummenberechnung hängt von deren Kollisionswahrscheinlichkeit ab. ⓘ

Wenn die Prüfsumme vor gezielten Manipulationen der Daten schützen soll, wird eine kryptographische Hashfunktion verwendet, da hier nur mit sehr hohem Rechenaufwand eine Kollision gefunden werden kann. ⓘ

Beispiele

Hashwerte haben unter anderem bei P2P-Anwendungen aus verschiedenen Gründen eine wichtige Aufgabe. Die Hashwerte werden hier sowohl zum Suchen und Identifizieren von Dateien als auch zum Erkennen und Prüfen von übertragenen Dateifragmenten verwendet. So lassen sich große Dateien zuverlässig in kleinen Segmenten austauschen. ⓘ

Zur Anwendung in P2P-Netzen kommen vor allem gestufte Hashfunktionen, bei denen für kleinere Teile einer Datei der Hashwert und dann aus diesen Werten ein Gesamtwert berechnet wird. Bei den Netzwerken Gnutella G2, Shareaza und Direct Connect sind dies zum Beispiel Tiger-Tree-Hash-Funktionen. ⓘ

Das Auffinden von Dateien anhand des Hashwertes ihres Inhaltes ist zumindest in den USA als Softwarepatent geschützt. Der Inhaber verfolgt Programme und Firmen, die auf Basis dieses Systems die Suche von Dateien ermöglichen, einschließlich Firmen, die im Auftrag von RIAA oder MPA Anbieter von unlizenzierten Inhalten ermitteln wollen. ⓘ

Bei der Programmierung von Internet-Anwendungen werden Hashfunktionen zum Erzeugen von Session-IDs genutzt, indem unter Verwendung von wechselnden Zustandswerten (wie Zeit, IP-Adresse) ein Hashwert berechnet wird. ⓘ

Kryptologie

Kryptographische Hashfunktionen besitzen spezielle Eigenschaften, in der Praxis sind es kollisionsresistente Einwegfunktionen. Sie werden verwendet, um Nachrichten zu signieren bzw. die Integrität von Daten sicherzustellen. Zum Hashen von Passwörtern, mit dem Ziel, sie sicher zu speichern oder daraus Schlüssel zu gewinnen, werden spezielle Hashfunktionen verwendet (z. B. aus der Klasse der "sicheren Hashalgorithmen"). Diese sind im Idealfall besonders aufwändig zu berechnen, um Brute-Force-Angriffe zu erschweren. Weiterhin müssen sie insbesondere den Eigenschaften der Konfusion und Unumkehrbarkeit genügen, damit das Klartextpasswort bzw. eine Menge von Kandidaten nicht ohne weiteres aus dem Schlüsselwert generierbar ist. ⓘ

Hash-Algorithmen

In der Praxis können oft heuristische Techniken anwendet werden, um eine gute Hashfunktion zu erstellen. Qualitative Informationen über die Verteilung der Schlüssel können in diesem Entwurfsprozess nützlich sein. Generell sollte eine Hashfunktion von jedem einzelnen Bit des Schlüssels abhängen, so dass sich zwei Schlüssel, die sich nur in einem Bit oder einer Bitfolge unterscheiden, unabhängig davon, ob die Folge am Anfang, am Ende oder in der Mitte des Schlüssels oder vorhanden ist, den gesamten Schlüssel-Hash auf verschiedene Werte abbildet. Daher ist eine Hashfunktion, die einfach einen Teil eines Schlüssels extrahiert, nicht geeignet. Wenn zwei Schlüssel einfach Permutationen voneinander sind, z. B. 256 und 625, sollten sie ebenfalls in unterschiedliche Werte gehasht werden. ⓘ

Heuristischen Methoden sind Hashing durch Division und Hashing durch Multiplikation. ⓘ

Hashing durch Division

Bei dieser Methode wird ein Schlüssel einem Hashwert zugeordnet, indem der Rest des Schlüssels bei Division durch die Größe der Hashtabelle berechnet wird. Das heißt, die Hashfunktion $h$ ist definiert als

$h(\mathrm {key} )=\mathrm {key} \ \mathrm {mod} \ \mathrm {tablesize}$

Weil nur eine einzige Divisionsoperation erforderlich ist, ist das Hashing durch Division ziemlich schnell. Wenn die Divisionsmethode verwendet wird, sollten bestimmte Werte für die Größe der Hashtabelle vermieden werden. Sie sollte keine Potenz einer Zahl sein. Wenn $\mathrm {tablesize} =r^{p}$ ist, dann ist der Hashwert $h(\mathrm {key} )$ immer gleich den letzten Bits von $\mathrm {key}$. Wenn wir nicht wissen, dass alle $p$-Bit-Muster niedriger Ordnung gleich wahrscheinlich sind, ist es besser, die Hashfunktion so zu gestalten, dass sie von allen Bits des Schlüssels abhängt. Es hat sich gezeigt, dass die besten Ergebnisse mit der Divisionsmethode erzielt werden, wenn die Größe der Hashtabelle eine Primzahl ist. Eine Primzahl, die nicht zu nah bei einer Zweierpotenz liegt, ist oft eine gute Wahl für die Größe der Hashtabelle. ⓘ

Hashing durch Multiplikation

Bei dieser Methode wird der Schlüssel $k$ mit einer konstanten reellen Zahl $c$ im Bereich $0<c<1$ multipliziert und die Nachkommastellen von $k\cdot c$ genommen. Dann wird dieser Wert mit der Größe der Hashtabelle multipliziert und mithilfe der Abrundungsfunktion der ganzzahlige Teil davon berechnet. Die Hashfunktion $h$ kann dargestellt werden als

$h(\mathrm {key} )=\mathrm {floor} (\mathrm {tablesize} \cdot (\mathrm {key} \cdot c\ \mathrm {mod} \ 1))$

Ein Vorteil besteht darin, dass die Größe der Hashtabelle nicht kritisch ist. Sie ist typischerweise eine Zweierpotenz, weil die Hashfunktion dann schneller implementiert werden kann. Obwohl diese Methode mit jeder reellen Zahl $c$ funktioniert, funktioniert sie mit einigen Werten besser als mit anderen. ⓘ

Bekannte Hashfunktionen

Bekannte Hashfunktionen sind zum Beispiel

• Brent-Hashing
• Divisions-Rest-Methode
• Doppel-Hashing
• Kuckucks-Hashing
• Multiplikative Methode
• Mittquadratmethode
• Zerlegungsmethode
• Ziffernanalyse ⓘ

Gitterbasierte Hashfunktionen

• Ajtai
• Micciancio
• Peikert-Rosen
• Schnelle Fourier-Transformation (FFT-Hashfunktion)
• LASH ⓘ

Prüfsummen

• Fletcher’s Checksum
• Adler-32
• CRC (Zyklische Redundanzprüfung)
• Parität
• Quersumme ⓘ

Kryptographische Hashfunktionen

• MD2, MD4, MD5
• Secure Hash Algorithm (SHA)
• RIPEMD-160
• Tiger
• HAVAL
• Whirlpool ⓘ

Nicht-kryptographische Hashfunktionen

Hashfunktion	Geschwindigkeit	Entwickler	Jahr ⓘ
xxHash	5,40 GB/s	Yann Collet	2012
MurmurHash 3a	2,70 GB/s	Austin Appleby	2008
SBox	1,40 GB/s	Bret Mulvey	2007
Lookup3	1,20 GB/s	Bob Jenkins	2006
CityHash64	1,05 GB/s	Geoff Pike & Jyrki Alakuijala	2011
FNV	0,55 GB/s	Fowler, Noll, Vo	1991
SipHash/HighwayHash		Jan Wassenberg & Jyrki Alakuijala	2016 / 2012

Passwort-Hashfunktionen

• LM-Hash
• PBKDF2
• Bcrypt
• Scrypt
• Argon2 ⓘ