Wörterbücher und Hash-Tabellen: Ein vollständiger Leitfaden für unerfahrene Entwickler

Was ist ein Wörterbuch?

Ein Wörterbuch (dictionary, map, associative array) ist eine Datenstruktur, die Schlüssel-Wert-Paare speichert. Jedem eindeutigen Schlüssel ist ein bestimmter Wert zugeordnet. Es ist wie ein gewöhnliches Wörterbuch, in dem ein Wort (Schlüssel) mit seiner Definition (Bedeutung) verknüpft ist.

In Python sehen Wörterbücher so aus:

student = {
    "name": "Anna",
    "age": 22,
    "specialty": "Programming"
}

print(student["name"])  # Auszug: Anna

JavaScript verwendet eine ähnliche Syntax:

const student = {
    name: "Anna",
    age: 22,
    specialty: "Programming"
};

console.log(student.name);  // Auszug: Anna

Grundlegende Operationen mit Wörterbüchern

Elemente hinzufügen und ändern

# Python
grades = {}
grades["Mathematics"] = 5
grades["Physics"] = 4
grades["Mathematics"] = 5  # Änderung eines bestehenden Wertes

print(grades)  # {'Mathematik': 5, 'Physik': 4}4}

Werte erhalten

# Direkter Aufruf (führt zu einem Fehler, wenn der Schlüssel nicht vorhanden ist)
print(grades["Mathematics"])  # 5

# Sicherer Empfang mit Standardwert
print(grades.get("Chemistry", 0))  # 0 (kein Schlüssel, Standardwert wird zurückgegeben)

Elemente entfernen

del grades["Physics"]  # Löscht ein Schlüssel-Wert-Paar

# Oder mit Hilfe von pop (gibt den entfernten Wert zurück)
math_grade = grades.pop("Mathematics")

Überprüfung des Vorhandenseins des Schlüssels

if "Physics" in grades:
    print("Physics grade is")
else:
    print("No rating")

Was ist eine Hashtabelle?

Eine Hash-Tabelle ist eine Möglichkeit, ein Wörterbuch "unter der Haube" zu implementieren. Dies ist die Magie, die es Wörterbüchern ermöglicht, sehr schnell zu arbeiten.

Wie funktioniert eine Hash-Tabelle?

Wenn Sie ein Element zum Wörterbuch hinzufügen, geschieht Folgendes:

1. Schlüssel-Hashing: Der Schlüssel wird mit einer speziellen Funktion in eine Zahl (Hash-Code) umgewandelt

2. Positionsbestimmung: basierend auf dem Hash-Code wird der Index im Array berechnet

3. Speichern des Wertes: das Schlüssel-Wert-Paar wird unter diesem Index gespeichert

# Vereinfachtes Beispiel einer Hash-Funktion
def simple_hash(key, table_size):
    return sum(ord(char) for char in key) % table_size

# Für Schlüssel "cat" und Tabellengröße 10
hash_value = simple_hash("cat", 10)  # Gibt eine Zahl von 0 bis 9 zurück

Kollisionen

Manchmal können verschiedene Schlüssel den gleichen Hash ergeben. Dies wird als Kollision bezeichnet. Es gibt mehrere Möglichkeiten, sie zu lösen:

Kettenmethode: Wenn zwei Paare den gleichen Hash haben, werden sie als Liste unter einem Index gespeichert.

Offene Adressierung: Wenn die Zelle besetzt ist, wird die nächste freie Zelle gesucht.

Komplexität der Operationen

Einer der Hauptvorteile von Wörterbüchern ist die Arbeitsgeschwindigkeit:

• Element hinzufügen: O(1) im Durchschnitt

• Suche nach Element: O(1) im Durchschnitt

• Element entfernen: O(1) im Durchschnitt

Dies bedeutet, dass die Ausführungszeit der Operation nicht von der Anzahl der Elemente im Wörterbuch abhängt. Zum Vergleich: Die Suche in der Liste erfordert O(n) Zeit — jedes Element muss überprüft werden.

