Как реализуешь кастомный Dictionary?

Реализация кастомного Dictionary в Swift

Чтобы реализовать кастомный Dictionary в Swift, необходимо создать структуру данных, которая поддерживает ключ-значение пары с эффективным доступом. Основные компоненты: хэш-таблица, обработка коллизий и соответствие протоколу Collection.

Базовая архитектура

struct CustomDictionary<Key: Hashable, Value> {
    private typealias Element = (key: Key, value: Value)
    private typealias Bucket = [Element]
    private var buckets: [Bucket]
    private(set) var count = 0
    
    private let initialCapacity: Int
    
    init(capacity: Int = 8) {
        self.initialCapacity = capacity
        self.buckets = Array<Bucket>(repeating: [], count: capacity)
    }
}

Ключевые методы реализации

1. Индекс по ключу

private func index(forKey key: Key) -> Int {
    let hashValue = abs(key.hashValue)
    return hashValue % buckets.count
}

2. Добавление и обновление значений

mutating func updateValue(_ value: Value, forKey key: Key) -> Value? {
    let index = self.index(forKey: key)
    
    // Поиск существующего ключа
    for (i, element) in buckets[index].enumerated() {
        if element.key == key {
            let oldValue = element.value
            buckets[index][i].value = value
            return oldValue
        }
    }
    
    // Добавление нового элемента
    buckets[index].append((key: key, value: value))
    count += 1
    
    // Рехеширование при необходимости
    if loadFactor > 0.75 {
        resize()
    }
    
    return nil
}

3. Получение значения

func value(forKey key: Key) -> Value? {
    let index = self.index(forKey: key)
    
    for element in buckets[index] {
        if element.key == key {
            return element.value
        }
    }
    
    return nil
}

4. Удаление элемента

mutating func removeValue(forKey key: Key) -> Value? {
    let index = self.index(forKey: key)
    
    for (i, element) in buckets[index].enumerated() {
        if element.key == key {
            let removedValue = element.value
            buckets[index].remove(at: i)
            count -= 1
            return removedValue
        }
    }
    
    return nil
}

Обработка коллизий и рехеширование

Коэффициент загрузки

private var loadFactor: Double {
    return Double(count) / Double(buckets.count)
}

Рехеширование

private mutating func resize() {
    let oldBuckets = buckets
    buckets = Array<Bucket>(repeating: [], count: oldBuckets.count * 2)
    count = 0
    
    for bucket in oldBuckets {
        for element in bucket {
            updateValue(element.value, forKey: element.key)
        }
    }
}

Соответствие протоколам

Последовательность (Sequence)

extension CustomDictionary: Sequence {
    func makeIterator() -> AnyIterator<(Key, Value)> {
        var bucketIndex = 0
        var elementIndex = 0
        
        return AnyIterator {
            while bucketIndex < self.buckets.count {
                if elementIndex < self.buckets[bucketIndex].count {
                    let element = self.buckets[bucketIndex][elementIndex]
                    elementIndex += 1
                    return (element.key, element.value)
                } else {
                    bucketIndex += 1
                    elementIndex = 0
                }
            }
            return nil
        }
    }
}

Subscript для удобного доступа

extension CustomDictionary {
    subscript(key: Key) -> Value? {
        get {
            return value(forKey: key)
        }
        set {
            if let value = newValue {
                updateValue(value, forKey: key)
            } else {
                removeValue(forKey: key)
            }
        }
    }
}

Оптимизации и особенности

1. Эффективность: Средняя сложность O(1) для операций поиска, вставки и удаления
2. Безопасность потоков: Базовая реализация не потокобезопасна, требует дополнительных механизмов
3. Память: Использует динамическое расширение для баланса между памятью и производительностью
4. Итерация: Поддержка for-in циклов через соответствие Sequence

Практическое использование

var myDict = CustomDictionary<String, Int>()
myDict["apple"] = 5
myDict["banana"] = 3

print(myDict["apple"]) // 5

for (key, value) in myDict {
    print("\(key): \(value)")
}

myDict["apple"] = nil // Удаление

Сравнение с системным Dictionary

• Преимущества кастомной реализации: Полный контроль над внутренней структурой, возможность специализированных оптимизаций
• Недостатки: Отсутствие многих оптимизаций Swift Runtime, возможная менее эффективная работа с памятью

Такая реализация демонстрирует понимание структур данных, хэширования, протоколо-ориентированного программирования и системы типов Swift. В production-среде обычно предпочтительнее использовать стандартный Dictionary, но кастомная реализация полезна для специализированных случаев и образовательных целей.