Hash-Datenstrukturen

Hash-Datenstrukturen ermöglichen schnellen Zugriff auf Werte.

In Python sind besonders wichtig:

• set
• frozenset
• dict

Hashbarkeit

Objekte, die in Hash-Strukturen als Schlüssel oder Set-Element verwendet werden, müssen stabil hashbar sein.

Der Grund: Wenn sich der Hashwert eines Objekts nach dem Einfügen ändern würde, könnte Python das Objekt nicht mehr zuverlässig finden.

Darum sind zum Beispiel Listen nicht als Set-Elemente oder Dictionary-Keys geeignet.

set

Ein Set ist eine ungeordnete, veränderliche Menge.

s = set([3, 5, 10])
s = {3, 5, 10}
t = {"H", "e", "l", "o", 3, 5}

Eigenschaften:

• ungeordnet
• veränderlich
• keine Duplikate
• Elemente müssen hashbar sein

Leeres Set

leeres_set = set()

Achtung:

not_a_set = {}

{} erzeugt ein leeres Dictionary, kein Set.

Mengenoperationen

a = t | s   # Union
b = t & s   # Schnittmenge
c = t - s   # Differenz
d = t ^ s   # symmetrische Differenz

Set verändern

t.add("x")
s.update([10, 37, 42])
t.remove("H")
res = "x" in t

in ist bei Sets typischerweise sehr effizient.

frozenset

Ein frozenset ist die unveränderliche Variante von set.

s = frozenset([3, 5, 10])
t = frozenset("Hello")

xy = s | t

Mengenoperationen erzeugen neue frozenset-Objekte.

dict

Ein Dictionary ist ein veränderlicher Key-Value-Speicher.

stock = {
    "name": "GOOG",
    "shares": 100,
    "price": 490.10
}

Eigenschaften:

• Zu einem Key gehört ein Value.
• Keys müssen hashbar sein.
• Values können beliebige Objekte sein.
• Zugriff erfolgt über den Key.

Zugriff

price = stock["price"]
name = stock["name"]

Wert ändern:

stock["shares"] = 75

Neuen Key einfügen:

stock["date"] = "June 7, 2007"

Key löschen:

del stock["name"]

Prüfen:

"name" in stock

Iteration

for k in stock.keys():
    print(k)

for v in stock.values():
    print(v)

for k, v in stock.items():
    print(k, v)

In der Praxis ist items() besonders nützlich, wenn Key und Value gemeinsam gebraucht werden.

Wann set, wann dict?

Merksatz

Sets beantworten „Ist es enthalten?“. Dictionaries beantworten „Welcher Wert gehört zu diesem Schlüssel?“.