Что происходит, когда хеш-таблица заполняется и в неё больше не помещаются новые элементы (rehashing)?

Хеш-таблица хранит элементы в массиве бакетов, индекс которых вычисляется хеш-функцией от ключа. По мере добавления элементов бакеты заполняются, растёт вероятность коллизий, и операции начинают деградировать до O(n). Чтобы этого избежать, таблица отслеживает коэффициент загрузки (load factor) — отношение числа элементов к числу бакетов.

Что такое rehashing

Когда load factor превышает заданный порог (например, 0.75 в Java HashMap), таблица выполняет rehashing:

• Создаётся новый массив бакетов, обычно в два раза больше старого.
• Для каждого существующего элемента заново вычисляется индекс по новой длине массива.
• Элементы переносятся в новые бакеты, коллизии перестраиваются.

Эта операция требует O(n) времени, потому что нужно перебрать все элементы. Но она происходит редко — примерно раз в n вставок, поэтому амортизированная стоимость одной вставки остаётся O(1).

Пример на JavaScript

Упрощённая реализация, показывающая момент rehashing:

class HashTable {
  constructor() {
    this.buckets = new Array(4);
    this.size = 0;
  }
  hash(key) {
    let h = 0;
    for (const ch of key) h = (h * 31 + ch.charCodeAt(0)) % this.buckets.length;
    return h;
  }
  set(key, value) {
    if (this.size / this.buckets.length > 0.75) this.rehash();
    const i = this.hash(key);
    if (!this.buckets[i]) this.buckets[i] = [];
    this.buckets[i].push([key, value]);
    this.size++;
  }
  rehash() {
    const old = this.buckets;
    this.buckets = new Array(old.length * 2);
    this.size = 0;
    for (const bucket of old) {
      if (bucket) for (const [k, v] of bucket) this.set(k, v);
    }
  }
}

Где это применяется

Rehashing встроен в стандартные реализации: HashMap в Java, dict в Python, unordered_map в C++, Map в JavaScript. Разработчику обычно не нужно вызывать его вручную, но важно понимать, что при большом количестве вставок возможны периодические «паузы» на перестройку. В высоконагруженных системах это учитывают, задавая начальную ёмкость (initial capacity), чтобы избежать лишних rehash.

Итог: rehashing — это автоматическое расширение хеш-таблицы при превышении load factor, обеспечивающее амортизированную O(1) для операций. Полезно знать при выборе начальной ёмкости и оценке производительности коллекций.