Assoziatives Array

Im Informatik, ein Assoziatives Array, Karte, Symboltabelle, oder Wörterbuch ist ein Zusammenfassung Datentyp das speichert a Sammlung von (Schlüssel, Wert) Paare, so dass jeder mögliche Schlüssel höchstens in der Sammlung erscheint. In mathematischer Hinsicht ist ein assoziatives Array a Funktion mit endlich Domain.[1] Es unterstützt "Such-", "Entfernen" und "Einfügen" Vorgänge.

Das Wörterbuchproblem ist das klassische Problem der effizienten Gestaltung Datenstrukturen das implementiert assoziative Arrays.[2] Die beiden Hauptlösungen für das Wörterbuchproblem sind Hash -Tische und Bäume suchen.[3][4][5][6] In einigen Fällen ist es auch möglich, das Problem mit direktem angesprochenem Problem zu lösen Arrays, Binäre Suchbäumeoder andere spezialisiertere Strukturen.

Viele Programmiersprachen enthalten assoziative Arrays als Primitive Datentypenund sie sind in erhältlich Software -Bibliotheken Für viele andere. Inhaltsadressible Speicher ist eine Form der Direktunterstützung auf Hardware-Ebene für assoziative Arrays.

Assoziative Arrays haben viele Anwendungen, einschließlich solcher grundlegender Programmiermuster wie Memoisierung und die Dekorateurmuster.[7]

Der Name kommt nicht von der assoziatives Eigentum bekannt in Mathematik. Vielmehr entsteht es aus der Tatsache, dass wir Werte mit Schlüsseln assoziieren. Es ist nicht zu verwechseln mit assoziative Prozessoren.

Operationen

In einem assoziativen Array die Zusammenarbeit zwischen ein Schlüssel und ein Wert wird oft als "Zuordnung" bezeichnet, und dieselbe Word -Zuordnung kann auch verwendet werden, um sich auf den Prozess der Erstellung einer neuen Assoziation zu beziehen.

Die Operationen, die normalerweise für ein assoziatives Array definiert sind, sind:[3][4][8]

  • Einfügung oder stellen: Fügen Sie eine neue hinzu Kombinieren Sie die Sammlung und machen Sie den Schlüssel zu seinem neuen Wert ab. Jede vorhandene Zuordnung wird überschrieben. Die Argumente für diesen Vorgang sind der Schlüssel und der Wert.
  • Entfernen oder löschen: entfernen a Kombiniere aus der Sammlung und entmischst einen bestimmten Schlüssel aus seinem Wert. Das Argument für diese Operation ist der Schlüssel.
  • Sieh nach oben, finden, oder erhalten: Finden Sie den Wert (falls vorhanden), der an einen bestimmten Schlüssel gebunden ist. Das Argument für diese Operation ist der Schlüssel, und der Wert wird von der Operation zurückgegeben. Wenn kein Wert gefunden wird, erhöhen einige assoziative Array -Implementierungen eine Ausnahme, während andere einen Standardwert zurückgeben (null, null, spezifischer Wert, der an den Konstruktor übergeben wird, ...).

Darüber hinaus können assoziative Arrays auch andere Operationen enthalten, z. Iterator über alle Zuordnungen zu schließen. In der Regel kann für einen solchen Betrieb die Reihenfolge, in der die Zuordnungen zurückgegeben werden, implementiert werden.

A Multimap verallgemeinert ein assoziatives Array, indem mehrere Werte mit einem einzelnen Schlüssel zugeordnet werden können.[9] A Bidirektionale Karte ist ein verwandter abstrakter Datentyp, in dem die Zuordnungen in beide Richtungen arbeiten: Jeder Wert muss mit einem eindeutigen Schlüssel zugeordnet werden, und ein zweiter Suchvorgang nimmt einen Wert als Argument an und sucht den mit diesem Wert verbundenen Schlüssel nach.

Eigenschaften

