Eine Kuddelmuddel-Funktion ist jeder Algorithmus oder Unterprogramm, das große Dateien der variablen Länge, genannt Schlüssel zu kleineren Dateien einer festen Länge kartografisch darstellt. Zum Beispiel konnte ein Name einer Person, eine variable Länge habend, hashed zu einer einzelnen ganzen Zahl sein. Die durch eine Kuddelmuddel-Funktion zurückgegebenen Werte werden Kuddelmuddel-Werte, Kuddelmuddel-Codes, Kuddelmuddel-Summen, Kontrollsummen oder einfach Kuddelmuddel genannt.

Beschreibungen

Kuddelmuddel-Funktionen werden größtenteils verwendet, um Tisch lookup oder Datenvergleich-Aufgaben wie Entdeckung von Sachen in einer Datenbank, das Ermitteln kopierter oder ähnlicher Aufzeichnungen in einer großen Datei, Entdeckung ähnlichen Streckens in DNA-Folgen und so weiter zu beschleunigen.

Eine Kuddelmuddel-Funktion, sollte d. h., wenn genannt, zweimal auf dem Eingang Verweisungs-durchsichtig sein, der "gleich" ist (zum Beispiel, Schnuren, die aus derselben Folge von Charakteren bestehen), es sollte dasselbe Ergebnis geben. Das ist ein Vertrag auf vielen Programmiersprachen, die dem Benutzer erlauben, Gleichheit und Kuddelmuddel-Funktionen für einen Gegenstand zu überreiten: Wenn zwei Gegenstände gleich sind, müssen ihre Kuddelmuddel-Codes dasselbe sein. Das ist für die Entdeckung eines Elements in einer Hash-Tabelle schnell entscheidend, weil zwei desselben Elements beides Kuddelmuddel zu demselben Ablagefach würden.

Einige Kuddelmuddel-Funktionen können zwei oder mehr Schlüssel zu demselben Kuddelmuddel-Wert kartografisch darstellen, eine Kollision verursachend. Solche Kuddelmuddel-Funktionen versuchen, die Schlüssel zu den Kuddelmuddel-Werten so gleichmäßig kartografisch darzustellen, wie möglich, weil Kollisionen häufiger werden, weil sich Hash-Tabellen füllen. So werden einzeln-stellige Kuddelmuddel-Werte oft auf 80 % der Größe des Tisches eingeschränkt. Abhängig vom verwendeten Algorithmus können andere Eigenschaften ebenso, wie doppelter hashing und geradlinige Untersuchung erforderlich sein. Obwohl die Idee in den 1950er Jahren konzipiert wurde, ist das Design von guten Kuddelmuddel-Funktionen noch ein Thema der aktiven Forschung.

Kuddelmuddel-Funktionen sind mit (und häufig verwirrt mit) Kontrollsummen, Prüfziffern, Fingerabdrücke, randomization Funktionen, Fehler verbunden, der Codes und kryptografische Kuddelmuddel-Funktionen korrigiert. Obwohl diese Konzepte einigermaßen überlappen, hat jeder seinen eigenen Nutzen und Voraussetzungen und wird entworfen und verschieden optimiert. Die Datenbank von HashKeeper, die durch das amerikanische Nationale Rauschgift-Nachrichtendienstzentrum zum Beispiel aufrechterhalten ist, wird als ein Katalog von Dateifingerabdrücken passender beschrieben als Kuddelmuddel-Werte.

Hash-Tabellen

Kuddelmuddel-Funktionen werden in erster Linie in Hash-Tabellen verwendet, um eine Datenaufzeichnung (zum Beispiel, eine Wörterbuch-Definition) gegeben sein Suchschlüssel (das Stichwort) schnell ausfindig zu machen. Spezifisch wird die Kuddelmuddel-Funktion verwendet, um den Suchschlüssel zum Kuddelmuddel kartografisch darzustellen. Der Index gibt den Platz, wo die entsprechende Aufzeichnung versorgt werden sollte. Hash-Tabellen werden abwechselnd verwendet, um assoziative Reihe und dynamische Sätze durchzuführen.

Im Allgemeinen kann eine Hashing-Funktion mehrere verschiedene Schlüssel zu demselben Index kartografisch darstellen. Deshalb wird jedes Ablagefach einer Hash-Tabelle mit (implizit oder ausführlich) eine Reihe von Aufzeichnungen, aber nicht eine einzelne Aufzeichnung vereinigt. Deshalb wird jedes Ablagefach einer Hash-Tabelle häufig einen Eimer genannt, und Kuddelmuddel-Werte werden auch Eimer-Indizes genannt.

