Wie erstellst du deine eigene Implementierung des Wörterbuchs?

Um eine eigene Implementierung eines Wörterbuchs (Dictionary) in iOS mit Swift zu erstellen, kann man eine Datenstruktur auf Basis einer Hashtabelle verwenden. Die Hauptidee ist, Schlüssel-Wert-Paare in einem Array von Buckets zu speichern, wobei jeder Bucket eine Liste von Elementen mit demselben Hash-Code enthält (zur Kollisionsauflösung).

Beispiel für eine einfache Implementierung eines Wörterbuchs mit einem Array und Verkettungen:

struct MyDictionary<Key: Hashable, Value> {
    private typealias Element = (key: Key, value: Value)
    private var buckets: [[Element]]
    private let capacity: Int

    init(capacity: Int = 16) {
        self.capacity = capacity
        self.buckets = Array(repeating: [], count: capacity)
    }

    private func index(forKey key: Key) -> Int {
        return abs(key.hashValue) % capacity
    }

    mutating func set(value: Value, forKey key: Key) {
        let index = self.index(forKey: key)
        // Überprüfen, ob bereits ein Element mit diesem Schlüssel existiert
        if let i = buckets[index].firstIndex(where: { $0.key == key }) {
            buckets[index][i].value = value
        } else {
            buckets[index].append((key, value))
        }
    }

    func get(forKey key: Key) -> Value? {
        let index = self.index(forKey: key)
        return buckets[index].first(where: { $0.key == key })?.value
    }
}

// Verwendung:
var dict = MyDictionary<String, Int>()
dict.set(value: 42, forKey: "answer")
print(dict.get(forKey: "answer") ?? "not found")  // 42

Diese Art von Wörterbuch unterstützt grundlegende Operationen wie Einfügen und Suchen. Für eine fortgeschrittene Implementierung können Löschfunktionen, dynamische Erweiterung, verbesserte Kollisionsbehandlung usw. hinzugefügt werden.