Erzählen Sie von Hash-Tabellen und ihrem…

Die Hashtabelle (Hash-Map) ist eine Datenstruktur, die ein assoziatives Array implementiert, das Schlüssel auf Werte abbildet.

Funktionsprinzip:

Hashing: Für jeden Schlüssel wird ein Hash-Code berechnet – ein fester numerischer Wert mittels einer Hash-Funktion. Eine gute Hash-Funktion verteilt die Hash-Codes gleichmäßig über den gesamten Ausgabebereich.
Indexierung: Der berechnete Hash-Code wird verwendet, um den Index (Position) im Array zu bestimmen, an dem der entsprechende Wert gespeichert wird. Häufig ergibt hash(key) % array_size den endgültigen Index.
Speicherung: Im Array wird an dem berechneten Index ein Paar (Schlüssel, Wert) gespeichert.
Suche: Um einen Wert anhand des Schlüssels zu finden, wird der Hash-Code des Schlüssels erneut berechnet, der Index bestimmt, und an diesem Index wird der Wert extrahiert.
Kollisionen: Tritt auf, wenn verschiedene Schlüssel denselben Hash-Code haben. Es gibt verschiedene Methoden, um Kollisionen zu lösen:
- Kettenmethode (Separate Chaining): An jedem Array-Index wird eine Liste (oder eine andere Datenstruktur) gehalten, die alle Paare (Schlüssel, Wert) enthält, deren Hash-Codes zu diesem Index führen.
- Offene Adressierung (Open Addressing): Bei Kollisionen wird nach einem freien Platz im Array nach einer bestimmten Regel gesucht (lineares Sondieren, quadratisches Sondieren, doppelte Hashfunktion).

Vorteile:

Im Durchschnitt haben Einfüge-, Lösch- und Suchoperationen eine Komplexität von O(1), vorausgesetzt, die Hash-Funktion ist gut und Kollisionen sind selten.

Nachteile:

Der schlechteste Fall in der Leistung kann O(n) sein, wenn alle Schlüssel auf denselben Index gehasht werden (z.B. bei einer schlechten Hash-Funktion oder vielen Kollisionen).
Es wird zusätzlicher Speicher für das Array und möglicherweise für die Kollisionsauflösung benötigt.

In Swift sind Hash-Tabellen mit dem Typ Dictionary implementiert.

// Beispiel für die Verwendung von Dictionary in Swift
var myDictionary: [String: Int] = ["apple": 1, "banana": 2, "orange": 3]

// Zugriff über Schlüssel
let value = myDictionary["banana"] // Erhält Optional(2)

// Hinzufügen/Aktualisieren
myDictionary["grape"] = 4 // Fügt ein neues Paar hinzu
myDictionary["apple"] = 10 // Aktualisiert den Wert für den Schlüssel "apple"

// Entfernen
myDictionary["orange"] = nil // Entfernt das Paar mit dem Schlüssel "orange"

Erzählen Sie von Hash-Tabellen und ihrem grundlegenden Funktionsprinzip.