Die Operationen des assoziativen Arrays sollten verschiedene Eigenschaften erfüllen:[8]

  • Lookup (k, einfügen (j, v, d)) = wenn k == j dann v sonst such (k, d)
  • Lookup (k, new ()) = fehlschlagen, wo scheitern ist eine Ausnahme oder Standardwert
  • Entfernen (k, k, einfügen (j, v, d)) = Wenn k == j dann (k, d) else einfügen (j, v, entfernen (k, d))
  • remove (k, new ()) = new ()

wo k und j sind Schlüssel, v ist ein Wert, D ist ein assoziatives Array und Neu() Erstellt ein neues, leeres assoziatives Array.

Beispiel

Angenommen, die von einer Bibliothek vermittelte Kredite ist in einer Datenstruktur dargestellt. Jedes Buch in einer Bibliothek kann jeweils nur von einem einzelnen Bibliotheksmatron ausgecheckt werden. Ein einzelner Patron kann jedoch möglicherweise mehrere Bücher auschecken. Daher werden die Informationen darüber, welche Bücher ausgecheckt werden, auf die Kunden durch ein assoziatives Array dargestellt werden können, in dem die Bücher die Schlüssel und die Gönner die Werte sind. Verwendung von Notation von Python oder JSONDie Datenstruktur wäre:

{  "Stolz und Vorurteile": "Alice",  "Wuthering Heights": "Alice",  "Große Erwartungen": "John" } 

Ein Nachbetrieb der wichtigsten "großen Erwartungen" würde "John" zurückgeben. Wenn John sein Buch zurückgibt, würde dies zu einem Löschvorgang führen, und wenn Pat ein Buch angeht, würde dies eine Einfügungsoperation verursachen, was zu einem anderen Zustand führt:

{  "Stolz und Vorurteile": "Alice",  "Die Brüder Karamazov": "Klopfen",  "Wuthering Heights": "Alice" } 

Implementierung

Für Wörterbücher mit sehr geringer Anzahl von Zuordnungen kann es sinnvoll sein, das Wörterbuch mit einem umzusetzen Assoziationsliste, a verlinkte Liste von Zuordnungen. Mit dieser Implementierung ist die Zeit für die Durchführung der grundlegenden Wörterbuchoperationen in der Gesamtzahl der Zuordnungen linear. Es ist jedoch einfach zu implementieren und die ständigen Faktoren in seiner Laufzeit sind gering.[3][10]

Eine weitere sehr einfache Implementierungstechnik, die verwendet werden kann, wenn die Schlüssel auf einen engen Bereich beschränkt sind, ist direkt in ein Array: Der Wert für einen bestimmten Schlüssel k wird in der Array -Zelle gespeichert A[k] oder wenn es keine Zuordnung für gibt k Dann speichert die Zelle ein Special Sentinel -Wert Das zeigt das Fehlen einer Kartierung an. Diese Technik ist nicht nur einfach, sondern auch einfach: Jeder Wörterbuchbetrieb braucht ständige Zeit. Der Raumbedarf für diese Struktur ist jedoch die Größe des gesamten Schlüsselspace, so dass es unpraktisch ist, es sei denn, der Schlüsselspace ist klein.[5]

Die beiden Hauptansätze zur Umsetzung von Wörterbüchern sind a Hash-tabelle oder ein Suchbaum.[3][4][5][6]

Hash -Tabellen -Implementierungen

Diese Grafik vergleicht die durchschnittliche Anzahl von CPU -Cache Fehlschlägen, die erforderlich sind, um Elemente in großen Hash -Tabellen zu suchen (weit über die Größe des Cache) mit der Verkettung und lineare Untersuchung. Lineare Probe ist aufgrund des besseren Leistungen besser ab ReferenzortObwohl der Tisch voll wird, nimmt sich ihre Leistung drastisch ab.

Die am häufigsten verwendete allgemeine Implementierung eines assoziativen Arrays ist mit a Hash-tabelle: ein Array kombiniert mit a Hash-Funktion Das unterteilt jeden Schlüssel in einen separaten "Eimer" des Arrays. Die Grundidee hinter einer Hash-Tabelle ist, dass der Zugriff auf ein Element eines Arrays über seinen Index ein einfacher Betrieb mit konstanter Zeit ist. Daher ist der durchschnittliche Aufwand eines Vorgangs für eine Hash -Tabelle nur die Berechnung des Hash des Schlüssels, kombiniert mit dem Zugriff auf den entsprechenden Eimer innerhalb des Arrays. Daher werden Hash -Tabellen normalerweise in o (1) Zeit durchgeführt und übertreffen Alternativen in den meisten Situationen.

