Как устроена хеш-таблица внутри?

Хеш-таблица хранит пары «ключ — значение» в массиве и находит значение по ключу за O(1) в среднем. Положение элемента вычисляют из ключа хеш-функцией.

Основные шаги

1. Хеш-функция превращает ключ в число: hash(key).
2. Индекс ячейки (корзины, bucket) получают как hash(key) % capacity.
3. Значение кладут в эту ячейку; для чтения повторяют вычисление.

function index(key, capacity) {
  let h = 0;
  for (const ch of String(key)) h = (h * 31 + ch.charCodeAt(0)) | 0;
  return Math.abs(h) % capacity;
}

Коллизии

Разные ключи могут попасть в одну ячейку. Два основных способа решения:

• Цепочки (chaining): в ячейке хранится список пар; при поиске сравнивают ключи в списке. Так устроена Java HashMap: слишком длинные цепочки превращаются в дерево.
• Открытая адресация: при занятой ячейке ищут следующую свободную (линейное и квадратичное пробирование, двойное хеширование).

Коэффициент заполнения и расширение

Load factor = элементов / ячеек. При превышении порога (часто 0,75) таблицу увеличивают вдвое и перехешируют все ключи (rehash). Это редкая, но дорогая операция O(n); амортизированно вставка остаётся O(1).

Сложность

• Поиск, вставка, удаление: O(1) в среднем, O(n) в худшем случае при множестве коллизий.
• Порядок элементов не гарантируется (если структура не помнит порядок вставки).

Требования к хеш-функции

Детерминированность, равномерное распределение, быстрота вычисления. Для ключей-объектов нужны согласованные equals и hashCode.

Где встречается

Map/Set в JavaScript, dict в Python, HashMap в Java, индексы в базах данных.

Коротко для собеседования

Хеш-таблица — массив корзин, индекс вычисляется как hash(key) % capacity. Коллизии решают цепочками или открытой адресацией, при росте заполнения таблицу расширяют с перехешированием; операции в среднем O(1).