Das Dictionary ist neben der Liste einer der grundlegenden Container-Datentypen, die in den meisten Programmiersprachen vorkommen. Manchmal wird es auch Map, Mapping oder Associative Array genannt.

Ein Dictionary ordnet jedem möglichen Schlüssel (key) maximal einen Wert (value) zu. Die folgenden Operationen werden mindestens unterstützt:

• lookup(key): gibt den zu key zugeordneten Wert zurück
• insert(key, value): definiert eine neue Zuordnung (eine bereits existierende Zuordnung wird überschrieben)
• remove(key): entfernt eine Zuordnung

Eine einfache Möglichkeit, in Python selber ein Dictionary zu implementieren, wäre eine Liste von Tupeln (key, value) zu speichern. Ein Tupel ist nichts anderes als eine unveränderliche Liste und wird (fast) immer in runde Klammern eingebettet.

Wenn wir möchten, dass unsere TupelListe die Python Syntax mit eckigen Klammern unterstützt, verwenden wir für die obigen Operationen die folgenden Special Method Names:

• Lookup: __getitem__(key)
• Insert: __setitem__(key, value)
• Remove: __delitem__(key)

Deren Spezifikation besagt, dass Lookup und Remove einen KeyError auslösen sollen, wenn der Schlüssel nicht existiert.

class TupelList:
    """A linear mapping type using list of (key, value) tuples."""
    def __init__(self):
        self._tuples = []
 
    def _finditem(self, key):
        """Returns the index of key, otherwise raises KeyError."""
        for index, (k, _) in enumerate(self._tuples):
            if key == k:
                return index
        raise KeyError
 
    def __getitem__(self, key):
        return self._tuples[self._finditem(key)][1]
 
    def __delitem__(self, key):
        return self._tuples.pop(self._finditem(key))[1]
 
    def __setitem__(self, key, value):
        try:
            # replace existing mapping
            self._tuples[self._finditem(key)] = (key, value)
        except KeyError:
            # add new mapping
            self._tuples.append((key, value))
 
map = TupelList()       # calls __init__
map['one'] = 42         # calls __setitem__
map['two'] = 21
 
print(map['one'])       # calls __getitem__
map['one'] = 'foobar'
print(map['one'])  

Die Tupel-Liste funktioniert, aber ist sie auch schnell? Wir machen eine kleine Messung:

def perf_test(map_type):
    import time, random
    # Measure how many mappings can be inserted, take no longer than 10s
    elapsed = 0
    count = 10 # start with 100 mappings
    while elapsed < 1:
        map = map_type()
        count = count * 10
        start = time.time()
        for i in range(count):
            key = random.randint(0, 1e6)
            map[key] = str(key)
            assert map[key] == str(key)
        elapsed = time.time() - start
        time_per_op = elapsed / count
        print(f"{map_type.__name__}: N={count:7}  Time per Op: {time_per_op:2.1e}")
 
perf_test(TupelList)

Output:

TupelList: N=   100  Time per Op: 5.4e-06
TupelList: N=  1000  Time per Op: 2.9e-05
TupelList: N= 10000  Time per Op: 2.5e-04

Die Zeit, um eine einzelne Zuordnung abzurufen wächst also linear mit der Anzahl Zuordnungen - wir sagen auch, dass die Lookup-Operation eine Laufzeit-Komplexität von $\mathcal{O}(n)$ hat.

Implementiere deine eigene Tupel-Liste und miss die Zeit für Lookup auf deinem Computer!

Natürlich möchten wir schneller sein als linear - zum Glück erinnern wir uns an die Informatik 1 und die Binärsuche!

Falls die verwendeten Schlüssel miteinander vergleichbar sind, könnten wir die Tupel-Liste ja sortieren, der Zugriff sollte dementsprechend schneller sein. Mathematiker sprechen auch davon, dass eine Totalordnung über die Schlüssel besteht. In Python ist dies der Fall, wenn wir für die Schlüssel Zahlen oder Strings (lexikographische Ordnung) verwenden, oder wenn die Schlüssel die Spezial-Funktionen für die Ordnung aufweisen.

Implementiere eine class SortedTupelList - Hinweise:

• Wir können von TupelList erben: class SortedTupelList(TupelList) um einigen Code wiederzuverwenden:
  • Die private Methode _finditem(key) muss angepasst werden um die Binärsuche zu implementieren.
  • In __getitem__ und __delitem__ bleiben sich gleich und müssen nicht angepasst werden.
• In __setitem__ benötigen wir den Einfüge-Index, falls _finditem nichts findet. Dafür gibt es verschiedene Möglichkeiten..

Führe jetzt eine Zeitmessung durch und vergleiche!

class SortedTupelList(TupelList):
    """A logarithmic mapping type using a sorted list of (key, value) tuples."""
    # Override _finditem to use binary search
    def _finditem(self, key, raise_on_notfound=True):
        """Returns the list index of key if it is present. Otherwise, 
           either raises KeyError or returns the insertion point."""
        left = 0
        right = len(self._tuples) - 1
        while left <= right:
            middle = (left + right) // 2
            k = self._tuples[middle][0]
            if key < k:
                right = middle - 1
            elif k < key:
                left = middle + 1 
            else:  # k == key
                return middle
        if raise_on_notfound:
            raise KeyError
        return left  # Insertion point
 
    # __getitem__ and __delitem__ are inherited as is, but
    # for __setitem__, we need to ensure that sorting is
    # maintained.
    def __setitem__(self, key, value):
        index = self._finditem(key, raise_on_notfound=False)
        if index < len(self._tuples) and self._tuples[index][0] == key:
            self._tuples[index] = (key, value)  # replace existing entry
        else:
            self._tuples.insert(index, (key, value))  # insert new entry

