Что такое хэш-таблица? Что под капотом у словаря (dict) и множества (set) в Python? (Хэш, коллизии, открытая адресация).

Question

Хэш-таблица — это структура данных, которая хранит пары ключ-значение и позволяет быстро находить значение по ключу с помощью хэш-функции. В Python словари (dict) и множества (set) реализованы как хэш-таблицы. Коллизии (когда разные ключи имеют одинаковый хэш) разрешаются с помощью открытой адресации.

YeaHub · Accepted Answer

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