So deutet die Kuddelmuddel-Funktion nur von der Position der Aufzeichnung an - es erzählt, wo man anfangen sollte, danach zu suchen. Und doch, in einem halb vollen Tisch wird eine gute Kuddelmuddel-Funktion normalerweise die Suche auf nur einen oder zwei Einträge beschränken.

Geheime Lager

Kuddelmuddel-Funktionen werden auch verwendet, um geheime Lager für große in langsamen Medien versorgte Dateien zu bauen. Ein geheimes Lager ist allgemein einfacher als ein Hashed-Suchtisch, da jede Kollision durch die Verschrottung oder das Zurückschreiben die älteren von den zwei kollidierenden Sachen aufgelöst werden kann.

Das wird auch im Dateivergleich verwendet.

Blüte-Filter

Kuddelmuddel-Funktionen sind eine wesentliche Zutat des Blüte-Filters, eine Kompaktdatenstruktur, die eine Umgeben-Annäherung an eine Reihe sie zur Verfügung stellt.

Entdeckung von Doppelaufzeichnungen

Wenn

man Aufzeichnungen in einer großen unsortierten Datei versorgt, kann man eine Kuddelmuddel-Funktion verwenden, jede Aufzeichnung zu einem Index in eine Tabelle T kartografisch darzustellen, und sich in jedem Eimer T [ich] zu versammeln, eine Liste der Zahlen aller Aufzeichnungen mit demselben Kuddelmuddel schätzt i. Sobald der Tisch abgeschlossen ist, werden irgendwelche zwei Doppelaufzeichnungen in demselben Eimer enden. Die Duplikate können dann durch die Abtastung jedes Eimers T [ich] gefunden werden, der zwei oder mehr Mitglieder enthalte, jene Aufzeichnungen herbeiholend, und sie vergleichend. Mit einem Tisch der passenden Größe wird diese Methode wahrscheinlich viel schneller sein als jede alternative Annäherung (wie das Sortieren der Datei und Vergleichen aller Konsekutivpaare).

Entdeckung ähnlicher Aufzeichnungen

Kuddelmuddel-Funktionen können auch verwendet werden, um Tabellenaufzeichnungen ausfindig zu machen, deren Schlüssel ähnlich, aber zu einem gegebenen Schlüssel nicht identisch ist; oder Paare von Aufzeichnungen in einer großen Datei, die ähnliche Schlüssel haben. Zu diesem Zweck braucht man eine Kuddelmuddel-Funktion, die ähnliche Schlüssel zu Kuddelmuddel-Werten kartografisch darstellt, die sich durch am grössten Teil der M unterscheiden, wo M eine kleine ganze Zahl ist (sagen Sie 1 oder 2). Wenn man eine Tabelle T aller Aktennummern mit solch einer Kuddelmuddel-Funktion baut, dann werden ähnliche Aufzeichnungen in demselben Eimer, oder in nahe gelegenen Eimern enden. Dann überprüft ein Bedürfnis nur die Aufzeichnungen in jedem Eimer T [ich] gegen diejenigen in Eimern T [i+k], wo sich k zwischen-m und M erstreckt.

Diese Klasse schließt die so genannten akustischen Fingerabdruck-Algorithmen ein, die verwendet werden, um ähnlich klingende Einträge in der großen Sammlung von Audiodateien ausfindig zu machen. Für diese Anwendung muss die Kuddelmuddel-Funktion so unempfindlich sein wie möglich gegen Datenfestnahme- oder Übertragungsfehler, und gegen "triviale" Änderungen wie Timing und Volumen-Änderungen, Kompression usw.

Entdeckung ähnlicher Teilketten

Dieselben Techniken können verwendet werden, um gleiches oder ähnliches Strecken in einer großen Sammlung von Schnuren, wie ein Dokumentenbehältnis oder eine genomic Datenbank zu finden. In diesem Fall werden die Eingangsschnuren in viele kleine Stücke gebrochen, und eine Kuddelmuddel-Funktion wird verwendet, um potenziell gleiche Stücke als oben zu entdecken.

Der Algorithmus von Rabin-Karp ist ein relativ schneller Schnur-Suche-Algorithmus, der in O (n) Zeit durchschnittlich arbeitet. Es basiert auf dem Gebrauch von hashing, um Schnuren zu vergleichen.

Geometrischer hashing