Können wir noch schneller sein als Binärsuche?

Binärsuche ist sehr viel schneller als lineare Suche: jedes Mal wenn wir die Anzahl Einträge quadrieren vergrössert sich die Zeit um einen konstanten Faktor. Mann kann auch sagen, dass die Zeit pro Lookup mit dem Logarithmus der Anzahl Einträge wächst, oder dass Lookup die Komplexität $\mathcal{O}(log(n))$ hat.

Allerdings wissen wir auch, dass der eigentliche Zugriff auf die zugrundeliegende Liste nicht von deren Grösse abhängt. Wenn wir den richtigen Index kennen würden, könnten wir den Zugriff in konstanter Zeit (oder $\mathcal{O}(1)$) schaffen. Dies wird mit einer Hashmap erreicht, indem der Index aus dem Key berechnet wird. Dazu wird für jedes Key-Objekt ein Hashwert (eine Ganzzahl) berechnet. Aus dem Hashwert wird der Index in der Tupel-Liste mittels hash % len(self.tuples) berechnet.

In Python können wir die eingebaute hash(object) Funktion verwenden, um für jedes Objekt einen Hashwert zu erhalten. Für die meisten Objekte ist dies ein Wert, der aus der internen Speicheradresse abgeleitet wird; für Typen, die __eq__ implementieren, wie beispielsweise Strings, basiert der Hashwert auf dem Inhalt, so dass zwei unterschiedliche String-Instanzen mit dem gleichen Inhalt trotzdem den gleichen Hashwert produzieren.

Natürlich kann es vorkommen, dass zwei unterschiedliche Keys denselben Hashwert produzieren, eine sogenannte Kollision. Wir müssen also beim Suchen sicherstellen, dass an der berechneten Adresse tatsächlich der gesuchte Key steht. Zur Behandlung von Kollisionen gibt es viele Möglichkeiten:

• Probing: In der Liste weiterzusuchen nach dem nächsten freien Slot.
  • … aber dann müssen wir bei Remove sicherstellen, dass die folgenden Elemente des Clusters wieder nach vorne gerückt werden.
• Chaining: Jedes Listenelement ist eine simple Tupel-Liste, die wir linear nach dem richtigen Key durchsuchen.

Um die Anzahl Kollisionen tief zu halten ist es wichtig, dass die Liste nie ganz gefüllt ist - die Tupel-Liste wird also bewusst grösser gewählt als nötig und bei Bedarf ein rehash ausgeführt: alle Einträge werden in eine neue, grössere Liste umgefüllt, wobei die Hashwerte dann neu berechnet werden müssen. Je nach gewähltem Faktor für die tolerierbare Kollisionszahl benötigt die Hashmap also mehr Speicher, um damit eine bessere Laufzeit zu erreichen.

Implementiere eine class HashMap.

Hinweise:

• wir können _tuples und __getitem__ wieder von TupelList erben.

class HashMap(TupelList):
    def __init__(self):
        self._tuples = [None] * 10  # The tuples (key, value).
        self._len = 0  # The number of elements we contain.
 
    def __len__(self):
        return len
 
    def _hash(self, key):
        return hash(key)  # Use Python's built-in hash function.
 
    def _index(self, key):
        return self._hash(key) % len(self._tuples)
 
    def _finditem(self, key, raise_on_notfound=True):
        """Returns (found, index) where found is True and index is the key's index it is present. Otherwise, 
           the index represents the index where key were to be inserted."""
        h = self._index(key)
 
        # Find the first matching or empty slot
        entry = self._tuples[h]
        while entry and entry[0] != key:
            h = (h + 1) % len(self._tuples)
            entry = self._tuples[h]
        if entry is None and raise_on_notfound:
            raise KeyError(key)
        return h
 
    # Any mappings that were shifted due to collision need to be moved to the gap.
    def __delitem__(self, key):
        index = self._finditem(key)
        v = self._tuples[index][1]
        self._tuples[index] = None
        self._len -= 1
        self.clean_up_after_delete(index)
        return v
 
    def clean_up_after_delete(self, index):
        """After a delete, we need to ensure that any subsequent entries that may have been 
           moved due to collisions are moved forward until we find another gap."""
        probe = index + 1
        while True:
            entry = self._tuples[probe]
            if entry is None:
                return # found a gap - we're done
            h = self._index(entry[0])
            if h <= index:
                # we found an entry that was moved
                self._tuples[index] = entry
                self._tuples[probe] = None
                index = probe
            probe = (probe + 1) % len(self._tuples)
 
    def __setitem__(self, key, value):
        index = self._finditem(key, raise_on_notfound=False)
        is_addition = self._tuples[index] is None
        self._tuples[index] = (key, value)
        if is_addition:
            self._len += 1
            self._attempt_rehash()
 
    def _attempt_rehash(self):
        """Rehashes the entire map if fullness reaches 50%. The capacity is doubled."""
        # Rehash if fullness is more than 50%
        if self._len > len(self._tuples) * 0.5:
            old_tuples = self._tuples
 
            # Re-insert all elements into twice as large list
            self._tuples = [None] * (len(old_tuples) * 2)  # Double the size!
            for entry in old_tuples:
                if entry:
                    index = self._finditem(entry[0], raise_on_notfound=False)
                    self._tuples[index] = entry