---
title: "Как работает хеш-таблица"
url: https://algopath.pro/ru/blog/kak-rabotaet-hesh-tablitsa
language: ru
summary: "Хеш-таблица превращает ключ в индекс массива, и этот шаг объясняет все правила, которые тебе велели соблюдать. Константное время это среднее."
updated: 2026-10-27
---

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

**Короткий ответ.** Хеш-таблица прогоняет ключ через хеш-функцию, берёт остаток от деления на размер массива и кладёт значение в эту ячейку. Чтение повторяет те же шаги, поэтому в среднем занимает константное время. Коллизии решают цепочками или открытой адресацией, а после заполнения примерно на 0,75 таблица удваивает массив.

 

## Главный ход

 

Есть массив, скажем на 16 ячеек.

 

Прогоняем ключ через хеш-функцию. Получаем число. Берём остаток от деления на 16.

 

Получилась ячейка. Кладём значение в неё.

 

Чтение повторяет те же шаги и попадает туда же.

 

Поиска не было. Отсюда и константное время.

 

У [хеш-функции](https://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F) одна работа. Равномерно раскидывать ключи по ячейкам.

 

Хеш-функция всегда даёт один ответ для одного ключа.

 

## Коллизии

 

Два ключа обязательно попадут в одну ячейку.

 

При 16 ячейках и 20 ключах это гарантировано. Вероятно гораздо раньше.

 

Стандартных ответов два.

 

**Цепочки.** В ячейке лежит маленький список. Столкнулись, дописали в конец.

 

Чтение находит ячейку и проходит список. Обычно там один или два элемента.

 

**Открытая адресация.** Ячейка занята? Пробуем следующую. И так до свободной.

 

Списков нет. С кешем дружелюбнее. Удаление капризнее.

 

Оба быстрые, пока списки короткие.

 

## Заполнение и расширение

 

За короткие списки отвечает коэффициент заполнения. Это записи, делённые на ячейки.

 

После примерно 0,75 коллизии становятся частыми, чтение замедляется.

 

Таблица берёт массив побольше, обычно вдвое. И перехеширует туда все ключи.

 

Расширение стоит O(n). Платит за него одна невезучая вставка.

 

В среднем по всем вставкам цена всё равно константная. Это честный смысл [амортизированной](https://ru.wikipedia.org/wiki/%D0%90%D0%BC%D0%BE%D1%80%D1%82%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7) оценки.

 

Что значит константное время, разобрано в [Big O без математики](/ru/blog/big-o-prostymi-slovami).

 

Отсюда же сюрприз в проде. Вставка, которая обычно занимает микросекунду, иногда занимает сильно больше.

 

Если ты в этот момент держишь блокировку, это важно.

 

## Почему худший случай O(n)

 

Все ключи в одной ячейке, и таблица вырождается в длинный список. Каждое чтение его сканирует.

 

На случайных данных так не бывает. На подобранных бывает.

 

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

 

Поэтому современные среды солят хеш-функцию случайным числом на каждый процесс.

 

На собеседовании отвечай «O(1) в среднем, O(n) в худшем». Проверяют как раз знание, что это среднее.

 

## Два правила, которые теперь понятны

 

**Не меняй ключ после вставки.** Ячейку выбрали по старому содержимому.

 

Изменил, и запись лежит не там. Она недостижима, а не потеряна. Это хуже.

 

**Равные ключи обязаны хешироваться одинаково.** Переопределил равенство и не тронул хеш? Словарь начнёт терять записи.

 

Баг всплывает через месяцы.

 

## Когда нужно другое

 

У хеш-таблицы нет порядка. Это сделка, а не упущение.

 

Поэтому «все ключи от 10 до 50» это полный проход. И «самый маленький ключ». И «всё по порядку».

 

Таким запросам нужно сбалансированное дерево. Log n на операцию, порядок по построению.

 

Базы данных держат обе. Хеш-индексы для точных совпадений, [B-деревья](https://ru.wikipedia.org/wiki/B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE) для диапазонов.

 

## Где это в треке

 

[AlgoPath](/ru) тратит шаги с 14 по 17 на то, чтобы ты её построил.

 

Ты сам напишешь код для коллизий и расширения, а не прочитаешь абзац.

 

Когда за ней вообще тянуться, разобрано в статье [множество, словарь или массив](/ru/blog/struktury-dannyh-javascript).

 

Паттерн, который на ней стоит, это [хеш-множество и словарь](/ru/patterns/hash-set-map).

 

Первые 33 шага бесплатные.