Dictionaries und Maps

Wie funktionieren Dictionaries und Maps?

Assoziative Datenstrukturen: Schlüssel und Wert

Stell dir ein klassisches Telefonbuch vor: Du suchst nicht nach der "fünften Nummer im Buch", sondern nach einem bestimmten Namen, um die dazugehörige Telefonnummer zu finden. Genau dieses Prinzip nutzen Dictionaries (in Python) oder Maps (in Java/JavaScript). Sie gehören zu den assoziativen Datenstrukturen.

Aus deinem Vorwissen kennst du bereits Arrays und Listen, die Elemente über einen fortlaufenden numerischen Index (0, 1, 2...) abspeichern. Dictionaries verwenden stattdessen Schlüssel-Wert-Paare (Key-Value Pairs).

Der Schlüssel (Key) muss zwingend eindeutig sein und dient als Suchbegriff.
Der Wert (Value) sind die eigentlichen Daten, die mit diesem Schlüssel verknüpft sind.

# Ein Dictionary, das Hauptstädte (Wert) ihren Ländern (Schlüssel) zuordnet
hauptstaedte = {
    "Deutschland": "Berlin",
    "Frankreich": "Paris",
    "Italien": "Rom"
}

# Direkter Zugriff auf den Wert über den Schlüssel
print(hauptstaedte["Frankreich"]) # Ausgabe: Paris

Der Geschwindigkeitsvorteil durch Hashing

Du kennst bereits Hash-Funktionen und die Big-O-Notation. Dictionaries kombinieren dieses Wissen, um extrem schnelle Zugriffszeiten zu erreichen.

Wie die Grafik veranschaulicht, wird ein neuer Schlüssel intern durch eine Hash-Funktion geschickt. Der daraus resultierende Hash-Wert bestimmt den exakten Speicherort des zugehörigen Wertes. Wenn du später nach diesem Schlüssel suchst, berechnet das System den Hash-Wert erneut und springt direkt zur richtigen Speicheradresse.

Dadurch entfällt das zeitraubende Durchsuchen aller Elemente. Das Suchen, Einfügen und Löschen in einem Dictionary hat daher eine durchschnittliche Zeitkomplexität von O(1) (konstante Zeit). Selbst wenn dein Dictionary Millionen von Einträgen enthält, dauert der Zugriff auf einen bestimmten Wert immer ungefähr gleich lang.

Dictionaries und Maps — dec-software-engineering-data-structures-and-algorithms-fundamental-data-structures-dictionaries-and-maps_page1.svg

Wie werden Dictionaries in der Praxis programmiert und eingesetzt?

Daten verwalten: Einfügen und Auslesen

Die programmiertechnische Nutzung von Dictionaries ist auf schnelle Lese- und Schreibzugriffe optimiert. Wenn du ein neues Element hinzufügst, gibst du einfach den neuen Schlüssel und den gewünschten Wert an. Beim Auslesen übergibst du den Schlüssel in eckigen Klammern.

# Ein leeres Dictionary erstellen
benutzer_daten = {}

# Einfügen (Insert) von Schlüssel-Wert-Paaren
benutzer_daten["u123"] = "Anna Schmitt"
benutzer_daten["u456"] = "Ben Weber"

# Auslesen (Search) eines Wertes
print(benutzer_daten["u123"]) # Ausgabe: Anna Schmitt

# Sicherer Zugriff: Prüfen, ob Schlüssel existiert
if "u999" in benutzer_daten:
    print(benutzer_daten["u999"])
else:
    print("Benutzer nicht gefunden.")

Daten pflegen: Aktualisieren und Löschen

Da jeder Schlüssel in einem Dictionary einzigartig sein muss, überschreibst du automatisch den alten Wert, wenn du einem bereits existierenden Schlüssel einen neuen Wert zuweist. Das Löschen von Einträgen erfolgt ebenfalls gezielt über den eindeutigen Schlüssel.

# Aktualisieren (Update) eines bestehenden Wertes
benutzer_daten["u123"] = "Anna Müller" # Nachname hat sich geändert
print(benutzer_daten["u123"]) # Ausgabe: Anna Müller

# Löschen (Delete) eines Eintrags
del benutzer_daten["u456"]
print(benutzer_daten) # Ausgabe: {'u123': 'Anna Müller'}

Praxisvergleich: Dictionaries vs. Listen (Arrays)

Wann nutzt du eine Liste und wann ein Dictionary? Die Wahl hängt von deinem spezifischen Problem ab:

Listen/Arrays sind ideal, wenn die Reihenfolge der Daten wichtig ist oder du alle Elemente nacheinander verarbeiten willst (z. B. eine Top-10-Highscore-Liste). Wenn du jedoch in einer unsortierten Liste nach einem bestimmten Element suchst, musst du im schlimmsten Fall alle Elemente überprüfen (O(n)).
Dictionaries glänzen, wenn du Daten über einen eindeutigen Bezeichner (wie eine ID, eine E-Mail-Adresse oder einen Namen) verknüpfst und blitzschnell abrufen musst (O(1)). Die Reihenfolge der Elemente spielt hier konzeptionell keine Rolle.

Anwendungsfall: Häufigkeiten zählen

Ein klassisches Szenario, in dem Dictionaries ihre Stärke gegenüber Listen ausspielen, ist das Zählen von Häufigkeiten. Stell dir vor, du möchtest zählen, wie oft jedes Wort in einem Text vorkommt. Das Wort dient als Schlüssel, die bisherige Anzahl als Wert.

text = "rot blau grün rot gelb blau rot"
wort_frequenz = {}

# Text in einzelne Wörter aufteilen und durchlaufen
for wort in text.split():
    if wort in wort_frequenz:
        wort_frequenz[wort] += 1 # Zähler erhöhen, wenn Wort bekannt
    else:
        wort_frequenz[wort] = 1  # Zähler auf 1 setzen, wenn Wort neu

print(wort_frequenz) 
# Ausgabe: {'rot': 3, 'blau': 2, 'grün': 1, 'gelb': 1}

Mit einer Liste müsstest du für jedes Wort die gesamte Liste durchsuchen, um den Zähler zu finden – mit einem Dictionary greifst du direkt auf den Zähler des jeweiligen Wortes zu.

Teste dein Wissen

Du entwickelst eine App zur Verwaltung von Server-IPs. Du möchtest Servernamen direkt ihren IP-Adressen zuordnen. Warum ist ein Dictionary hierfür besser geeignet als ein klassisches Array?