Hash -Tische müssen in der Lage sein, umgehen können Kollisionen: Wenn die Hash -Funktion zwei verschiedene Schlüssel auf denselben Eimer des Arrays ordnet. Die beiden am weitesten verbreiteten Ansätze für dieses Problem sind separate Verkettung und Offene Adressierung.[3][4][5][11] In separaten Verkettung speichert das Array den Wert selbst nicht, sondern speichert a Zeiger zu einem anderen Behälter, normalerweise eine AssoziationslisteDas speichert alle Werte, die dem Hash entsprechen. Auf der anderen Seite sucht die Tabelle bei offener Adressierung, wenn eine Hash -Kollision gefunden wird, einen leeren Punkt in einem Array, um den Wert deterministisch zu speichern, normalerweise durch Betrachtung der nächsten unmittelbaren Position im Array.

Offene Adressierung hat eine niedrigere Cache Miss Verhältnis als separate Verkettung, wenn die Tabelle größtenteils leer ist. Da die Tabelle jedoch mit mehr Elementen gefüllt wird, verschlechtert sich die Leistung von Open Adressing exponentiell. Darüber hinaus verwendet die separate Verkettung in den meisten Fällen weniger Speicher, es sei denn, die Einträge sind sehr klein (weniger als viermal so groß wie ein Zeiger).

Baumimplementierungen

Selbstausgleichende binäre Suchbäume

Ein weiterer häufiger Ansatz besteht darin, ein assoziatives Array mit a umzusetzen selbstausgleichender binärer Suchbaumwie ein Avl Baum oder ein Rot -Schwarz -Baum.[12]

Im Vergleich zu Hash -Tabellen haben diese Strukturen sowohl Vorteile als auch Schwächen. Die schlechteste Leistung von selbstausgleichenden binären Suchbäumen ist erheblich besser als die eines Hash-Tisches, mit einer zeitlichen Komplexität in Big O Notation von o (log n). Dies steht im Gegensatz zu Hash-Tabellen, deren Worst-Case-Leistung alle Elemente betrifft, die einen einzelnen Eimer teilen, was zu O führt ((n) Zeitkomplexität. Außerdem und wie alle binären Suchbäume halten selbstausgleichende binäre Suchbäume ihre Elemente in Ordnung. Das Durchlaufen seiner Elemente folgt daher einem am wenigsten zu wichtigsten Muster, während das Durchqueren einer Hash-Tabelle dazu führen kann, dass Elemente in scheinbar zufälliger Reihenfolge sind. Hash-Tabellen haben jedoch eine viel bessere Komplexität der Durchschnittsfallzeit als selbstausgleichende binäre Suchbäume von O (1), und ihre schlimmste Leistung ist höchst unwahrscheinlich, wenn ein Gutes gut ist Hash-Funktion wird genutzt.

Es ist erwähnenswert, dass ein selbstausgleichender binärer Suchbaum verwendet werden kann, um die Eimer für eine Hash-Tabelle zu implementieren, die separate Verkettung verwendet. Dies ermöglicht eine konstante Suche durch durchschnittliche Fälle, sorgt jedoch für eine Worst-Case-Leistung von O (log n). Dies führt jedoch zusätzliche Komplexität in die Implementierung ein und kann für kleinere Hash -Tabellen eine noch schlechtere Leistung verursachen, in denen die Zeit, die für den Einsetzen und Ausgleich des Baumes verbracht wurde Lineare Suche auf allen Elementen einer verknüpften Liste oder einer ähnlichen Datenstruktur.[13][14]

Andere Bäume

Assoziative Arrays können auch in unausgeglichenen Aufbewahrung gespeichert werden Binäre Suchbäume oder in Datenstrukturen spezialisiert auf einen bestimmten Typ von Schlüssel wie z. Radixbäume, Versuche, Judy Arrays, oder Van Emde Boas BäumeObwohl die Fähigkeit dieser Implementierungsmethoden im Vergleich zu Hash -Tabellen unterschiedlich ist; Zum Beispiel sind Judy -Bäume weiterhin für eine geringere Menge an Effizienz als Hash -Tabellen angezeigt, während sorgfältig ausgewählte Hash -Tabellen im Vergleich zu adaptiven Radixbäumen im Allgemeinen mit einer erhöhten Effizienz durchführen, wobei möglicherweise höhere Datenstypen, die sie ausführen können,.[15] Die Vorteile dieser alternativen Strukturen stammen aus ihrer Fähigkeit, Operationen über die grundlegenden assoziativen Array hinaus zu handhaben, z.

Vergleich

Zugrunde liegende Datenstruktur Suche oder Entfernung Einfügen Bestellt
Durchschnitt schlimmsten Fall Durchschnitt schlimmsten Fall
Hash-tabelle O (1) Ö(n)) O (1) Ö(n)) Nein
Selbstausgleichender binärer Suchbaum O (Protokoll n)) O (Protokoll n)) O (Protokoll n)) O (Protokoll n)) Ja
unausgeglichen Binärer Suchbaum O (Protokoll n)) Ö(n)) O (Protokoll n)) Ö(n)) Ja
Sequentieller Container von Schlüssel -Wert -Paare
(z.B. Assoziationsliste))
Ö(n)) Ö(n)) O (1) O (1) Nein

