Was ist der Unterschied zwischen Hash und Dictionary?

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

Antwort

Hash ist eine äußerst schlecht benannte Datenstruktur, bei der der Programmierer die Schnittstelle mit der Implementierung verwechselt hat ( und waren zu faul, um den vollständigen Namen zu schreiben, dh HashTable greift stattdessen auf eine Abkürzung zurück (Hash).

Dictionary ist der „korrekte“ 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 müssen ha sein shable und Gleichheit vergleichbar .
  2. Die Einträge werden in keiner bestimmten Reihenfolge im Wörterbuch angezeigt.

(Für einen Schlüssel zu hashable bedeutet, dass wir einen numerischen Wert aus einem Schlüssel berechnen können, der anschließend als Index in einem Array verwendet wird.)

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

To Zusammenfassend: Ein Wörterbuch ist ein ADT, das Schlüssel Werten zuordnet. Es gibt mehrere mögliche Implementierungen dieses ADT, von denen die Hash-Tabelle eine ist. Hash ist eine falsche Bezeichnung, entspricht jedoch im Kontext einem Wörterbuch, das in Form einer Hash-Tabelle implementiert ist.

Kommentare

  • Um ein Beispiel in C ++ zu geben, konnten die assoziativen Standardcontainervorlagen ' nicht als Hashes implementiert werden, obwohl der nächste Standard effektiv Hash-Tabellen enthält. Sie ' werden unordered_map genannt, um zu zeigen, was sie tun und nicht was sie sind.
  • „richtig“ gemäß Welche Autorität? In einigen Sprachen, wie Ruby und Perl, lautet der offizielle Name für diese Strukturen „Hash“.
  • @nohat: Beachten Sie, dass ich Anführungszeichen verwende. Außerdem habe ich erklärt erklärt, warum der Name schlecht gewählt ist, oder? Wenn Sie also eine Berechtigung benötigen, werde ich sagen, dass dies von der Behörde der theoretischen Informatikpolizei erfolgt.
  • Interessanterweise ist es in Ruby 1.9 tatsächlich unmöglich, die -Klasse mit einer Hash-Tabelle, da Ruby 1.9 Hash die Einfügereihenfolge beibehält, während eine Hash-Tabelle dies nicht tut. In Ruby 1.9 spiegelt der Name Hash ' nicht einmal mehr die Implementierung wider.
  • @hippietrail Sie liegen falsch – erstens sind dies 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 für die Verkürzung des Namens wesentlich ist, d. H. Es gibt keinen Grund, hier einen Kurznamen zu verwenden, außer den Namen zu verkü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 liegt Jahrzehnte vor Python.

Antwort

„Wörterbuch“ ist der Name des Konzepts. Eine Hashtabelle ist eine mögliche Implementierung.

Kommentare

  • Hash ist auch ein ADT. HashTable ist eine Implementierung eines Hash
  • @Sairam. Ich denke, es ist weitaus häufiger, wenn ' Hash ' bedeutet eine Hash-Funktion anstelle einer Hash-Tabelle.
  • @jk Tatsächlich ist der " Hash " das Ergebnis der Anwendung eine " Hash-Funktion / Algorithmus " für eine Eingabe. Eine " Hash-Tabelle " oder " Hash-Map " omehoe bezieht ein Hash-Objekt auf ein Objekt (Objekt in generischer Form, nicht auf OOP beschränkt).
  • Es gibt Sprachen, die ' Hash ' bezieht sich auf eine Struktur vom Typ eines Wörterbuchs und nicht nur auf die Hash-Funktionsoperation. Ruby zum Beispiel .

Antwort

Ein Wörterbuch ist der Sammelbegriff für jede Datenstrukturimplementierung, die für schnelle Suchvorgänge / Einfügungen verwendet wird. Dies kann mithilfe einer Vielzahl von Datenstrukturen wie Hash-Tabelle, Sprunglisten, 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.

Kommentare

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

Antwort

Ein Wörterbuch verwendet einen Schlüssel für Verweisen Sie auf den Wert direkt in einem assoziativen Array .

dh (KEY => VALUE)

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

dh KEY => HASH FUNCTION => VALUE

Ich denke, einer ist direkt, während der andere isn „t. Hash-Funktionen sind möglicherweise auch nicht perfekt und liefern manchmal einen Index, der auf den falschen Wert verweist. Dies kann jedoch korrigiert werden.

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

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.