Assoziative Arrays

under construction

Datenstruktur-Dreieck für assoziative Arrays

Assoziative Arrays sind eine der wichtigsten Anwendungen für Suchalgorithmen und Suchbäume. Bevor wir dies im Detail erklären, wollen wir jedoch noch einmal einen Blick auf das Datenstruktur-Dreieck aus der ersten Vorlesung werfen, das am Beispiel der assoziativen Arrays sehr schön illustriert werden kann. Wir zeigen es hier noch einmal:

Wir erinnern daran, dass man zwei Ecken des Dreicks wählen muss, um eine Datenstruktur zu definieren. Wir werden im Folgenden zeigen, wie Python durch Festlegen der erlaubten Operationen und deren Bedeutung den abstrakten Datentyp "Assoziatives Array" definiert, wie durch Festlegen eines Speicherlayouts und der Bedeutung der gespeicherten Entitäten das Standard-Datenformat "JSON" definiert ist, und wie durch effiziente Implementation der festgelegten Operationen mit jeweils passendem Speicherlayout die Datenstruktur auf unterschiedliche Arten realisiert werden kann.

Definition des abstrakten Datentyps

Assoziative Arrays können genau wie gewöhnliche Arrays benutzt werden, sie unterstützen also den lesenden und schreibenden Zugriff über den Indexoperator a[...]. Im Unterschied zum gewöhnlichen Array, wo die Indizes ganze Zahlen im Bereich <math> i \in 0 \ldots N-1</math> sein muss, kann der Typ der Indizes jetzt beliebig sein. Wir verwenden dafür den Begriff "Schlüssel" (engl.: key):

   a[key] = value   # Speichern des Wertes 'value' unter dem Schlüssel 'key'
   value  = a[key]  # Auslesen des unter dem Schlüssel 'key' gespeicherten Wertes

Eine typische Anwendung ist ein Wörterbuch

   x = toEnglish['Baum']   # ergibt 'tree'

In diesem Fall ist der Typ des Schlüssels string. Dies ist in der Praxis der häufigste Fall, weshalb assoziative Arrays oft als Dictionary bezeichnet werden (so auch in Python, hier heißt der Typ dict). Im allgemeinen kann aber jeder Typ als Schlüssel benutzt werden, der eine der folgenden Anforderungen erfüllt:

unterstützte Vergleichsoperationen für Schlüssel	mögliche Implementation des assoziativen Arrays
Identitätstest: key1 == key2	sequentielle Suche
Ordnungsrelation: key1 < key2	Suchbaum (auch binäre Suche, falls keine neuen Schlüssel eingefügt und keine gelöscht werden)
Identitätstest und Hashfunktion: key1 == key2 und hash(key1) == hash(key2)	Hashtabelle

Wenn über die Schlüssel mehr bekannt ist (eine Ordnungsrelation oder eine Hashfunktion statt einer bloßen Indentitätsprüfung), kann man entsprechend bessere Datenstrukturen (Suchbäume oder Hashtabellen statt sequentieller Suche) verwenden, deren Zugriffsfunktionen wesentlich effizienter sind (sequentielle Suche ist ja nur in O(N)).

Zu den beiden obigen Zugriffsfunktionen treten in Python noch zwei weiter hinzu: eine um zu testen, ob ein Schlüssel vorhanden ist, sowie eine, mit der man einen Schlüssel und die darunter gespeicherten Daten löschen kann:

   if a.has_key(key): # Testen, ob Schlüssel 'key' existiert
       del a[key]     # Schlüssel 'key' und zugehörige Daten aus dem Array entfernen

Die Syntax der aufgeführten Funktionen gilt für die Benutzung eines assoziativen Arrays. Will man einen solchen Datentyp implementieren, muss man die entsprechende Funktionalität als Methoden der jeweiligen Klasse zur Verfügung stellen. Der Python-Interpreter transformiert den Index-/Schlüsselzugriff a[key] und den del-Operator automatisch in Aufrufe der jeweiligen Methode, wie die folgende Tabelle verdeutlicht. Zur vollständigen Definition der Bedeutung der einzelnen Operationen (wie vom Datenstruktur-Dreieck gefordert) gehört außerdem die Spezifikation des Verhaltens im Fehlerfall (wenn z.B. ein angeforderter Schlüssel nicht existiert).