Praktische Anwendungsbeispiele

Berechnung der Häufigkeit von Elementen

text = "hello world"
letter_count = {}

for letter in text:
    if letter in letter_count:
        letter_count[letter] += 1
    else:
        letter_count[letter] = 1

print(letter_count)
# {'h': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1}

Eine elegantere Möglichkeit mit get():

text = "hello world"
letter_count = {}

for letter in text:
    letter_count[letter] = letter_count.get(letter, 0) + 1

Datengruppierung

students = [
    {"name": "Anna", "group": "A"},
    {"name": "Ivan", "group": "B"},
    {"name": "Maria", "group": "A"},
]

groups = {}
for student in students:
    group_name = student["group"]
    if group_name not in groups:
        groups[group_name] = []
    groups[group_name].append(student["name"])

print(groups)
# {'A': ['Anna', 'Maria'], 'B': ['Ivan']}

Zwischenspeichern von Ergebnissen

def fibonacci(n, cache={}):
    if n in cache:
        return cache[n]
    
    if n <= 1:
        return n
    
    result = fibonacci(n-1, cache) + fibonacci(n-2, cache)
    cache[n] = result
    return result

print(fibonacci(100))  # Wird dank Caching sehr schnell berechnet

Wann verwendet man Wörterbücher?

Wörterbücher sind ideal für:

• Speichern von Einstellungen und Konfigurationen

• Berechnung der Häufigkeit von Elementen

• Schnelle Suche nach eindeutiger Kennung

• Gruppierung und Aggregation von Daten

• Zwischenspeicherung von Berechnungen

• Darstellung von Graphen (Adjazenzliste)

Wichtige Merkmale

Die Schlüssel müssen unveränderlich sein: In Python können Schlüssel Zeichenfolgen, Zahlen, Tupel sein, aber keine Listen oder andere Wörterbücher.

# Richtig
valid_dict = {
    "name": "value",
    42: "value",
    (1, 2): "value"
}

# Fehler! Listen sind änderbar# invalid_dict = {[1, 2]: "value"}

Reihenfolge der Elemente: In Python 3.7+ behalten Wörterbücher die Reihenfolge bei, in der Elemente hinzugefügt werden, aber es lohnt sich nur, sich darauf zu verlassen, wenn die Reihenfolge wirklich wichtig ist.

Produktivität: Wörterbücher verbrauchen mehr Speicher als Listen, gleichen dies jedoch durch Zugriffsgeschwindigkeit aus.

Befund

Wörterbücher und Hash-Tabellen sind grundlegende Datenstrukturen, die jeder Entwickler verstehen sollte. Sie ermöglichen es, Daten effizient zu organisieren und viele praktische Probleme zu lösen. Wenn Sie verstehen, wie sie funktionieren, können Sie schnelleren und effizienteren Code schreiben.

Beginnen Sie, Wörterbücher in Ihren Projekten zu verwenden, und Sie werden schnell ihre Leistungsfähigkeit und Benutzerfreundlichkeit zu schätzen wissen. Üben Sie mit einfachen Aufgaben, machen Sie sie nach und nach komplizierter, und bald wird die Arbeit mit Wörterbüchern für Sie selbstverständlich sein.

Theorie ist großartig, aber wahres Verständnis kommt durch Übung. In der App Kodik Es erwarten Sie Hunderte von Programmieraufgaben mit unterschiedlichen Schwierigkeitsgraden, einschließlich Übungen zur Arbeit mit Wörterbüchern, Hash-Tabellen und anderen Datenstrukturen. Lösen Sie die Aufgaben in einem für Sie angenehmen Tempo und verfolgen Sie Ihren Fortschritt!

Und wir haben auch eine lebendige Community in Telegram! Hier helfen erfahrene Entwickler Anfängern, teilen nützliche Materialien, diskutieren interessante Aufgaben und kommunizieren einfach über Programmierthemen. Die Atmosphäre ist freundlich und unterstützend — jede Frage ist wichtig und niemand wird unbeantwortet bleiben. Schließen Sie sich uns an! 👋