Dieser Grundsatz wird in der Computergrafik, rechenbetonter Geometrie und vielen anderen Disziplinen weit verwendet, um viele Nähe-Probleme im Flugzeug oder im dreidimensionalen Raum, wie Entdeckung nächster Paare in einer Reihe von Punkten, ähnlicher Gestalten in einer Liste von Gestalten, ähnlichen Images in einer Bilddatenbank und so weiter zu beheben. In diesen Anwendungen ist der Satz aller Eingänge eine Art metrischer Raum, und die Hashing-Funktion kann als eine Teilung dieses Raums in einen Bratrost von Zellen interpretiert werden. Der Tisch ist häufig eine Reihe mit zwei oder mehr Indizes (hat eine Bratrost-Datei, Bratrost-Index, Eimer-Bratrost und ähnliche Namen genannt), und die Kuddelmuddel-Funktion gibt ein Index-Tupel zurück. Dieser spezielle Fall von hashing ist als geometrischer hashing oder die Bratrost-Methode bekannt. Geometrischer hashing wird auch im Fernmeldewesen (gewöhnlich unter dem Namenvektoren quantization) verwendet, um mehrdimensionale Signale zu verschlüsseln und zusammenzupressen.

Eigenschaften

Gute Kuddelmuddel-Funktionen, im ursprünglichen Sinn des Begriffes, sind gewöhnlich erforderlich, bestimmte Eigenschaften zu befriedigen, die unten verzeichnet sind. Bemerken Sie, dass verschiedene Voraussetzungen für die anderen zusammenhängenden Konzepte (kryptografische Kuddelmuddel-Funktionen, Kontrollsummen, usw.) gelten.

Niedrig Kosten

Die Kosten, eine Kuddelmuddel-Funktion zu schätzen, müssen klein genug sein, um eine mit Sitz in hashing Lösung effizienter zu machen, als alternative Annäherungen. Zum Beispiel kann sich ein selbstbalancierender binärer Baum niederlassen ein Artikel in einem sortierten Tisch von n Sachen mit O (loggen Sie n) Schlüsselvergleiche. Deshalb wird eine Hash-Tabelle-Lösung effizienter sein als ein selbstbalancierender binärer Baum, wenn die Zahl von Sachen groß ist und die Kuddelmuddel-Funktion wenige Kollisionen und weniger effizient erzeugt, wenn die Zahl von Sachen klein ist und die Kuddelmuddel-Funktion kompliziert ist.

Determinismus

Ein Kuddelmuddel-Verfahren muss deterministische Bedeutung sein, die für einen gegebenen Wert eingegeben hat, muss es immer denselben Kuddelmuddel-Wert erzeugen. Mit anderen Worten muss es eine Funktion der hashed Daten in der mathematischen Bedeutung des Terminus sein. Diese Voraussetzung schließt Kuddelmuddel-Funktionen aus, die von variablen Außenrahmen, wie pseudozufällige Zahlengeneratoren oder die Zeit des Tages abhängen. Es schließt auch Funktionen aus, die von der Speicheradresse des Gegenstands abhängen, der hashed ist, weil sich diese Adresse während der Ausführung ändern kann (wie auf Systeme stoßen kann, die bestimmte Methoden der Müll-Sammlung verwenden), obwohl manchmal die erneute Verhandlung des Artikels möglich ist.

Gleichförmigkeit

Eine gute Kuddelmuddel-Funktion sollte die erwarteten Eingänge so gleichmäßig kartografisch darstellen wie möglich über seine Produktionsreihe. D. h. jeder Kuddelmuddel-Wert in der Produktionsreihe sollte mit grob derselben Wahrscheinlichkeit erzeugt werden. Der Grund für diese letzte Voraussetzung besteht darin, dass die Kosten von mit Sitz in hashing Methoden scharf als die Zahl von Kollisionspaaren von Eingängen steigen, die zu denselben Kuddelmuddel-Wertzunahmen kartografisch dargestellt werden. Grundsätzlich, wenn einige Kuddelmuddel-Werte mit größerer Wahrscheinlichkeit vorkommen werden, als andere ein größerer Bruchteil der lookup Operationen einen größeren Satz von kollidierenden Tabelleneinträgen wird durchsuchen müssen.

Bemerken Sie, dass dieses Kriterium nur verlangt, dass der Wert gleichförmig verteilt wird, in jedem Sinn nicht zufällig. Eine gute Randomizing-Funktion ist (das Abhalten rechenbetonter Leistungsfähigkeitssorgen) allgemein eine gute Wahl als eine Kuddelmuddel-Funktion, aber das gegenteilige braucht nicht wahr zu sein.

