В чем разница скорости доступа в словаре и массиве?

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

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

Как отвечать

Сравнивать надо одинаковые операции, иначе ответ бессмысленный:

• Array по индексу: O(1). Элементы лежат в непрерывном буфере, адрес считается смещением. Выход за границы не возвращает nil, а роняет приложение;
• Array поиск по значению: contains, firstIndex(of:) и first(where:) проходят массив подряд, это O(n);
• Dictionary по ключу: O(1) в среднем. Ключ обязан быть Hashable, по хэшу вычисляется позиция в таблице, коллизии Swift разрешает открытой адресацией. Сабскрипт возвращает опционал, отсутствие ключа даёт nil, а не краш;
• Set: та же хэш-таблица без значений, contains за O(1) в среднем.

Средний O(1) у словаря дороже честного O(1) у массива. Нужно посчитать хэш (для строки это проход по всем её символам), сравнить ключи через ==, а данные лежат менее удобно для кэша процессора. Поэтому на десятке элементов линейный поиск по массиву бывает быстрее словаря, а на тысячах словарь выигрывает на порядки.

Для iOS добавьте две детали. Оба типа это value types с copy-on-write: копия дешёвая, пока одну из копий не начнут менять. И Dictionary в Swift не хранит порядок вставки, для этого есть OrderedDictionary из пакета swift-collections.

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

Сравнивают доступ по индексу с поиском по ключу и делают вывод «массив быстрее». Если элемент нужен по идентификатору, массив даёт O(n), а first(where:) внутри цикла по другому массиву превращается в O(n·m).

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

Считают сабскрипт массива таким же безопасным, как у словаря. array[10] на массиве из пяти элементов это краш с «Index out of range», поэтому индекс из внешних данных сначала проверяют через indices.contains.