Geordnetes Wörterbuch

Die grundlegende Definition des Wörterbuchs schreibt keine Anordnung vor. Um eine feste Reihenfolge der Aufzählung zu gewährleisten, werden häufig geordnete Versionen des assoziativen Arrays verwendet. Es gibt zwei Sinne eines geordneten Wörterbuchs:

  • Die Reihenfolge der Aufzählung ist immer deterministisch für eine bestimmte Schlüsselgruppe durch Sortieren. Dies ist der Fall für baumbasierte Implementierungen, ein Vertreter ist der der ist der Container von C ++.[16]
  • Die Reihenfolge der Aufzählung ist Schlüsselunabhängiger und basiert stattdessen auf der Reihenfolge der Einfügung. Dies ist der Fall für das "geordnete Wörterbuch" in .NET Framework und Python.[17][18]

Das letztere Gefühl der geordneten Wörterbücher werden häufiger auftreten. Sie können mit einem implementiert werden Assoziationsliste, oder durch Überlagern a doppelt verknüpfte Liste Über ein normales Wörterbuch. Der letztere Ansatz, der von CPython vor Version 3.6 verwendet wird, hat den Vorteil, die potenziell bessere Komplexität einer anderen Implementierung zu halten.[19] CPython 3.6+ macht Wörterbücher, die durch Aufteilung der Hash-Tabelle in ein insertioniertes Array von K-V-Paaren und ein spärliches Array ("Hash-Tabelle") von Indizes geordnet sind.[20]

Sprachunterstützung

Assoziative Arrays können in jeder Programmiersprache als Paket implementiert werden, und viele Sprachsysteme bieten sie als Teil ihrer Standardbibliothek. In einigen Sprachen sind sie nicht nur in das Standardsystem integriert, sondern haben auch eine spezielle Syntax, häufig mit Array-ähnlichen Abonnements.

Die integrierte syntaktische Unterstützung für assoziative Arrays wurde 1969 von eingeführt von Snobol4, unter dem Namen "Tabelle". Tmg Angebotene Tabellen mit Stringschlüssel und ganzzahligen Werten. MUMPS multidimensionale assoziative Arrays hergestellt, optional persistent, seine Schlüsseldatenstruktur. Setl unterstützte sie als eine mögliche Implementierung von Sätzen und Karten. Die meisten modernen Skriptsprachen, beginnend mit Awk und einschließlich Rexx, Perl, Php, Tcl, JavaScript, Ahorn, Python, Rubin, Wolfram Sprache, gehen, und Lua, unterstützen Sie assoziative Arrays als primärer Containertyp. In vielen weiteren Sprachen sind sie als Bibliotheksfunktionen ohne spezielle Syntax erhältlich.