Hash-Tabellen enthalten häufig nur eine kleine Teilmenge der gültigen Eingänge. Zum Beispiel kann eine Klub-Mitgliedschaft-Liste nur ungefähr hundert Mitglied-Namen aus dem sehr großen Satz aller möglichen Namen enthalten. In diesen Fällen sollte das Gleichförmigkeitskriterium für fast alle typischen Teilmengen von Einträgen halten, die im Tisch nicht nur für den globalen Satz aller möglichen Einträge gefunden werden können.

Mit anderen Worten, wenn ein typischer Satz der M Aufzeichnungen hashed zu n Tabellenablagefächern, der Wahrscheinlichkeit eines Eimers ist, der noch viele erhält, als M/n-Aufzeichnungen klein sein vanishingly sollten. Insbesondere wenn M weniger ist als n, sollten sehr wenige Eimer mehr als eine oder zwei Aufzeichnungen haben. (In einer idealen "vollkommenen Kuddelmuddel-Funktion" sollte kein Eimer mehr als eine Aufzeichnung haben; aber eine kleine Anzahl von Kollisionen ist eigentlich unvermeidlich, selbst wenn n viel größer ist, als M - das Geburtstag-Paradox sieht).

Wenn

man eine Kuddelmuddel-Funktion prüft, kann die Gleichförmigkeit des Vertriebs von Kuddelmuddel-Werten durch den chi-karierten Test bewertet werden.

Variable Reihe

In vielen Anwendungen kann die Reihe von Kuddelmuddel-Werten für jeden Lauf des Programms verschieden sein, oder kann sich entlang demselben Lauf ändern (zum Beispiel, wenn eine Hash-Tabelle ausgebreitet werden muss). In jenen Situationen braucht man eine Kuddelmuddel-Funktion, die zwei Rahmen - die Eingangsdaten z und die Nummer n von erlaubten Kuddelmuddel-Werten nimmt.

Eine allgemeine Lösung ist zu rechnen eine feste Kuddelmuddel-Funktion mit einer sehr großen Reihe (sagen Sie 0 zu 2−1), teilen Sie das Ergebnis durch n, und verwenden Sie den Rest der Abteilung. Wenn n selbst eine Macht 2 ist, kann das durch die Bit-Maskierung und Bit-Verschiebung getan werden. Wenn diese Annäherung verwendet wird, muss die Kuddelmuddel-Funktion gewählt werden, so dass das Ergebnis ziemlich Rechteckverteilung zwischen 0 und n−1 für jeden n hat, der in der Anwendung vorkommen kann. Abhängig von der Funktion kann der Rest nur für bestimmten n, z.B ungerade Zahlen oder Primzahlen gleichförmig sein.

Wir können der Tabellengröße n erlauben, eine Macht 2 nicht zu sein und noch immer nicht zu haben, um jeden Rest oder Abteilungsoperation durchzuführen, weil diese Berechnung manchmal kostspielig ist. Lassen Sie zum Beispiel n bedeutsam weniger als 2 sein. Denken Sie eine Funktion des Pseudozufallszahlengenerators (PRNG) P (Schlüssel), der auf dem Zwischenraum [0, 2−1] gleichförmig ist. Denken Sie die Kuddelmuddel-Funktion n P (Schlüssel) / 2. Wir können die Abteilung durch (vielleicht schneller) richtige Bit-Verschiebung ersetzen: n P (Schlüssel)>> b.

Variable Reihe mit der minimalen Bewegung (dynamische Kuddelmuddel-Funktion)

Wenn die Kuddelmuddel-Funktion verwendet wird, um Werte in einer Hash-Tabelle zu versorgen, die den Lauf des Programms überlebt, und die Hash-Tabelle ausgebreitet oder zusammenschrumpfen gelassen werden muss, wird die Hash-Tabelle eine dynamische Hash-Tabelle genannt.

Eine Kuddelmuddel-Funktion, die die minimale Zahl von Aufzeichnungen umsiedeln wird, wenn der Tisch in der Größe angepasst wird, ist wünschenswert.

Was erforderlich ist, ist eine Kuddelmuddel-Funktion H (z, n) - wo z der Schlüssel ist, der hashed ist, und n die Zahl von erlaubten Kuddelmuddel-Werten - solch dass H (z, n+1) = H (z, n) mit der Wahrscheinlichkeit in der Nähe von n / (n+1) ist.

