Какая алгоритмическая сложность получения элемента из Dictionary и Set в Swift

Что проверяют

Не только цифру O(1), но и условия, при которых она держится: качество хеша, коллизии, копирование при записи. Часто вопрос уходит в Hashable и в реальную стоимость операций над value-типами.

Как отвечать

Короткий ответ: чтение по ключу из Dictionary и проверка вхождения в Set это O(1) в среднем и амортизированно, худший случай O(n).

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

Худший случай наступает, когда много ключей дают один хеш и поиск вырождается в перебор кластера. На практике это самописный hash(into:), кладущий в хешер одно поле из десяти, или Hashable, несогласованный с ==.

Про хеширование полезно добавить: применяется SipHash с сидом, случайным на каждый запуск процесса. Отсюда два следствия: подобрать коллизии снаружи трудно, и порядок обхода Dictionary/Set меняется от запуска к запуску, завязываться на него нельзя.

Остальные операции:

• вставка и удаление O(1) амортизированно;
• count и isEmpty O(1);
• полный перебор O(n);
• keys и values это ленивые представления, копирования нет.

Что не видно за записью O(1) и что обычно уточняют:

• copy-on-write. Присваивание словаря другой переменной стоит O(1), но первая же мутация при наличии второй ссылки копирует хранилище целиком, то есть O(n). Отсюда неожиданные просадки в цикле, если коллекция где-то ещё захвачена;
• предаллокация через Dictionary(minimumCapacity:) снимает серию перестроений, когда объём известен заранее;
• коллекция, пришедшая из Objective-C как NSDictionary, работает через мост, и константа заметно хуже нативной;
• сравнение с массивом: Array.contains это O(n), поэтому проверку вхождения внутри цикла переводят на Set и получают O(n) вместо O(n в квадрате).

let ages = ["Alice": 25, "Bob": 30]
let alice = ages["Alice"]              // O(1) в среднем, тип Int?
var seen = Set<Int>(minimumCapacity: 1000)
seen.insert(3)                          // O(1) амортизированно

Где спотыкаются

Называют O(1) и останавливаются, не объясняя, откуда берётся худший случай и как он связан с качеством hash(into:). Ещё частое: описывают разрешение коллизий цепочками по аналогии с Java и не знают про copy-on-write, из-за которого дешёвая на бумаге операция превращается в копирование всей коллекции.