Warum heißt es "Hash-Tabelle" oder "Hash-Funktion"? Hash macht für mich hier keinen Sinn

26

Es sind nun ungefähr 4 Jahre Entwicklung, in denen ich Hash-Tabellen und Hash-Funktionen verwende, höre, darüber spreche und implementiere. Aber ich verstehe wirklich nie, warum es Haschisch heißt?

Ich erinnere mich an die ersten Tage, an denen ich mit dem Programmieren angefangen habe. Dieser Begriff war für mich etwas umständlich . Ich habe nie herausgefunden, was es ist, basierend auf seinem Namen . Ich habe nur experimentell verstanden, was es macht und warum und wann wir es verwenden sollten .

Trotzdem versuche ich manchmal herauszufinden, warum es Hash heißt . Ich habe kein Problem mit Tabelle oder Funktion und um ehrlich zu sein, sie sind ziemlich deduktiv, rationale Begriffe. Ich denke jedoch, dass bessere Wörter anstelle von Hash, wie Schlüssel oder Eindeutigkeit , verwendet werden könnten . Keine Schlüsseltabelle oder Eindeutigkeitstabelle .

Nach meinem Wörterbuch bedeutet Hash:

  1. Gebratenes Gericht aus Kartoffeln und Fleisch (höchst irrelevant)
  2. # -Zeichen (AKA-Nummernzeichen, Nummernzeichen usw.) (immer noch irrelevant, möglicherweise nur eine falsche Nomenklatur)
  3. Anwenden eines Algorithmus auf eine Zeichenfolge (hat immer noch nichts mit der Eindeutigkeit zu tun , die das wichtigste Merkmal einer Hash-Tabelle ist)
  4. Essen schneiden
  5. Ein anderer Begriff für Haschisch

Weiß jemand, warum es Hash heißt?

Saeed Neamati
quelle
32
Sie scheinen etwas falsch zu verstehen, was Hashes sind. Die Eindeutigkeit ist ausdrücklich kein Merkmal von Hash-Funktionen (dh sie sind niemals injektiv).
Peter Taylor
1
@ Peter Taylor: Hash-Tabellen definieren injektive Zuordnungen.
Reinierpost
2
@Peter Taylor: um ein bisschen pingelig zu sein, müssen sie nicht injektiv sein , aber manchmal sind sie sogar bijektiv. Denken Sie an die typische Implementierung einer Hash-Funktion für eine Ganzzahl :)
keppla
4
Ein Hash kann eindeutig sein, solange entweder der Schlüsselbereich nicht größer als der Hash-Wertebereich ist (für Tabellen-Hashes) oder der Hash-Wertebereich so groß ist, dass Kollisionen mathematisch nicht ausführbar sind (für kryptographische Hashes).
Sichern Sie sich den
1
Außerdem klingt eine "Schlüsseltabelle" eher wie eine "Schlüssel / Wert" -Datenstruktur (auch "Wörterbuch" genannt). Nicht alle Schlüssel- / Wertdatenstrukturen sind Hash-Tabellen.
Barjak

Antworten:

46

Laut Wikipedia bezieht es sich auf die Hash-Funktion . Wenn Sie noch einen Schritt weiter gehen möchten, heißt es auf der Wiki-Seite für die Hash-Funktion, dass die Verwendung des Wortes "Hash" in der Hash-Funktion folgendermaßen entstanden ist:

Der Begriff "Hash" bedeutet in Analogie zu seiner nichttechnischen Bedeutung "hacken und mischen". Tatsächlich "zerlegen" typische Hash-Funktionen wie die Mod-Operation die Eingabedomäne in viele Unterdomänen, die in den Ausgabebereich "gemischt" werden, um die Gleichmäßigkeit der Schlüsselverteilung zu verbessern.

user937146
quelle
2
Ich bin mir nicht sicher, was die "Sub-Domains" dort tun. Es ist nur so, dass die Hash-Funktion die Werte ihrer Domain gründlich „verwechselt“.
Reinierpost
15

Im Französischen heißt eine Hash-Tabelle "table de hachage", das verwandte Verb "hacher" bedeutet hacken / hacken (meistens Essen). Das Verb to hashhat im Englischen die gleiche Bedeutung.

Wie andere bereits betont haben, wird es Hash genannt, weil Sie Ihre Eingaben abhacken, die Sie an verschiedenen Stellen (Ihren Tabelleneinträgen) in Stücke setzen.

Xavier T.
quelle
2
Es ist eigentlich "hachage" und "hacher" ohne Akzent geschrieben.
14.
10

