Как реализован Dictionary в Swift: хеш-таблица или красно-чёрное дерево?

В стандартной библиотеке Swift тип Dictionary реализован как хеш-таблица (hash table).

Почему хеш-таблица?

• Средняя сложность O(1) для основных операций: вставка (insert), поиск (subscript), удаление (remove).
• Высокая производительность для большинства сценариев использования словаря.

Принцип работы:

1. Ключ хешируется (протокол Hashable) в целочисленное значение.
2. Это значение используется для вычисления индекса (bucket) во внутреннем массиве.
3. Для разрешения коллизий (когда разные ключи дают одинаковый индекс) Swift использует метод открытой адресации с линейным пробированием.

Пример и важные детали:

var scores: [String: Int] = ["Alice": 10, "Bob": 15]
// Вставка - средняя O(1)
scores["Charlie"] = 20
// Поиск - средняя O(1)
let aliceScore = scores["Alice"] // Optional(10)
// Удаление - средняя O(1)
scores["Bob"] = nil

Красно-чёрные деревья (самобалансирующиеся BST) гарантируют O(log n) для операций и используются в некоторых реализациях (например, NSDictionary на macOS может использовать tree-based подход). Однако в Swift выбор в пользу хеш-таблиц сделан для оптимальной скорости в типичных случаях.

Вывод: Swift Dictionary — это хеш-таблица, что обеспечивает отличную производительность при условии качественной хеш-функции ключа.