Geradliniger hashing und spiralförmige Lagerung sind Beispiele von dynamischen Kuddelmuddel-Funktionen, die in der unveränderlichen Zeit durchführen, aber das Eigentum der Gleichförmigkeit entspannen, das minimale Bewegungseigentum zu erreichen.

Ausdehnbarer hashing verwendet eine dynamische Kuddelmuddel-Funktion, die verlangt, dass zu n proportionaler Raum die Kuddelmuddel-Funktion schätzt, und es eine Funktion der vorherigen Schlüssel wird, die eingefügt worden sind.

Mehrere Algorithmen, die das Gleichförmigkeitseigentum bewahren, aber verlangen, dass zu n proportionale Zeit den Wert von H schätzt (z, n) sind erfunden worden.

Datennormalisierung

In einigen Anwendungen können die Eingangsdaten Eigenschaften enthalten, die zum Vergleich Zwecke irrelevant sind. Zum Beispiel, wenn man einen Vornamen nachschlägt, kann es wünschenswert sein, die Unterscheidung zwischen Briefen der Groß- und Kleinschreibung zu ignorieren. Für solche Daten muss man eine Kuddelmuddel-Funktion verwenden, die mit dem Datengleichwertigkeitskriterium vereinbar ist, das wird verwendet: D. h. irgendwelche zwei Eingänge, die gleichwertig betrachtet werden, müssen denselben Kuddelmuddel-Wert nachgeben. Das kann durch das Normalisieren des Eingangs vorher hashing es, als durch die obere Umkleidung alle Briefe vollbracht werden.

Kontinuität

Eine Kuddelmuddel-Funktion, die verwendet wird, um ähnlich (im Vergleich mit der Entsprechung) Daten zu suchen, muss so dauernd sein wie möglich; zwei Eingänge, die sich durch etwas unterscheiden, sollten zu gleichen oder fast gleichen Kuddelmuddel-Werten kartografisch dargestellt werden.

Bemerken Sie, dass Kontinuität gewöhnlich als ein tödlicher Fehler für Kontrollsummen, kryptografische Kuddelmuddel-Funktionen und andere zusammenhängende Konzepte betrachtet wird. Kontinuität ist für Kuddelmuddel-Funktionen nur in einigen Anwendungen wie Hash-Tabellen wünschenswert, die geradlinige Suche verwenden.

Kuddelmuddel-Funktionsalgorithmen

Für die meisten Typen von Hashing-Funktionen hängt die Wahl der Funktion stark von der Natur der Eingangsdaten und ihrem Wahrscheinlichkeitsvertrieb in der beabsichtigten Anwendung ab.

Triviale Kuddelmuddel-Funktion

Wenn die Gegebenheit, um hashed zu sein, klein genug ist, kann man die Gegebenheit selbst (wiederinterpretiert als eine ganze Zahl in der binären Notation) als der Hashed-Wert verwenden. Die Kosten, diesen "trivialen" (Identität) Kuddelmuddel-Funktion zu schätzen, sind effektiv Null-. Diese Kuddelmuddel-Funktion ist vollkommen, weil sie jeden Eingang zu einem verschiedenen Kuddelmuddel-Wert kartografisch darstellt.

Die Bedeutung "kleinen genug" hängt von der Größe des Typs ab, der als der Hashed-Wert verwendet wird. Zum Beispiel, in Java, ist der Kuddelmuddel-Code eine ganze 32-Bit-Zahl. So können die ganze 32-Bit-Zahl und 32-Bit-Schwimmpunkt-Gegenstände einfach den Wert direkt verwenden; wohingegen die ganze 64-Bit-Zahl und der 64-Bit-Schwimmpunkt diese Methode nicht verwenden können.

Andere Typen von Daten können auch dieses vollkommene hashing Schema verwenden. Zum Beispiel, wenn man Charakter-Schnuren zwischen der Groß- und Kleinschreibung kartografisch darstellt, kann man die binäre Verschlüsselung jedes Charakters verwenden, der als eine ganze Zahl interpretiert ist, um einen Tisch mit einem Inhaltsverzeichnis zu versehen, der die alternative Form dieses Charakters ("A" für "a", "8" für "8", usw.) gibt. Wenn jeder Charakter in 8 Bit versorgt wird (als in ASCII oder ISO lateinischem 1), hat der Tisch nur 2 = 256 Einträge; im Fall von Charakteren von Unicode würde der Tisch 17×2 = 1114112 Einträge haben.

