Ответ
O(1) в среднем случае, но может деградировать до O(n) в худшем.
Объяснение: Dictionary реализован как хеш-таблица.
- Средний случай (O(1)): Хеш-функция вычисляет индекс корзины (bucket) для ключа, обеспечивая почти мгновенный доступ. Коллизии (разные ключи с одинаковым хешем) разрешаются методами вроде цепочек или открытой адресации, но при хорошем распределении хешей и достаточном размере таблицы доступ остается константным.
- Худший случай (O(n)): Возникает при множественных коллизиях, когда все ключи попадают в одну корзину, и поиск превращается в линейный обход.
Пример:
var capitals = ["France": "Paris", "Japan": "Tokyo", "Brazil": "Brasília"]
let city = capitals["Japan"] // O(1) в среднемПрактический вывод: Для типов с качественной хеш-функцией (как стандартные) сложность эффективна. Избегайте использования в качестве ключей типов с плохим хешированием.
Ответ 18+ 🔞
А, ну ты глянь, какой вопрос подъехал! Словарь в Свифте, он же Dictionary — это ж, блядь, как шкаф с ящичками, только для данных. Ну, хеш-таблица, если по-умному.
Так вот, слушай сюда, вся соль в том, что достать из него значение по ключу — это обычно O(1), то есть почти моментально, как хуй с горы. Представь: у тебя ключ, типа "Japan". Компьютер его через хеш-функцию пропускает — получается номер ящика. Подбежал к шкафу, открыл ящик под этим номером — бац, а там лежит "Tokyo". Всё, ебушки-воробушки, дело сделано. Константная сложность, красота!
НО! Здесь, сука, есть одно жирное «но», которое может всё испортить. Это худший случай — O(n). А случается он тогда, когда твоя хеш-функция — говно, или ты такой умный, что специально подобрал кучу ключей, которые все лезут в один и тот же ящик. Представь: у тебя шкаф на 100 ящиков, а ты все свои вещи запихнул в один-единственный, да ещё и в беспорядке. И теперь ищешь там один носок. Придётся, блядь, перерыть всю эту кучу, по сути сделать линейный поиск. Вот это и есть O(n), пиздец и ужас.
Код, его не трогаем, он святой:
var capitals = ["France": "Paris", "Japan": "Tokyo", "Brazil": "Brasília"]
let city = capitals["Japan"] // O(1) в среднемВидишь? Достаём "Tokyo" по ключу "Japan". Обычно — мгновенно.
Так что запомни, чувак: Пока ты используешь нормальные ключи (строки, числа, и прочую стандартную хуйню), которые хорошо хешируются — всё летает. Но если возьмёшься делать ключом свой кастомный тип и накосячишь с реализацией hash(into:), то получишь эту самую деградацию. И тогда твой быстрый словарь превратится в тупой линейный список, а производительность — накрылась медным тазом. Волнение, блядь, чувствую, уже подкатывает.