Im Smalltalk, Ziel c, .NETZ,[21] Python, Realbasic, Schnell, VBA und Delphi[22] Sie heißen Wörterbücher; in Perl, Rubin und Samen7 Sie heißen Hashes; in C ++, Java, gehen, Clojure, Scala, Ocaml, Haskell Sie heißen Karten (sehen Karte (C ++), Under Ordered_map (C ++), und Karte); in Common Lisp und Windows PowerShell, Sie heißen Hash -Tische (Da beide diese Implementierung normalerweise verwenden); in Ahorn Und Lua, sie werden genannt Tische. Im PhpAlle Arrays können assoziativ sein, außer dass die Schlüssel auf Ganzzahlen und Saiten beschränkt sind. In JavaScript (siehe auch JSON), alle Objekte verhalten sich als assoziative Arrays mit String-Wert-Tasten, während die MAP- und Schwachhap-Typen willkürliche Objekte als Schlüssel annehmen. In Lua werden sie als primitiver Baustein für alle Datenstrukturen verwendet. Im Visual Foxpro, Sie heißen Sammlungen. Das D Sprache hat auch Unterstützung für assoziative Arrays.[23]

Permanente Speicherung

Viele Programme, die assoziative Arrays verwenden, müssen diese Daten irgendwann in einer dauerhafteren Form speichern, wie in a Computerdatei. Eine gemeinsame Lösung für dieses Problem ist ein generalisiertes Konzept, das als bekannt ist Archivierung oder Serialisierung, der einen Text oder eine binäre Darstellung der ursprünglichen Objekte erzeugt, die direkt in eine Datei geschrieben werden können. Dies wird am häufigsten im zugrunde liegenden Objektmodell wie .NET oder Kakao implementiert, die Standardfunktionen enthalten, die die internen Daten in Textform umwandeln. Das Programm kann eine vollständige Textdarstellung jeder Gruppe von Objekten erstellen, indem diese Methoden aufgerufen werden, die fast immer in der Basis -Associativ -Array -Klasse implementiert sind.[24]

Für Programme, die sehr große Datensätze verwenden, ist diese Art von Einzeldateispeicher nicht angemessen und a Datenbankverwaltungssystem (DB) ist erforderlich. Einige DB -Systeme speichern assoziative Arrays nativ, indem sie die Daten serialisieren und dann diese serialisierten Daten und den Schlüssel speichern. Einzelne Arrays können dann mithilfe des Schlüssels aus der Datenbank geladen oder gespeichert werden. Diese Schlüssel -Wert -Stores werden seit vielen Jahren eingesetzt und haben eine Geschichte, solange dies das häufigere ist relationale Datenbank (RDBS), aber ein Mangel an Standardisierung unter anderem beschränkte ihre Verwendung auf bestimmte Nischenrollen. RDBs wurden in den meisten Fällen für diese Rollen verwendet, obwohl das Speichern von Objekten in einem RDB kompliziert werden kann, ein Problem, das als bekannt ist als Objektrelationsimpedanz-Missverhältnis.

Nach c.2010die Notwendigkeit von Hochleistungsdatenbanken für geeignet für Cloud Computing und genauer gesagt, die interne Struktur der Programme zu entsprechen, die sie verwenden, führte zu einer Renaissance auf dem Key -Wert -Store -Markt. Diese Systeme können assoziative Arrays in native Weise speichern und abrufen, was die Leistung in gemeinsamen Web-Workflows erheblich verbessern kann.

Siehe auch

