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

Основные компоненты и принцип работы:

Массив (Buckets): Основное хранилище данных, представляющее собой массив определенного размера. Каждый элемент этого массива называется "ведром" (bucket) или "слотом".
Хеш-функция: Преобразует ключ в числовое значение (хеш-код). Хорошая хеш-функция распределяет ключи равномерно по хеш-кодам.
Индексирование: Хеш-код, полученный от хеш-функции, используется для определения индекса в массиве, где будет храниться или извлекаться значение, соответствующее данному ключу. Часто используется операция по модулю (хеш_код % размер_массива) для получения индекса в диапазоне от 0 до размер_массива - 1.
Разрешение коллизий: Поскольку разные ключи могут иметь одинаковый хеш-код (хеш-коллизия), хеш-таблица должна иметь механизм их разрешения. Два основных подхода:
- Метод цепочек (Chaining): В каждом ведре хранится связанный список (или другая структура данных, например, бинарное дерево), содержащий все пары ключ-значение, которые были хешированы в это ведро.
- Метод открытой адресации (Open Addressing): При коллизии ищется следующее свободное ведро в массиве, используя различные стратегии (линейное пробирование, квадратичное пробирование, двойное хеширование).

Процесс вставки (put):

Вычисляется хеш-код ключа.
Вычисляется индекс ведра на основе хеш-кода.
Пара ключ-значение помещается в соответствующее ведро. При использовании метода цепочек добавляется в список ведра. При открытой адресации ищется свободное место.

Процесс извлечения (get):

Вычисляется хеш-код и индекс ведра для данного ключа.
Переход к соответствующему ведру.
Если используется метод цепочек, поиск пары ключ-значение в списке ведра. Если используется открытая адресация, поиск пары в массиве, начиная с вычисленного индекса, используя ту же стратегию пробирования, что и при вставке.
Сравнение ключей (так как разные ключи могут иметь одинаковый хеш-код) для нахождения нужной пары.

Процесс удаления (delete):

Похож на извлечение: вычисляется хеш-код и индекс.
Находится пара ключ-значение.
Пара удаляется. Для открытой адресации обычно используется "ленивое удаление" (пометка слота как удаленного), чтобы не нарушить последовательности поиска при извлечении.

Пример (концептуальный):

Предположим, у нас есть небольшой массив из 5 ведер, и мы используем метод цепочек.

Ключ	Хеш-функция	Индекс (хеш % 5)	Ведро
"apple"	$\approx 110$	$110 \% 5 = 0$	Ведро 0: [("apple", "red")]
"banana"	$\approx 221$	$221 \% 5 = 1$	Ведро 1: [("banana", "yellow")]
"cherry"	$\approx 332$	$332 \% 5 = 2$	Ведро 2: [("cherry", "red")]
"date"	$\approx 115$	$115 \% 5 = 0$	Ведро 0: [("apple", "red"), ("date", "brown")]

При поиске "date", хеш-функция дает хеш-код $\approx 115$ , индекс 0. Переходим к Ведру 0 и просматриваем список, пока не найдем ключ "date".

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

В Python хеш-таблица реализована в типе данных dict.

python

Как работает хеш-таблица?