Operation	von Python intern generierter Methodenaufruf	zu implementierende Methodensignatur	Bedeutung
a[key] = value	a.__setitem__(key, value)	def __setitem__(self, key, value):	* wenn key bereits existiert: ersetze die zugehörigen Daten * wenn key noch nicht existiert: lege einen neuen Eintrag an
value = a[key]	a.__getitem__(key)	def __getitem__(self, key):	* wenn key existiert: gebe die zugehörigen Daten zurück * wenn key nicht existiert: löse KeyError-Exception aus
a.has_key(key)	a.has_key(key)	def __has_key__(self, key):	gibt True zurück wenn key existiert, sonst False
del a[key]	a.__delitem__(key)	def __delitem__(self, key):	* wenn key existiert: entferne diesen Schlüssel und die zugehörigen Daten * wenn key nicht existiert: löse KeyError-Exception aus

Das JSON-Datenformat

siehe [1]

Realisierung des assoziativen Arrays als Suchbaum

Wenn für den Indextyp des assoziativen Arrays eine Ordnung definiert ist (wenn also i1 < i2 oder cmp(i1, i2) unterstützt werden), kann man das Indexierungsproblem auf das Suchproblem zurückführen, indem man die Indizes als Suchschlüssel verwendet. Im einfachsten Fall kann dies mit sequentieller Suche realisiert werden: Man verwendet ein gewöhnliches Array, dessen Einträge (Schlüssel, Daten)-Paare sind. Bei der Frage nach einem Schlüssel wird das betreffende Paar gesucht und die darin gespeicherten Daten zurückgegeben. Dies erfordert aber einen Suchaufwand in O(n). Effizienter geht es mit einem Suchbaum. Die Datenstruktur des Suchbaums muss dafür so erweitert werden, dass zu jedem Schlüssel (=Index) weitere Informationen gespeichert werden können (nämlich der Inhalt des indexierten Feldes). Man erweitert die Node-Klasse um ein Feld "data":

   class Node:
       def __init__(self, key, data = None):
           self.key = key
           self.data = data
           self.left = self.right = None

Dann kann man eine Klasse AssociativeArray realisieren, die die Indexoperationen intern mit Hilfe der Baumsuche implementiert. In Python wird der Zugriffsoperator [ ] für eine Datenstruktur (also innerhalb einer Klasse) wie folgt implementiert (vgl. die Python Docs zum Thema):

       def __setitem__(self, key, value)

so dass im Programmtext dann folgende Syntax möglich ist: a[key] = value (schreibender Zugriff auf a[key]). Analog wird der lesende Zugriff value = a[key] wie folgt umgesetzt:

       def __getitem__(self, key, value)

Der Konstruktor der Klasse AssociativeArray initialisiert einen leeren Suchbaum:

   class AssociativeArray:
       def __init__(self):
           self.root = None
           self.size = 0

Die Funktion __setitem__ schaut nach, ob ein Eintrag mit dem betreffenden Index bereits existiert. Wenn ja, werden seine Daten mit den neuen Daten überschrieben, andernfalls wird ein neuer Eintrag angelegt. Intern werden dazu die bereits bekannten Funktionen treeSearch und treeInsert verwendet (siehe Abschnitt Suchbäume):

       def __setitem__(self, index, data):
            node = treeSearch(self.root, index)
            if node is None:
                self.root = treeInsert(self.root, index)
                self.size += 1
                node = treeSearch(self.root, index) 
            node.data = data

(Eine geschicktere Implementation würde natürlich die wiederholten Aufrufe von treeSearch und treeInsert eliminieren. Dies ändert aber nichts an der Komplexität der Funktion.) Die Funktion __getitem__ sucht ebenfalls einen Eintrag mit dem gegebenen Index. Wenn er gefunden wird, gibt sie die zugehörigen Daten zurück, andernfalls eine Fehlermeldung:

       def __getitem__(self, index):
           node = treeSearch(self.root, index)
           if node is None:
               raise KeyError(index)
           else:
               return node.data

Die Indexoperationen haben bei der Realisierung mit Baumsuche eine Komplexität in O(log n).

Ein wichtiges Beispiel für ein assoziatives Array, das auf diese Weise realisiert wurde, ist die C++ Standardklasse std::map.