Какая алгоритмическая сложность поиска в словаре

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

Знаете ли вы, что Dictionary в Swift это хэш-таблица, от чего зависит её скорость и что может сделать поиск медленным. На iOS следом обычно спрашивают про Hashable, свою реализацию hash(into:) и копирование словарей как типов-значений.

Как отвечать

• поиск по ключу: dict[key] в среднем O(1). Хэш ключа определяет позицию в таблице, дальше сравнение через ==;
• худший случай: O(n), если хэши многих ключей совпадают. Обычно виноват самописный hash(into:);
• устройство: нативный словарь Swift использует открытую адресацию с линейным пробированием, а не цепочки. При заполнении примерно на три четверти таблица расширяется; отдельная вставка при этом стоит O(n), но в среднем выходит O(1);
• хэширование: со Swift 4.2 работает Hasher со случайным зерном на каждый запуск процесса. Это защищает от подбора коллизий, но делает порядок обхода словаря разным от запуска к запуску;
• поиск по значению: dict.values.contains(x) или first(where:) перебирают всё, это O(n).

Для своего ключа-структуры достаточно объявить соответствие Hashable, если все хранимые свойства сами Hashable: компилятор синтезирует == и hash(into:). Если пишете вручную, в hash(into:) должны участвовать те же поля, что и в ==.

Отдельно упомяните copy-on-write. Dictionary это тип-значение: присваивание не копирует данные, но первая мутация, пока буфер разделён с другой переменной, копирует всю таблицу за O(n). Если размер известен заранее, reserveCapacity(_:) избавит от промежуточных расширений.

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

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

Пишут hash(into:) по полю с малым числом значений, например по типу или флагу. Ключи с одинаковым хэшем сбиваются в один кластер, и поиск деградирует до линейного.

Меняют словарь через временную копию в цикле: var d = model.items; d[k] = v; model.items = d. В момент мутации буфер разделён со свойством, поэтому каждая итерация копирует всю таблицу, и цикл из O(n) становится O(n²).