Dieselbe Technik kann verwendet werden, um zweistellige internationale Vorwahlen wie "wir" oder "za" zu Landesnamen (26=676 Tabelleneinträge), 5-stellige Postleitzahlen wie 13083 zu Stadtnamen kartografisch darzustellen (100000 Einträge), usw. können Ungültige Datenwerte (wie die internationale Vorwahl "xx" oder die Postleitzahl 00000) unbestimmt im Tisch verlassen werden, oder haben zu einem passenden "ungültigen" Wert kartografisch dargestellt.

Vollkommener hashing

Wie man

sagt, ist eine Kuddelmuddel-Funktion, die injective-d.-h. Karten jeder gültige Eingang zu einem verschiedenen Kuddelmuddel-Wert ist - vollkommen. Mit solch einer Funktion kann man den gewünschten Zugang in einer Hash-Tabelle ohne jede zusätzliche Suche direkt ausfindig machen.

Minimaler vollkommener hashing

Wie man

sagt, ist eine vollkommene Kuddelmuddel-Funktion für n Schlüssel minimal, wenn seine Reihe aus n aufeinander folgenden ganzen Zahlen, gewöhnlich von 0 bis n1 besteht. Außer der Versorgung von Einzelschrittlookup gibt eine minimale vollkommene Kuddelmuddel-Funktion auch eine Kompakthash-Tabelle ohne irgendwelche freien Ablagefächer nach. Minimale vollkommene Kuddelmuddel-Funktionen sind viel härter zu finden als vollkommene mit einer breiteren Reihe.

Hashing hat gleichförmig Daten verteilt

Wenn die Eingänge Schnuren der begrenzten Länge (wie Telefonnummern, Autonummernschilder, Rechnungsnummern, usw.) sind, und jeder Eingang mit der gleichförmigen Wahrscheinlichkeit unabhängig vorkommen kann, dann muss eine Kuddelmuddel-Funktion nur grob dieselbe Zahl von Eingängen zu jedem Kuddelmuddel-Wert kartografisch darstellen. Nehmen Sie zum Beispiel an, dass jeder Eingang eine ganze Zahl z in der Reihe 0 zu N1 ist, und die Produktion eine ganze Zahl h in der Reihe 0 zu n1 sein muss, wo N viel größer ist als n. Dann konnte die Kuddelmuddel-Funktion h = z mod n (der Rest von z sein, der durch n geteilt ist) oder h = (z × n) ÷ N (der Wert z, heruntergeschraubt durch n/N und gestutzt zu einer ganzen Zahl), oder viele andere Formeln.

Warnung: h = z mod wurde n in vielen der ursprünglichen Zufallszahlengeneratoren verwendet, aber wurde gefunden, mehrere Probleme zu haben. Von denen einer ist, dass weil sich n N nähert, diese Funktion wird immer weniger gleichförmig.

Daten von Hashing mit anderem Vertrieb

Diese einfachen Formeln werden nicht tun, wenn die Eingangswerte nicht ebenso wahrscheinlich sind, oder ziemlich abhängig sind. Zum Beispiel werden die meisten Schutzherren eines Supermarkts in demselben geografischen Gebiet leben, so werden ihre Telefonnummern wahrscheinlich mit denselben 3 bis 4 Ziffern beginnen. In diesem Fall, wenn n 10000 oder so, die Abteilungsformel (z × n) ÷ N ist, der hauptsächlich von den Hauptziffern abhängt, wird viele Kollisionen erzeugen; wohingegen die Rest-Formel z mod n, der zu den schleifenden Ziffern ziemlich empfindlich ist, noch einen ziemlich gleichen Vertrieb nachgeben kann.

Daten der variablen Länge von Hashing

Wenn die Datenwerte (oder variable Länge) Charakter-Schnuren - wie Vornamen, Webseite-Adressen oder Postnachrichten lang sind - ist ihr Vertrieb gewöhnlich mit komplizierten Abhängigkeiten sehr uneben. Zum Beispiel hat der Text in jeder natürlichen Sprache hoch ungleichförmigen Vertrieb von Charakteren und Charakter-Paare, die für die Sprache sehr charakteristisch sind. Für solche Daten ist es vernünftig, eine Kuddelmuddel-Funktion zu verwenden, die von allen Charakteren der Schnur abhängt - und von jedem Charakter auf eine verschiedene Weise abhängt.