Nummer 3 hat alles damit zu tun. Aus Wikipedia :

Das Herzstück des Hash-Tabellen-Algorithmus ist ein einfaches Array von Elementen. Dies wird oft einfach als Hash-Tabelle bezeichnet . Hash-Tabellenalgorithmen berechnen einen Index aus dem Schlüssel des Datenelements und verwenden diesen Index, um die Daten in das Array einzufügen. Die Durchführung dieser Berechnung ist die Hash - Funktion , f:

index = f(key, arrayLength)

Die Hash-Funktion berechnet indexaus den Daten ein innerhalb des Arrays key. arrayLengthist die Größe des Arrays. Bei Assemblersprachen oder anderen einfachen Programmen kann eine einfache Hash-Funktion häufig einen Index mit nur ein oder zwei Inline- Maschinenanweisungen erstellen .

Eine Hash-Tabelle speichert also nicht wirklich Werte, die auf einem Schlüssel basieren. Es speichert Werte basierend auf einer gehashten Version dieses Schlüssels.

Michelle Tilley
quelle
1
es hängt davon ab, was Sie mit Hash-Tabelle meinen. Die Datenstruktur, wie sie in Sprachen wie Perl, Java und C # angeboten wird, bietet Ihnen eine Key-to-Value-Zuordnung unter Verwendung der Art von Hash-Tabelle, auf die Sie intern verweisen.
Reinierpost
10

Hash-Tabellen werden aufgrund der Verwendung so aufgerufen Hash-Code verwendet wird und dieser sich auf "Lebensmittel schneiden" bezieht.

Stellen Sie sich das so vor - Sie nehmen Ihr hübsches Objekt wie eine Frucht und hacken es, sodass es wie alles andere aussieht - nur eine Zahl - es enthält keine Struktur mehr. Dieses Stück "geschnittenes Essen" wird in der Hash-Tabelle verwendet, um Ihr schönes hübsches Objekt herauszufinden.

  • Sieht es hässlicher aus als dein hübsches Objekt? Vielleicht - aber es hilft, es schnell zu finden - das ist der Punkt. oh und es ist nicht eindeutig, das ist sicher.
     
    Hash-Code findet einen Bucket in der Tabelle, in dem sich Ihr hübsches Objekt in einer kleinen Firma mit demselben Hash-Code befindet. In diesem kleinen Unternehmen wird das Objekt mithilfe der Gleichheitsprüfung gesucht - was viel langsamer sein dürfte als die Hash-Suche, aber keine große Sache ist, da es nur wenige gibt (die meisten anderen Objekte werden dank schnellem Hash bereits ignoriert). .
Mücke
quelle
3

Beim Haschieren (wie beim Schneiden in kleine Stücke, Zerkleinern usw.) wird eine Eingabe (Lebensmittel oder manchmal Superschurken) in eine relativ homogene Ausgabe umgewandelt. Dh egal was du am Anfang hattest, am Ende hast du nur Haschisch. Und ein Löffel des Hashes ist ungefähr so ​​hilfreich wie der gesamte Hash, um festzustellen, was die Eingabe war (vorausgesetzt, Ihre Hashing-Maschine hasht gut).
Das Hashing kann also jedes essbare oder böse Objekt in einen Löffel Hash umwandeln, wobei zwei verschiedene Objekte unterschiedliche Hashes ergeben, während zwei gleiche Objekte gleiche Hashes ergeben. Das heißt, wenn zwei Superschurken in Ihre Hashing-Maschine gefallen sind, genügt es, ihre Hashes zu vergleichen, um festzustellen, ob einer ein Klon des anderen war.

In gewisser Weise ähneln sich die Hashing-Funktionen in der Informatik. Sie nehmen eine ganze Eingabe unterschiedlicher Größe und Semantik und - ganz einfach ausgedrückt - schneiden sie sie einfach in Stücke und mischen diese herum und schneiden die resultierende Sequenz zurück in Stücke und mischen diese herum und so weiter. Am Ende haben Sie einen Löffel (n Bytes) der Eingabe, die Sie gehasht haben.

back2dos
quelle
Mit der Einschränkung kann der Superschurke jedoch auch denselben Hash wie ein Superheld mit einem bestimmten Satz von Parametern zurückgeben, da Hashing nicht die Einzigartigkeit zu diktieren scheint. Immerhin gibt es Hash-Kollisionen ... es ist das, was Sie nach der Kollision tun ...
Rig