Mehr Infos zu Python-Dictionaries

Im ersten Teil zum Thema Dictionaries ging es um die Grundlagen. Im zweiten Teil möchte ich in dieses Thema tiefer eintauchen.

Dictionaries erstellen

Wie im ersten Teil dargestellt, kann man ein Dictionary mithilfe geschweifter Klammern oder mit der Funktion dict() erstellen.

a = {'Spain': 'Madrid', 'Germany': 'Berlin'}  # dict literal
b = dict(Spain='Madrid', Germany='Berlin')  # dict constructor

Das ist richtig, aber es gibt noch mehr Wege, wie nachfolgender Code zeigt:

c = dict([('Spain', 'Madrid'), ('Germany', 'Berlin')])
d = dict({'Spain': 'Madrid', 'Germany': 'Berlin'})

Im Fall ‚c‘ wird das Dictionary aus einer Liste (mit Tupel) gebildet. Im Fall ‚d‘ bildet ein anderes Dictionary die Grundlage für das neue Dictionary. Alle diese Dictionaries sind gleich, was nachfolgender Code beweist:

print(a == b == c == d)  # -> True

Die Reihenfolge der Elemente ist dabei unerheblich. Würde man die Anordnung der Schlüssel-Wert-Paare im Falle ‚d‘ verändern, würde sich nichts ändern:

d = dict({'Germany': 'Berlin', 'Spain': 'Madrid'})
print(a == b == c == d)  # -> True

Für das Erzeugen eines Dictionary kann auch eine Dictionary Comprehension (kurz: Dict Comprehension oder dictcomp) genutzt werden.

Das klassische Lehrbuchbeispiel sieht wie folgt aus:

towns = ['Manchester', 'Liverpool', 'Bristol']

towns_dict = {a: len(a) for a in towns}

print(towns_dict)
# -> {'Liverpool': 9, 'Manchester': 10, 'Bristol': 7}

Ausgehend von einer Liste mit Städten, wird hier ein Dictionary erstellt, das als Schlüssel die Städtenamen und als Werte die Länge der Städtenamen enthält.

Das neue Dictionary mit Städtenamen ließen sich noch weiter eingrenzen, zum Beispiel auf Namen, die weniger als zehn Zeichen haben:

towns_dict = {a: len(a) for a in towns if len(a) < 10}
print(towns_dict2)
# -> {'Liverpool': 9, 'Bristol': 7}

Und wenn man zusätzlich nur jene Städte haben möchte, die mit einem „B“ beginnen, ließe sich dies wie folgt realisieren:

towns_dict3 = {a: len(a) for a in towns if len(a) < 10 and a[0] == 'B'}
print(towns_dict)
# -> {'Bristol': 7}

Und noch ein weitere Beispiel: Eine Liste, die Tupel mit Staaten und deren Hauptstädte enthält soll in ein Dictionary konvertiert werden:

capitals = [('Spain', 'Madrid'), ('Germany', 'Berlin'), ('Austria', 'Vienna')]

capitals_dict = {country: capital for capital, country in capitals}

for (key, values) in capitals_dict.items():
        print(f"{key} is the capital of {values}.")

Madrid is the capital of Spain.
Berlin is the capital of Germany.
Vienna is the capital of Austria.

Hashable, Hash-Werte

Die Schlüssel, nicht aber die Werte, müssen hashable sein. Oder anders ausgedrückt: Es muss möglich sein, aus ihnen einen Hash-Wert zu bilden. Dabei handelt es sich um einen Wert, der sich innerhalb des Gültigkeitsbereichs (scope) nicht ändert. Für das Erzeugen eines Hash-Wertes steht die built-in-Funktion hash() zur Verfügung.

>>> hash('Bodo')
524564108850686177
>>> hash('22.7')
-7547384886550110071
>>> hash(('Spain', 'Madrid'))
6467689980226118510

Man kann sich merken: Unveränderbare Datentypen (immutable types) sind hashable.

Dies ist aber hinsichtlich der Tupels mit einer kleinen Einschränkung zu versehen. Bei einem Tupel handelt es sich zwar ebenfalls um einen unveränderbaren Datentyp, aber hier gilt, dass alle Elemente des Tupels hashable sein müssen, damit auch hinsichtlich des Tupels ein Hashwert gebildet werden kann. Daher funktioniert zwar folgender Code…

>>> hash((('Spain', 'Madrid'), ('Germany', 'Berlin')))
-1382653587324135590

..aber folgende Zeile verursacht eine Fehlermeldung:

>>> hash((('Spain', 'Madrid'), {'Germany': 'Berlin'}))
Traceback (most recent call last):
  File "<pyshell#22>", line 1, in <module>
    hash((('Spain', 'Madrid'), {'Germany': 'Berlin'}))
TypeError: unhashable type: 'dict'

Denn hier haben wir ein Tupel, welches ein Tupel und ein Dictionary zum Inhalt hat. Letzteres ist veränderbar, was bedeutet, dass kein Hash-Wert gebildet werden kann. Gleiches würde beispielsweise auch für Sets gelten:

>>> hash({'Regensburg', 'Fulda', 'Augsburg'})
Traceback (most recent call last):
  File "<pyshell#23>", line 1, in <module>
    hash({'Regensburg', 'Fulda', 'Augsburg'})
TypeError: unhashable type: 'set'

Hinweis: Nicht irritieren lassen. Für Sets werden ebenfalls geschweifte Klammern verwendet.

Kommen wir nach diesem Exkurs nun aber wieder zurück zu den Dictionaries.

Zusammen mit dem Begriff „Dictionary“ trifft man auf die Bezeichnung Hashtabelle (Hash Table). Hier sollte man sich nicht irritieren lassen. Wenn von einer Hashtabelle die Rede ist, meint man in der Regel ein Dictionary. Beide Begriffe werden synonym verwendet. Oder anders ausgedrückt: Der Datentyp Dictionary stellt in Python die Implementierung einer Hashtabelle dar.

Eine Hashtabelle hat Schlüssel-Wert-Paare, wobei der Schlüssel unter Verwendung einer Hash-Funktion gebildet wurde.

Geschwindigkeit, Big-O

Wenn man mit dem in-Operator in einer Liste nach einem Element sucht, wird im Hintergrund eine lineare Suche durchgeführt. Dies bedeutet zwangsläufig, dass die Suche sich proportional zur Anzahl der Elemente verlängert.

Bei einem Dictionary kommt hingegen ein Hash-Algorithmus zum Einsatz. Dies führt dazu, das die Suchzeit nahezu unverändert bleibt, gleich welche Anzahl von Schlüssel-Wert-Paaren vorhanden ist (Big-O-Notation: O(1)). Etwas anderes mag dann gelten, wenn der Hash-Algorithmus schlecht implementiert wurde und dies zu einer Reihe von Kollisionen führt.

Zuletzt aktualisiert am 7. Januar 2022