Хеш-таблица (хеш-мап) — это структура данных, реализующая ассоциативный массив, которая отображает ключи на значения.
Основной принцип работы:
- Хеширование: Для каждого ключа вычисляется хеш-код — числовое значение фиксированного размера с помощью хеш-функции. Хорошая хеш-функция распределяет хеш-коды равномерно по всему диапазону выходов.
- Индексирование: Вычисленный хеш-код используется для определения индекса (позиции) в массиве, где будет храниться соответствующее значение. Часто хеш-код по модулю размера массива (
hash(key) % array_size) дает итоговый индекс.
- Хранение: В массиве по рассчитанному индексу хранится пара (ключ, значение).
- Поиск: Для нахождения значения по ключу, снова вычисляется хеш-код ключа, определяется индекс, и по этому индексу извлекается значение.
- Коллизии: Возникают, когда разные ключи имеют одинаковый хеш-код. Существуют различные методы для разрешения коллизий:
- Метод цепочек (Separate Chaining): По каждому индексу массива хранится список (или другая структура данных), содержащий все пары (ключ, значение), хеш-коды которых привели к этому индексу.
- Метод открытой адресации (Open Addressing): При возникновении коллизии ищется другое свободное место в массиве по определенному правилу (линейное зондирование, квадратичное зондирование, двойное хеширование).
Преимущества:
- В среднем операции вставки, удаления и поиска имеют сложность O(1), если хеш-функция хорошая и коллизии редки.
Недостатки:
- Худший случай производительности может быть O(n), если все ключи хешируются в один и тот же индекс (например, при плохой хеш-функции или большом количестве коллизий).
- Требуется дополнительная память для массива и, возможно, для разрешения коллизий.
В Swift хеш-таблицы реализованы типом Dictionary.
swift