Ответ
Хеш-таблица (hash table) — это структура данных, реализующая ассоциативный массив (словарь), которая позволяет хранить пары «ключ-значение» и выполнять операции поиска, вставки и удаления в среднем за время O(1).
Принцип работы основан на трёх ключевых компонентах:
- Массив (buckets): Основное хранилище данных, состоящее из ячеек (бакетов).
- Хеш-функция: Функция, которая преобразует ключ в целочисленный индекс массива. Идеальная хеш-функция распределяет ключи по массиву равномерно.
index = hash_function(key) % array_size - Механизм разрешения коллизий: Ситуация, когда хеш-функция генерирует одинаковый индекс для разных ключей, называется коллизией. Существует два основных метода её разрешения:
- Метод цепочек (Chaining): Каждая ячейка массива является указателем на связанный список (или другую структуру), в котором хранятся все пары ключ-значение с одинаковым хешем. Это наиболее распространенный подход.
- Открытая адресация (Open Addressing): Если ячейка занята, алгоритм ищет следующую свободную ячейку в массиве по определённому правилу (например, линейное или квадратичное пробирование).
Производительность
- Среднее время: O(1) для поиска, вставки и удаления.
- Худшее время: O(n), когда все ключи попадают в одну ячейку (плохая хеш-функция или специально подобранные данные), и структура вырождается в связанный список.
В Python структура данных dict реализована с использованием хеш-таблицы с открытой адресацией.