In kryptografischen Kuddelmuddel-Funktionen wird ein Merkle-Damgård Aufbau gewöhnlich verwendet. Im Allgemeinen soll das Schema für hashing solche Daten den Eingang in eine Folge von kleinen Einheiten (Bit, Bytes, Wörter, usw.) brechen und alle Einheiten b [1], b [2]..., b [M] folgend, wie folgt verbinden

S  S0;//Initialisieren den Staat.

für k in 1, 2..., tut M//Ansehen die Eingangsdateneinheiten:

S  F (S, b [k]);//Vereinigungsdateneinheit k in den Staat.

geben Sie G zurück (S, n)//Ziehen den Kuddelmuddel-Wert aus dem Staat Heraus. </code>

Dieses Diagramm wird auch in vielen Textkontrollsumme und Fingerabdruck-Algorithmen verwendet. Die Zustandsgröße S kann ein 32- oder nicht unterzeichnete ganze 64-Bit-Zahl sein; in diesem Fall kann S0 0 sein, und G (S, n) kann gerade S mod n sein. Die beste Wahl von F ist ein kompliziertes Problem und hängt von der Natur der Daten ab. Wenn die Einheiten b [k] einzelne Bit sind, dann konnte F (S, b), zum Beispiel sein

wenn highbit (S) = 0 dann

kehren Sie 2 * S + b zurück

sonst

kehren Sie (2 * S + b) ^ P </Code> zurück

Hier zeigt highbit (S) das bedeutendste Bit von S an; der '' Maschinenbediener zeigt nicht unterzeichnete Multiplikation der ganzen Zahl mit der verlorenen Überschwemmung an; '' ist das bitwise exklusive oder die auf Wörter angewandte Operation; und P ist ein passendes festes Wort.

Kuddelmuddel-Funktionen des speziellen Zwecks

In vielen Fällen kann man einen speziellen Zweck (heuristische) Kuddelmuddel-Funktion entwerfen, die viele weniger Kollisionen nachgibt als eine gute Mehrzweckkuddelmuddel-Funktion. Nehmen Sie zum Beispiel an, dass die Eingangsdaten Dateinamen solcher als usw. mit größtenteils folgenden Zahlen sind. Für solche Daten würde eine Funktion, die den numerischen Teil k des Dateinamens herauszieht und k mod n zurückgibt, fast optimal sein. Selbstverständlich kann eine Funktion, die für eine spezifische Art von Daten außergewöhnlich gut ist, düstere Leistung auf Daten mit dem verschiedenen Vertrieb haben.

Das Rollen des Kuddelmuddels

In einigen Anwendungen, wie Teilkette-Suche, muss man rechnen eine Kuddelmuddel-Funktion h für jede k-character Teilkette eines gegebenen n-character spannen t; wo k eine feste ganze Zahl ist, und n k ist. Die aufrichtige Lösung, die ist, jede solche Teilkette s t herauszuziehen und h (s) getrennt zu schätzen, verlangt mehrere zu k proportionale Operationen · n. Jedoch, mit der richtigen Wahl von h, kann man die Technik des rollenden Kuddelmuddels verwenden, um ganzes jenes Kuddelmuddel mit einer zu k+n proportionalen Anstrengung zu schätzen.

Universaler hashing

Ein universales hashing Schema ist ein randomized Algorithmus, der eine Hashing-Funktion h unter einer Familie solcher Funktionen auf solche Art und Weise auswählt, dass die Wahrscheinlichkeit einer Kollision irgendwelcher zwei verschiedenen Schlüssel 1/n ist, wo n die Zahl von verschiedenen Kuddelmuddel-Werten gewünscht — unabhängig von den zwei Schlüsseln ist. Universaler hashing sichert (in einem probabilistic Sinn), dass sich die Kuddelmuddel-Funktionsanwendung benehmen wird, sowie wenn es eine zufällige Funktion für einen Vertrieb der Eingangsdaten verwendete. Es wird jedoch mehr Kollisionen haben als vollkommener hashing, und kann mehr Operationen verlangen als eine Kuddelmuddel-Funktion des speziellen Zwecks.

Hashing mit Kontrollsumme-Funktionen

Man kann bestimmte Kontrollsumme oder Fingerabdruck-Algorithmen für den Gebrauch als Kuddelmuddel-Funktionen anpassen. Einige jener Algorithmen werden willkürliche lange Schnur-Daten z mit jedem typischen wirklichen Vertrieb kartografisch darstellen - egal wie ungleichförmig und abhängig - zu einer 32-bit- oder 64-Bit-Schnur, aus der einen Kuddelmuddel-Wert in 0 durch n1 herausziehen kann.

