Was ist der Unterschied zwischen einem Hash und einem Wörterbuch?

46

Was ist der Unterschied zwischen Hashund Dictionary?

Ich habe das Gefühl, dass sie ähnlich sind, aber ich wollte die genauen Unterschiede herausfinden. Googeln hat mir nicht viel geholfen.

data-structures hashing dictionary difference hashtable Sairam
quelle

Antworten:

92

Hashist eine extrem schlecht benannte Datenstruktur, bei der der Programmierer die Schnittstelle mit der Implementierung verwechselt hat ( und zu faul war, um den vollständigen Namen zu schreiben, dh HashTablestattdessen auf eine Abkürzung zurückzugreifen Hash).

Dictionaryist der „richtige“ Name der Schnittstelle (= ADT ), dh ein assoziativer Container, der (normalerweise eindeutige) Schlüssel (nicht unbedingt eindeutigen) Werten zuordnet.

Eine Hash-Tabelle ist eine mögliche Implementierung eines solchen Wörterbuchs, das (in Bezug auf die Laufzeit) recht gute Zugriffseigenschaften bietet und daher häufig die Standardimplementierung ist.

Eine solche Implementierung hat zwei wichtige Eigenschaften:

  1. die Schlüssel sein müssen hashable und Gleichheit vergleichbar .
  2. Die Einträge erscheinen in keiner bestimmten Reihenfolge im Wörterbuch.

(Wenn ein Schlüssel hashbar sein soll, können wir einen numerischen Wert aus einem Schlüssel berechnen, der anschließend als Index in einem Array verwendet wird.)

Es gibt alternative Implementierungen der Wörterbuchdatenstruktur, die den Schlüsseln eine Reihenfolge auferlegen - dies wird häufig als sortiertes Wörterbuch bezeichnet (und wird normalerweise in Form eines Suchbaums implementiert, obwohl andere effiziente Implementierungen existieren).

Zusammenfassend lässt sich sagen, dass ein Wörterbuch ein ADT ist, das Schlüssel zu Werten zuordnet. Es gibt mehrere mögliche Implementierungen dieses ADT, von denen die Hash-Tabelle eine ist. Hashist eine Fehlbezeichnung, entspricht aber im Kontext einem Wörterbuch, das in Form einer Hash-Tabelle implementiert ist.

Konrad Rudolph
quelle
4
Um ein Beispiel in C ++ zu geben, konnten die assoziativen Standardcontainervorlagen nicht als Hashes implementiert werden, obwohl der nächste Standard tatsächlich Hashtabellen enthält. Sie sollen unordered_mapzeigen, was sie tun und nicht, was sie sind.
David Thornley
6
Nach welcher Autorität „richtig“? In einigen Sprachen, wie Ruby und Perl, lautet der offizielle "korrekte" Name für diese Strukturen "Hash".
Keine Ahnung
11
@nohat: Beachten Sie meine Verwendung von Anführungszeichen. Außerdem habe ich habe erklärt , warum der Name schlecht gewählt ist, nicht wahr? Wenn Sie also eine Behörde benötigen, dann sage ich, dass dies von der Polizei für theoretische Informatik genehmigt wurde.
Konrad Rudolph
9
Interessanterweise ist es in Ruby 1.9 tatsächlich unmöglich, die HashKlasse mit einer Hash-Tabelle zu implementieren , da Ruby 1.9 die HashEinfügereihenfolge beibehält, während dies in einer Hash-Tabelle nicht der Fall ist. In Ruby 1.9 Hashspiegelt der Name also nicht einmal mehr die Implementierung wider.
Jörg W Mittag
7
@ Hippietrail Du liegst falsch - das sind zunächst objektive Beschreibungen. Immerhin qualifiziere ich, warum die Benennung schlecht und eine falsche Bezeichnung ist (siehe unten). „Zu faul“ ist meinerseits eine künstlerische Lizenz, aber der Punkt bleibt, dass der Grund, den Namen zu kürzen, immanent ist, dh es gibt keinen Grund, hier einen Kurznamen zu verwenden, außer den Namen zu kürzen. Und Sie irren sich über "Wörterbuch": Das ist einfach der offizielle Name der Datenstruktur. Ihre Definition von "Wörterbuch" ist im Kontext der Informatik falsch, und der Name geht Python um Jahrzehnte voraus.
Konrad Rudolph
8

"Dictionary" heißt das Konzept. Eine Hash-Tabelle ist eine mögliche Implementierung.

dan_waterworth
quelle
1
Hash ist auch ein ADT. HashTable ist eine Implementierung eines Hash
Sairam
3
@Sairam Ich denke, es ist weitaus häufiger, dass 'Hash' eine Hash-Funktion bedeutet als eine Hash-Tabelle.
jk.
@jk Tatsächlich ist der "Hash" das Ergebnis der Anwendung einer "Hash-Funktion / eines Algorithmus" auf eine Eingabe. Eine "Hash-Tabelle" oder eine "Hash-Karte" bezieht sich auf ein Objekt und kann von einem Objekt gehasht werden (Objekt in einer generischen Form, nicht auf OOP beschränkt)
Johannes
Es gibt Sprachen, die 'Hash' verwenden, um sich auf eine Wörterbuchstruktur zu beziehen, und nicht nur auf die Hash-Funktionsoperation. Ruby zum Beispiel .
Sean Burton
7

Ein Wörterbuch ist der Sammelbegriff für jede Datenstrukturimplementierung, die für schnelle Suchvorgänge / Einfügungen verwendet wird. Dies kann unter Verwendung einer Vielzahl von Datenstrukturen wie Hash-Tabellen, Überspringlisten, RB-Baum usw. erreicht / implementiert werden. Eine Hash-Tabelle ist eine spezifische Datenstruktur, die für viele Zwecke nützlich ist, einschließlich der Implementierung eines Wörterbuchs.

aufather
quelle
Hash ist auch ein ADT. Gibt es einen spezifischen Unterschied zwischen Hash und Dictionary ADT?
Sairam
2
@Sairam: Nein, ein Hash ist die Ausgabe einer bestimmten Art von Algorithmus (Hash-Funktion).
5

Ein Wörterbuch verwendet einen Schlüssel, um auf den Wert direkt in einem assoziativen Array zu verweisen .

dh (KEY => VALUE)

Ein Hash wird häufiger als eine Hash-Tabelle beschrieben, die eine Hash-Funktion verwendet , um die Position im Speicher (oder einfacher ein Array) zu berechnen, an der sich der Wert befindet. Der Hash nimmt den KEY als Eingabe und gibt einen Wert als Ausgabe aus. Stecken Sie dann diesen Wert in den Speicher- oder Array-Index.

dh KEY => HASH FUNCTION => VALUE

Ich denke, einer ist direkt, der andere nicht. Hash-Funktionen sind möglicherweise auch nicht perfekt und liefern manchmal einen Index, der auf den falschen Wert verweist. Aber das kann korrigiert werden.

Bester Ort zum Schauen: Wikipedia ( assoziatives Array und Hash-Tabelle )

Ross
quelle