Этот вопрос проверяет понимание устройства хэш-таблиц и их реализации в Python для словарей и множеств.
Хэш-таблица — это структура данных, которая хранит пары ключ-значение и позволяет быстро находить значение по ключу с помощью хэш-функции. В Python словари (dict) и множества (set) реализованы как хэш-таблицы. Коллизии (когда разные ключи имеют одинаковый хэш) разрешаются с помощью открытой адресации.
Хэш-таблицы обеспечивают среднюю сложность O(1) для операций вставки, удаления и поиска.
Как работает хэш-таблица:
Хэш-функция: Преобразует ключ в индекс массива (бакетов).
Хранение: Значения хранятся в массиве по вычисленному индексу.
Коллизии: Когда два ключа дают одинаковый хэш, используется метод разрешения коллизий.
В Python:
dict и set используют хэш-таблицы.
Коллизии разрешаются открытой адресацией: При коллизии ищется следующий свободный слот в массиве.
Хэширование: Ключи должны быть хэшируемыми (неизменяемые типы).
Пример коллизии:
# Разные ключи могут иметь одинаковый хэш
hash('key1') % 8 == hash('key2') % 8 # Возможна коллизияОптимизации в Python:
Таблица resize-уется при заполнении для поддержки эффективности.
Используется pseudo-random probing для поиска свободного слота.
