it-swarm-eu.dev

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

Was ist der Unterschied zwischen Hash und Dictionary?

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

48
Sairam

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

Dictionary ist das "korrekter" Name der Schnittstelle (= das ADT ), dh ein assoziativer Container, der (normalerweise eindeutige) Schlüssel (nicht unbedingt eindeutigen) Werten zuordnet.

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

Eine solche Implementierung hat zwei wichtige Eigenschaften:

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

(Wenn ein Schlüssel hashbar ist, 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 oft als sortiert Wörterbuch bezeichnet (und wird normalerweise in Bezug auf implementiert einen Suchbaum, obwohl andere effiziente Implementierungen existieren).


Zusammenfassend: a 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 Fehlbezeichnung, entspricht jedoch im Kontext einem Wörterbuch, das in Form einer Hash-Tabelle implementiert ist.

94
Konrad Rudolph

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

8
dan_waterworth

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.

7
aufather

Ein Wörterbuch verwendet einen Schlüssel, um den Wert direkt in einem assoziatives Array zu referenzieren.

d.h. (KEY => VALUE)

Ein Hash wird häufiger als Hash-Tabelle beschrieben, das ein Hash-Funktion verwendet, um die Position im Speicher (oder einfacher ein Array) zu berechnen, wobei Der Wert wird sein. 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.

d.h. 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. Das kann aber korrigiert werden.

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

5
Ross