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

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

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

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

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

// Пустой словарь
var emptyDictionary: [String: Int] = [:]

// Словарь с начальными значениями
let cities: [String: String] = [
    "London": "UK",
    "Paris": "France",
    "Tokyo": "Japan"
]

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

// Доступ по ключу (возвращает Optional)
let country = cities["Paris"] // Optional("France")

// Добавление или обновление значения
var scores: [String: Int] = ["Alice": 100, "Bob": 85]
scores["Charlie"] = 90 // Добавление
scores["Alice"] = 105 // Обновление

// Удаление значения
scores["Bob"] = nil // Удаление элемента с ключом "Bob"

Итерация:

for (city, country) in cities {
    print("\(city) is in \(country)")
}

for city in cities.keys {
    print("City: \(city)")
}

for country in cities.values {
    print("Country: \(country)")
}

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

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

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

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