Почему поиск по ключу в Dictionary выполняется быстро?

Быстрый поиск в Dictionary<Key, Value> обеспечивается внутренней структурой — хеш-таблицей.

Принцип работы:

1. Ключ (тип Key) должен соответствовать протоколу Hashable.
2. При вставке или поиске для ключа вычисляется хэш-значение.
3. Это значение преобразуется в индекс корзины (bucket) внутри внутреннего массива хеш-таблицы.
4. Доступ к элементу по индексу массива — операция O(1).

Пример:

var scores: [String: Int] = ["Alice": 95, "Bob": 87]
// Поиск:
let bobsScore = scores["Bob"] // O(1) в среднем случае

Детали реализации и сложность:

• Средний случай O(1): Хорошая хэш-функция равномерно распределяет ключи по корзинам, минимизируя коллизии.
• Худший случай O(n): Возникает при множественных коллизиях, когда много ключей попадает в одну корзину, и поиск превращается в линейный по списку внутри неё.
• Swift автоматически рехеширует словарь (увеличивает количество корзин и перераспределяет элементы), когда коэффициент загрузки становится слишком высоким, чтобы сохранять производительность.

Требования к типу Key:

struct Coordinate: Hashable {
    let x: Int
    let y: Int
    // Компилятор может автоматически синтезировать hash(into:) и ==, 
    // если все свойства также Hashable.
}

var dict = [Coordinate: String]()
dict[Coordinate(x: 10, y: 20)] = "Point A"

Важно: Dictionary не гарантирует порядок элементов. Для упорядоченного хранения пар ключ-значение используйте другие структуры (например, массив кортежей или сторонние реализации).