Diese Methode kann genug Rechteckverteilung von Kuddelmuddel-Werten erzeugen, so lange die Kuddelmuddel-Reihe-Größe n im Vergleich zur Reihe der Kontrollsumme oder Fingerabdruck-Funktion klein ist. Jedoch, ein Kontrollsumme-Fahrgeld schlecht im Lawine-Test, der eine Sorge in einigen Anwendungen sein kann. Insbesondere die populäre CRC32 Kontrollsumme stellt nur 16 Bit zur Verfügung (die höhere Hälfte des Ergebnisses), die für hashing verwendbar sind. Außerdem hat jedes Bit des Eingangs eine deterministische Wirkung auf jedes Bit des CRC32, der ist, kann man erzählen, ohne auf den Rest des Eingangs zu schauen, den Bit der Produktion schnipsen werden, wenn der Eingang gebissen hat, wird geschnipst; so muss Sorge gebracht werden, um alle 32 Bit zu verwenden, wenn man das Kuddelmuddel von der Kontrollsumme schätzt.

Hashing mit kryptografischen Kuddelmuddel-Funktionen

Einige kryptografische Kuddelmuddel-Funktionen, wie SHA-1, haben noch stärkere Gleichförmigkeitsgarantien als Kontrollsummen oder Fingerabdrücke, und können so sehr gute Mehrzweckhashing-Funktionen zur Verfügung stellen.

In gewöhnlichen Anwendungen kann dieser Vorteil zu klein sein, um ihre viel höher Kosten auszugleichen. Jedoch kann diese Methode gleichförmig verteiltes Kuddelmuddel zur Verfügung stellen, selbst wenn die Schlüssel von einem böswilligen Agenten gewählt werden. Diese Eigenschaft kann helfen, Dienstleistungen gegen die Leugnung von Dienstangriffen zu schützen.

Ursprünge des Begriffes

Der Begriff "Kuddelmuddel" kommt über die Analogie mit seiner nicht technischen Bedeutung, um "zu hacken und sich zu vermischen". Tatsächlich "hacken" typische Kuddelmuddel-Funktionen, wie die mod Operation, das Eingangsgebiet in viele Subgebiete, die in die Produktionsreihe "gemischt" werden, um die Gleichförmigkeit des Schlüsselvertriebs zu verbessern.

Donald Knuth bemerkt, dass Hans Peter Luhn von IBM scheint, erst gewesen zu sein, um das Konzept im datierten Januar 1953 eines Merkzettels zu verwenden, und dass Robert Morris den Begriff in einer Überblick-Zeitung in CACM gebraucht hat, der den Begriff vom technischen Jargon bis formelle Fachsprache erhoben hat.

Liste von Kuddelmuddel-Funktionen

• Kuddelmuddel von Bernstein
• Fowler-Noll-Vo-Kuddelmuddel-Funktion (32, 64, 128, 256, 512, oder 1024 Bit)
• Kuddelmuddel-Funktion von Jenkins (32 Bit)
• Pearson hashing (8 Bit)
• Zobrist hashing

Siehe auch

• Blüte-Filter
• Verschmelzter hashing
• Kuckuck hashing
• Kryptografische Kuddelmuddel-Funktion
• Verteilte Hash-Tabelle
• Geometrischer hashing
• Hash-Tabelle
• HMAC
• Identicon
• Geradliniges Kuddelmuddel
• Die Liste des Kuddelmuddels fungiert
• Gegend empfindlicher hashing
• MD5
• Vollkommene Kuddelmuddel-Funktion
• Schnur von Rabin-Karp sucht Algorithmus
• Das Rollen des Kuddelmuddels
• Umstellungstisch
• Universaler hashing

Links

• Allgemeine Zweck-Kuddelmuddel-Funktionsalgorithmen (C/C ++/Pascal/Java/Python/Ruby)
• Kuddelmuddel-Funktionen und Block-Ziffern durch Bob Jenkins
• Die Funktion der Goulburn Hashing (PDF) durch Mayur Patel
• Die Einführung von MIT in Algorithmen: Hashing 1 MIT OCW halten Video Vorlesungen
• Die Einführung von MIT in Algorithmen: Hashing 2 MIT OCW halten Video Vorlesungen
• Kuddelmuddel Fuction Aufbau für die Textliche und Geometrische Datenwiederauffindung Letzte Tendenzen auf Computern, Vol.2, Seiten 483-489, CSCC Konferenz, Corfu, 2010