Что такое хеш-таблица (hash table)?

Хеш-таблица — это структура данных, реализующая интерфейс ассоциативного массива (словаря). Она хранит пары ключ-значение и обеспечивает в среднем O(1) время для операций вставки, удаления и поиска по ключу.

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

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

Проблема коллизий: Разные ключи могут давать одинаковый хеш. Существует два основных метода разрешения коллизий:

• Метод цепочек (Separate Chaining): Каждая корзина содержит связный список (или другую структуру) всех пар, попавших в нее. Dictionary в Swift использует этот метод.
• Открытая адресация (Open Addressing): При коллизии алгоритм ищет следующую свободную корзину по определенному алгоритму (линейное/квадратичное пробирование).

Пример и внутреннее устройство Swift Dictionary:

var scores: [String: Int] = ["Alice": 10, "Bob": 20]
// Под капотом:
// 1. Хеш-функция вычисляет хеш для "Alice".
// 2. Индекс корзины = hash % capacity массива.
// 3. Значение 10 сохраняется в этой корзине (в связном списке, если есть коллизии).

scores["Alice"] = 15 // O(1) в среднем случае

Критически важные аспекты:

• Качество хеш-функции: Должна равномерно распределять ключи по корзинам.
• Коэффициент загрузки (load factor): Отношение количества элементов к количеству корзин. При превышении порога выполняется ресейзинг (rehashing) — увеличение массива и пересчет хешей для всех элементов, что стоит O(n).
• В худшем случае (все ключи попали в одну корзину) производительность деградирует до O(n).