Словарь (Dictionary) в Swift представляет собой коллекцию неупорядоченных пар "ключ-значение".

Основные характеристики:

Неупорядоченность: Порядок элементов не гарантируется.
Уникальные ключи: Каждый ключ в словаре должен быть уникальным.
Хэшируемые ключи: Тип ключа должен быть хэшируемым (т.е., соответствовать протоколу Hashable). Типы, такие как String, Int, Double, Bool и большинство структур, являются хэшируемыми по умолчанию.
Типизация: Словарь строго типизирован, как по ключам, так и по значениям.
Storage: Реализован на основе хэш-таблицы, что обеспечивает высокую эффективность операций вставки, удаления и доступа по ключу (в среднем O(1)).

Создание словаря:

swift

Доступ и модификация:

swift

Итерация:

swift

Внутренняя структура (обобщенно):

Swift использует модифицированную реализацию хэш-таблицы. При вставке пары "ключ-значение":

Вычисляется хэш-значение ключа.
Хэш-значение используется для определения "корзины" (bucket), в которую должен быть помещен элемент.
Если в корзине уже есть элементы, используется механизм разрешения коллизий (например, цепочки или открытая адресация) для поиска подходящего места.

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

Как устроен словарь в Swift?