Verweise

  1. ^ Collins, Graham; Syme, Donald (1995). "Eine Theorie endlicher Karten". Logik -Theorem -Beweis für höhere Ordnung und seine Anwendungen. Vorlesungsnotizen in Informatik. 971: 122–137. doi:10.1007/3-540-60275-5_61. ISBN 978-3-540-60275-0.
  2. ^ Andersson, Arne (1989). "Optimale Grenzen für das Wörterbuchproblem". Proc. Symposium über optimale Algorithmen. Vorlesungsnotizen in Informatik. Springer Verlag. 401: 106–114. doi:10.1007/3-540-51859-2_10. ISBN 978-3-540-51859-4.
  3. ^ a b c d e Goodrich, Michael T.; Tamassia, Roberto (2006), "9.1 DIE MAP STRACTRACT -Datentyp", " Datenstrukturen und Algorithmen in Java (4. Aufl.), Wiley, S. 368–371
  4. ^ a b c d Mehlhorn, Kurt; Sanders, Peter (2008), "4 Hash -Tabellen und assoziative Arrays", Algorithmen und Datenstrukturen: Die grundlegende Toolbox (PDF), Springer, S. 81–98
  5. ^ a b c d Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "11 Hash -Tabellen", Einführung in Algorithmen (2. Aufl.), MIT Press und McGraw-Hill, S. 221–252, ISBN 0-262-03293-7.
  6. ^ a b M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert und R. E. Tarjan 1994."Dynamic Perfect Hashing: Ober- und Untergrenzen" Archiviert 2016-03-04 bei der Wayback -Maschine. Siam J. Comput. 23, 4 (August 1994), 738-761.http://portal.acm.org/citation.cfm?id=182370 doi:10.1137/s0097539791194094
  7. ^ Goodrich & Tamassia (2006), S. 597–599.
  8. ^ a b Black, Paul E.; Stewart, Rob (2. November 2020). "Wörterbuch". Wörterbuch von Algorithmen und Datenstrukturen. Abgerufen 26. Januar 2022.
  9. ^ Goodrich & Tamassia (2006), S. 389–397.
  10. ^ "Wann sollte ich eine Hash -Tabelle anstelle einer Assoziationsliste verwenden?". Lisp-Faq/Part2. 1996-02-20.
  11. ^ Klammer, F.; Mazzolini, L. (2006), "Pathfinders for Associative Maps", Ext. Abstracts GIS-L 2006, Gis-I, S. 71–74.
  12. ^ Joel Adams und Larry Nyhoff."Bäume in STL". Zitat: "Die Standard -Vorlagenbibliothek ... einige seiner Container - die Set <T>, MAP <T1, T2>, Multiset <T> und Multimap <T1, T2> Vorlagen - werden im Allgemeinen unter Verwendung eines Spezialisten erstellt So'ne Art selbstausgleichender binärer Suchbaum genannt Rot -Schwarz -Baum. "
  13. ^ Knuth, Donald (1998). Die Kunst der Computerprogrammierung. Vol. 3: Sortieren und Suchen (2. Aufl.). Addison-Wesley. S. 513–558. ISBN 0-201-89685-0.
  14. ^ Probst, Mark (2010-04-30). "Linear gegen binäre Suche". Abgerufen 2016-11-20.
  15. ^ Alvarez, Victor; Richter, Stefan; Chen, Xiao; Dittrich, Jens (April 2015). "Ein Vergleich von adaptiven Radixbäumen und Hash -Tischen". 2015 IEEE 31. Internationale Konferenz für Daten Engineering. Seoul, Südkorea: IEEE: 1227–1238. doi:10.1109/icde.2015.7113370. ISBN 978-1-4799-7964-6. S2CID 17170456.
  16. ^ "std :: map". en.cppreference.com.
  17. ^ "Ordnungswesensklasse (System.Collections.Specialized)". Frau Docs.
  18. ^ "Sammlungen - Containerdatenatypen - Python 3.9.0A3 Dokumentation". docs.python.org.
  19. ^ Dimitris Fasarakis Hilliard. "Dictionary - Wie erinnert sich Pythons geordneter Elemente, die eingefügt wurden?". Paketüberfluss.
  20. ^ Dimitris Fasarakis Hilliard. "Werden Wörterbücher in Python 3.6+ bestellt?". Paketüberfluss.
  21. ^ "Dictionary <tKey, TVAlue> Klasse".Msdn.
  22. ^ "System.generics.collections.tdictionary - RAD Studio API -Dokumentation". docwiki.embarcadero.com. Abgerufen 2017-04-18.
  23. ^ "Assoziative Arrays, die D -Programmiersprache".Digital Mars.
  24. ^ "Programmierleitfaden für Archive und Serialisierungen", Apple Inc., 2012

Externe Links