Как устроен Dictionary под капотом?

Устройство Dictionary в Swift

В Swift Dictionary — это высокооптимизированная хеш-таблица с открытой адресацией и линейным пробированием, обеспечивающая среднюю амиортизированную сложность O(1) для основных операций.

Основные концепции

Хеш-таблица с открытой адресацией

В основе лежит массив бакетов (buckets), где каждый бакет может содержать ключ-значение или быть пустым. В отличие от цепочек, здесь коллизии разрешаются поиском следующего доступного слота в самом массиве.

// Упрощенное представление структуры
struct Dictionary<Key: Hashable, Value> {
    private var buckets: [Bucket?]
    private var count: Int = 0
    
    enum Bucket {
        case filled(key: Key, value: Value)
        case deleted // Tombstone для удаленных элементов
    }
}

Ключевые механизмы

1. Хеширование и индексирование

Ключи должны соответствовать протоколу Hashable. Swift использует универсальное хеширование для защиты от DoS-атак:

let hashValue = key.hashValue
let index = abs(hashValue) % buckets.count

2. Разрешение коллизий - линейное пробирование

При коллизии Dictionary ищет следующий доступный бакет:

func findIndex(for key: Key) -> Int? {
    var index = initialIndex(for: key)
    while case let .filled(k, _) = buckets[index] {
        if k == key { return index }
        index = (index + 1) % buckets.count
    }
    return nil
}

3. Масштабирование и рехеширование

При достижении коэффициента заполнения (обычно ~75%) происходит увеличение емкости:

• Создается новый массив бакетов большего размера (обычно удвоение)
• Все элементы перехешируются и перераспределяются
• Tombstones (удаленные элементы) не переносятся

Особенности реализации Swift

Copy-on-Write оптимизация

Как и другие коллекции Swift, Dictionary использует COW для эффективного копирования:

var dict1 = ["a": 1, "b": 2]
var dict2 = dict1 // Одинаковый буфер, ссылочный счетчик увеличивается
dict2["c"] = 3 // Только здесь происходит реальное копирование

Нативный Swift vs NSDictionary

Swift Dictionary отличается от NSDictionary:

• Типобезопасность (дженерики)
• Value семантика
• Более предсказуемая производительность
• Нет необходимости в упаковке через AnyHashable

Производительность и оптимизации

Малые словари

Для словарей с небольшим количеством элементов используется специальная оптимизированная реализация, избегающая накладных расходов хеш-таблицы.

Память и tombstone

При удалении вместо реального удаления элемент помечается как tombstone, что:

• Ускоряет поиск (не нужно сдвигать элементы)
• Замедляет деградацию производительности
• Требует периодического рехеширования для очистки

Порядок итерации

Порядок элементов не гарантирован и может меняться при:

• Добавлении новых элементов
• Удалении элементов
• Рехешировании таблицы

Практические следствия

Кастомные типы в качестве ключей

struct UserID: Hashable {
    let id: Int
    
    func hash(into hasher: inout Hasher) {
        hasher.combine(id) // Важно комбинировать все значимые поля
    }
    
    static func == (lhs: UserID, rhs: UserID) -> Bool {
        return lhs.id == rhs.id
    }
}

Производительность операций

• Вставка: O(1) в среднем, O(n) в худшем случае
• Поиск: O(1) в среднем, O(n) в худшем
• Удаление: O(1) в среднем с tombstone подходом

Специальные возможности Swift 5+

reserveCapacity(_:)

Позволяет предварительно выделить память:

var dict: [String: Int] = [:]
dict.reserveCapacity(1000) // Избегаем многократных рехеширований

Модификация значений

dict["key", default: 0] += 1 // Эффективное обновление

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