Как работают хеш-таблицы: визуализация O(1) на Python

Почему хеш-таблицы работают за O(1)?

Большинство разработчиков знают, что хеш-таблицы дают доступ за O(1), но мало кто может объяснить, что происходит внутри. Как хеш-функция превращает ключ в индекс? Что такое коллизия и как она влияет на скорость? Почему вставка иногда замедляется? В этой статье мы разберём работу хеш-таблицы на пальцах и с помощью визуализатора, который показывает каждый шаг: хеш, корзины, коллизии, коэффициент загрузки и ресайз.

Шаг 1: хеш-функция превращает ключ в корзину

Каждый ключ проходит через хеш-функцию. В визуализаторе используется djb2:

h = 5381
for char in key:
    h = h * 33 + ord(char)
bucket = h % capacity

Например, для ключа "apple":

key: "apple"
hash: 2090620131
bucket = 2090620131 % 16 = 3

Модуль — это вся магия: произвольная строка превращается в индекс массива, а доступ по индексу — это действительно O(1). Визуализатор показывает число и остаток от деления для каждой операции.

Шаг 2: коллизии образуют цепочки

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

# Пример: корзина 6
[6] banana:🍌 → peach:🍑
# Корзина 7
[7] apple:🍎  → mango:🥭

Теперь поиск — это не "прыжок в ячейку", а "прыжок в корзину, затем просмотр цепочки". Если цепочки короткие, это всё ещё O(1); если все ключи свалены в одну корзину, сложность падает до O(n). Поэтому следующий шаг критичен.

Шаг 3: коэффициент загрузки решает всё

Коэффициент загрузки = количество элементов / ёмкость. Это среднее число записей на корзину. Низкий коэффициент — короткие цепочки и быстрые операции. Высокий — длинные цепочки. Хеш-таблица отслеживает этот показатель, и когда он превышает порог (в нашем визуализаторе 0.75, как в java.util.HashMap), происходит ресайз.

Шаг 4: ресайз и рехеширование — почему "амортизированное O(1)"

Когда коэффициент загрузки пересекает 0.75, таблица удваивает количество корзин и рехеширует все существующие ключи в новый массив. Рехеширование необходимо, потому что корзина = hash % capacity, а ёмкость изменилась — старый индекс в новом размере недействителен.

Один ресайз занимает O(n). Как же тогда вставка может быть O(1)? Ответ: амортизация. Удвоение означает, что ресайзы происходят экспоненциально реже по мере роста таблицы: чтобы добавить n элементов, ресайзы происходят при ~1, 2, 4, 8, ... n элементах. Суммарная работа по всем рехешированиям составляет около 2n — константная дополнительная работа на каждую вставку в среднем. Какая-то одна вставка может быть дорогой, но средняя стоимость плоская. Наблюдая, как полоска коэффициента загрузки ползёт к 0.75 и затем резко сбрасывается при удвоении корзин, вы лучше всего почувствуете этот компромисс.

Попробуйте сами

Нажмите +5 random несколько раз: смотрите, как ключи хешируются, попадают в корзины, образуют цепочки. Продолжайте, и вы увидите, как коэффициент загрузки достигает 0.75, а таблица прыгает с 8 до 16, затем до 32, перераспределяя всё. Затем выполните get для ключа — проследите, как просматривается цепочка, и put для существующего ключа — убедитесь, что значение обновляется на месте, а не дублируется (так работает Map.set).

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

Практический вывод

Попробуйте визуализатор прямо сейчас: https://dev48v.github.io/hash-table-visualizer/. Поставьте звезду на GitHub, если проект помог: https://github.com/dev48v/hash-table-visualizer.