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 Index string, was in der Praxis der häufigste Fall ist, 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 Index benutzt werden, für den entweder eine Ordnung oder eine Hashfunktion definiert ist. Im ersten Fall realisiert man das assoziative Array mit Hilfe eines Suchbaums, im zweiten Fall mit Hilfe einer Hashtabelle.

Zu den beiden obigen Zugriffsfunktionen treten in Python noch eine Funktion um zu testen, ob ein Schlüssel vorhanden ist, sowie die Möglichkeit, einen Schlüssel und die darunter gespeicherten Daten zu löschen:

   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

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.