Was ist der Unterschied zwischen einer Karte und einem Wörterbuch?

Ich weiß, dass eine Karte eine Datenstruktur ist, die Schlüssel Werten zuordnet. Ist ein Wörterbuch nicht dasselbe? Was ist der Unterschied zwischen einer Karte und einem Wörterbuch ¹ ?

_{1. Ich frage nicht, wie sie in der Sprache X oder Y definiert sind (was anscheinend das ist, was die Leute hier auf SO allgemein fragen), ich möchte wissen, was ihr Unterschied in der Theorie ist.}

Zwei Begriffe für dasselbe:

• "Map" wird von Java, C ++ verwendet
• "Dictionary" wird von .Net, Python verwendet
• "Assoziatives Array" wird von PHP verwendet

"Map" ist der richtige mathematische Begriff, wird jedoch vermieden, da er in der funktionalen Programmierung eine separate Bedeutung hat .

Einige Sprachen verwenden noch andere Begriffe ("Objekt" in Javascript, "Hash" in Ruby, "Tabelle" in Lua) , aber alle haben auch in der Programmierung unterschiedliche Bedeutungen, daher würde ich sie vermeiden.

Sehen Sie hier für weitere Informationen.

Einer ist ein älterer Begriff für den anderen. Typischerweise wurde der Begriff "Wörterbuch" verwendet, bevor sich der mathematische Begriff "Karte" durchsetzte. Wörterbücher haben in der Regel einen Schlüsseltyp, aber das stimmt nicht überall.

Meine 2 Cent.

Dictionary ist eine abstrakte Klasse in Java, während Map eine Schnittstelle ist. Da Java keine Mehrfachvererbungen unterstützt, kann eine Klasse, die Dictionary erweitert, keine andere Klasse erweitern.

Daher wurde die Kartenschnittstelle eingeführt.

Die Wörterbuchklasse ist veraltet und die Verwendung von Map wird bevorzugt.

Die Beantwortung dieser Frage wird dadurch erschwert, dass Programmierer gesehen haben, dass die Begriffe in bestimmten Sprachen oder Systemen, die sie verwendet haben, spezifischere Bedeutungen haben, aber die Frage verlangt einen sprachunabhängigen Vergleich "in der Theorie", den ich in Begriffen der Informatik meine .

Die Terminologie erklärt

Das Oxford University Dictionary of Computer Science listet auf:

Wörterbuch jede Datenstruktur, die eine Reihe von Elementen darstellt, die das Einfügen und Löschen von Elementen sowie den Test auf Mitgliedschaft unterstützen können

• Zum Beispiel haben wir eine Reihe von Elementen {A, B, C, D ...}, die wir einfügen und löschen konnten, und wir können abfragen: " Ist C vorhanden?" .

Der Computing Science-Begriff der Karte basiert jedoch auf dem mathematisch-sprachlichen Begriff Mapping , den das Oxford Dictionary definiert als:

Mapping Eine Operation, die jedes Element einer bestimmten Menge (die Domäne) einem oder mehreren Elementen einer zweiten Menge (dem Bereich) zuordnet.

• Als solches bietet eine Kartendatenstruktur eine Möglichkeit, von Elementen einer bestimmten Menge - bekannt als " Schlüssel " in der Karte - zu einem oder mehreren Elementen in der zweiten Menge zu gelangen, die als zugehörige " Werte " bekannt sind.
• Der Aspekt "... oder mehr Elemente im zweiten Satz" kann von einer Implementierung auf zwei verschiedene Arten unterstützt werden:
  • Viele Map-Implementierungen erzwingen die Eindeutigkeit der Schlüssel und erlauben nur, dass jeder Schlüssel einem Wert zugeordnet wird. Dieser Wert kann jedoch möglicherweise eine Datenstruktur selbst sein, die viele Werte eines einfacheren Datentyps enthält, z. B. {{1, {"one". , "ichi"}, {2, {"two", "ni"}}} zeigt Werte, die aus Zeichenfolgenpaaren bestehen.
  • Andere Zuordnungsimplementierungen ermöglichen doppelte Schlüssel, die jeweils denselben oder unterschiedlichen Werten zugeordnet sind. Dies erfüllt funktional den Fall "assoziiert ... jedes [Schlüssel] -Element ... mit ... mehr [mehr als einem] [Wert] -Element". Zum Beispiel {{1, "eins"}, {1, "ichi"}, {2, "zwei"}, {2, "ni"}}.

Wörterbuch und Karte kontrastiert

Unter Verwendung der oben beschriebenen strengen Comp Sci-Terminologie ist ein Wörterbuch nur dann eine Karte, wenn die Schnittstelle zusätzliche Vorgänge unterstützt, die nicht für jedes Wörterbuch erforderlich sind:

• die Fähigkeit, Speicherelemente mit unterschiedlichen Schlüsseln und Wertkomponenten

• die Fähigkeit, die Werte nur mit dem Schlüssel abzurufen

Eine triviale Wendung:

• Eine Kartenschnittstelle unterstützt möglicherweise nicht direkt einen Test, ob sich ein {Schlüssel, Wert} -Paar im Container befindet. Dies ist pedantisch eine Anforderung eines Wörterbuchs, in dem die Elemente zufällig {Schlüssel, Wert} -Paare sind. Eine Karte verfügt möglicherweise nicht einmal über eine Funktion zum Testen eines Schlüssels. Im schlimmsten Fall können Sie jedoch feststellen, ob ein versuchter Wertabruf nach Schlüssel erfolgreich ist oder fehlschlägt. Wenn Sie sich darum kümmern, können Sie überprüfen, ob der Schlüssel einen erwarteten Wert abgerufen hat.

Kommunizieren Sie eindeutig mit Ihrem Publikum

⚠ Wenn Sie trotz alledem ein Wörterbuch in der oben erläuterten strengen Bedeutung von Computing Science verwenden, sollten Sie nicht erwarten, dass Ihr Publikum Ihnen zunächst folgt oder beeindruckt ist, wenn Sie die Terminologie teilen und verteidigen. Die anderen Antworten auf diese Frage (und ihre positiven Stimmen) zeigen, wie wahrscheinlich es ist, dass "Wörterbuch" nach Erfahrung der meisten Programmierer gleichbedeutend mit "Karte" ist . Versuchen Sie, eine Terminologie zu wählen, die umfassender und eindeutiger verstanden wird: z

• assoziativer Container : Jeder Container, der Schlüssel / Wert-Paare mit Wertabruf und Löschung nach Schlüssel speichert
• Hash-Map : Eine Hash-Tabellenimplementierung eines zugeordneten Containers
• Hash-Set, das eindeutige Schlüssel erzwingt : Eine Hash-Tabellenimplementierung eines Wörterbuchs, in dem Elemente / Werte gespeichert werden, ohne dass sie unterschiedliche Schlüssel- / Wertkomponenten enthalten, wobei Duplikate der Elemente nicht eingefügt werden können
• balance binäre Baumkarte, die doppelte Schlüssel unterstützt : ...

Crossreferencing Comp Sci-Terminologie mit spezifischen Implementierungen

C ++ Standard Library

• Karten: map, multimap, unordered_map,unordered_multimap
• andere Wörterbuch: set, multiset, unordered_set,unordered_multiset
• Anmerkung: mit Iteratoren oder std::findSie können ein Element und Test für die Mitgliedschaft in löschen array, vector, list, dequeusw., aber die Container - Schnittstellen unterstützen nicht direkt , dass da ein Element zu finden , bei O (N) spektakulär ineffizient ist, in einigen Fällen insert / Erase Ineffizient, und die Unterstützung dieser Vorgänge untergräbt die absichtlich eingeschränkte API, die der Container impliziert - z. B. dequesollten s nur das Löschen / Pop auf der Vorder- und Rückseite und nicht in Bezug auf einen Schlüssel unterstützen. Wenn der Programmierer mehr Arbeit im Code leisten muss, um die Suche zu koordinieren, wird er aufgefordert, zu einer Container-Datenstruktur mit effizienterer Suche zu wechseln.

... kann später weitere Sprachen hinzufügen / kann in ... bearbeitet werden

Normalerweise gehe ich davon aus, dass eine Karte von einer Hash-Tabelle unterstützt wird. es bedeutet einen ungeordneten Laden. Wörterbücher kennzeichnen einen bestellten Laden.

Es gibt ein baumbasiertes Wörterbuch namens Trie .

In Lisp könnte es so aussehen:

(a (n (d t)) n d )

Welches kapselt die Wörter:

• ein
• und
• Ameise
• ein
• Anzeige

Die Durchquerung von oben zum Blatt ergibt ein Wort.

Nicht wirklich dasselbe. Karten sind eine Teilmenge des Wörterbuchs. Wörterbuch ist hier so definiert , dass es die Funktionen Einfügen, Löschen und Suchen hat. Map, wie es von Java (gemäß diesem ) verwendet wird, ist ein Wörterbuch mit der Anforderung, dass die Schlüsselzuordnung zu Werten streng als Eins-zu-Eins-Funktion zugeordnet wird. Ein Wörterbuch kann mehr als eine Schlüsselzuordnung zu einem Wert oder eine Schlüsselzuordnung zu mehreren Werten haben (z. B. Verketten in einer Hashtabelle), z. B. Twitter-Hashtag-Suche.

Als Beispiel für eine "realere Welt" kann das Nachschlagen eines Wortes in einem Wörterbuch eine Reihe von Definitionen für dasselbe Wort ergeben, und wenn wir einen Eintrag finden, der uns auf einen anderen Eintrag verweist (siehe anderes Wort), eine Reihe von Wörtern für die gleiche Liste von Definitionen. In der realen Welt sind Karten viel breiter, so dass wir Orte für Namen oder Namen für Koordinaten haben können, aber wir können auch einen nächsten Nachbarn oder andere Attribute (Populationen usw.) finden, so dass meiner Meinung nach Argumente für eine größere Erweiterung von vorhanden sein könnten Der Kartentyp soll möglicherweise graphbasierte Implementierungen haben. Es ist jedoch am besten, immer nur das Schlüssel-Wert-Paar anzunehmen, zumal der nächste Nachbar und andere Attribute des Werts nur Datenelemente des Werts sein können.

Java-Maps können trotz der Eins-zu-Eins-Anforderung eher ein verallgemeinertes Wörterbuch implementieren, wenn der Wert als Sammlung selbst verallgemeinert wird oder wenn die Werte lediglich Verweise auf an anderer Stelle gespeicherte Sammlungen sind.

Denken Sie daran, dass Java-Betreuer nicht die Verwalter von ADT-Definitionen sind und dass Java-Entscheidungen speziell für Java gelten.

Andere Begriffe für dieses Konzept, die ziemlich häufig vorkommen: assoziatives Array und Hash.

Ja, sie sind gleich. Sie können der Mischung "Assoziatives Array" hinzufügen.

using Hashtable oder a Hashofter bezieht sich auf die Implementierung.

also auf einer rein theoretischen Ebene.

Ein Wörterbuch ist ein Wert, mit dem ein verknüpfter Wert gefunden werden kann. Eine Karte ist ein Wert, der Anweisungen zum Auffinden anderer Werte enthält

Alle Sammlungen, die einen nichtlinearen Zugriff ermöglichen (dh nur zuerst oder zuletzt erhalten), sind eine Karte, da selbst ein einfaches Array einen Index hat, der dem richtigen Wert zugeordnet ist. Während ein Wörterbuch ein Kartentyp ist, bieten Karten einen viel breiteren Funktionsbereich.

In der Praxis ist dies normalerweise die Zuordnungsfunktion, die den Namen definiert. Eine HashMap ist also eine zugeordnete Datenstruktur, die einen Hashing-Algorithmus verwendet, um den Schlüssel mit dem Wert zu verknüpfen, wobei ein Wörterbuch nicht angibt, wie die Schlüssel mit einem Wert verknüpft sind Dies könnte über eine verknüpfte Liste, einen Baum oder einen anderen Algorithmus gespeichert werden. Vom Ende der Nutzung ist es Ihnen normalerweise egal, welchen Algorithmus sie nur verwenden, sodass Sie ein generisches Wörterbuch verwenden und nur dann zu einer der anderen Strukturen wechseln, wenn Sie den Typ des Algorithmus angeben müssen

Dies sind zwei verschiedene Begriffe für dasselbe Konzept.
Hashtableund HashMapbeziehen sich auch auf das gleiche Konzept.

Der Hauptunterschied besteht darin, dass für eine Map alle Einträge (Wert & Schlüsselpaar) einen eindeutigen Schlüssel haben müssen. Wenn Kollisionen auftreten, dh wenn ein neuer Eintrag denselben Schlüssel wie ein Eintrag in der Sammlung hat, ist eine Kollisionsbehandlung erforderlich.

Normalerweise behandeln wir Kollisionen entweder mit einer separaten Verkettung . Oder lineare Prüfung .

Mit einem Wörterbuch können mehrere Einträge mit demselben Schlüssel verknüpft werden.

Wenn eine Karte eine separate Verkettung implementiert hat, ähnelt sie in der Regel einem Wörterbuch.