Алгоритмы с нуля

Коллизии и реальная стоимость хеширования

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

◷ 20 min

Ты узнал, что хеш-множество или хеш-таблица отвечает на вопрос “есть ли X в таблице?” за O(1) в среднем. Но слово “в среднем” — это суть. Обещание O(1) зависит от двух вещей: (1) функция хеша распределяет ключи равномерно по корзинам, и (2) каждая корзина маленькая. Когда два разных ключа отображаются в одну корзину — коллизия — они должны храниться вместе, и время поиска растёт с длиной цепочки. Если все ключи коллизируют в одну корзину, структура становится связным списком и время становится O(n). На этом уроке мы разберёмся, почему коллизии происходят, как их разрешают, как их держать редкими и когда обещание O(1) в среднем действительно держится.

Goal

После этого урока ты сможешь объяснить, почему два разных ключа могут отображаться в одинаковый индекс (коллизия), понять, как разделённое цепочками разрешение коллизий хранит несколько пар ключ–значение в связном списке в каждой корзине, узнать, что коэффициент заполнения (элементы ÷ корзины) определяет длину цепочки и стоимость поиска, объяснить, почему расширение таблицы сохраняет O(1) в среднем при росте таблицы, рассуждать об амортизированном анализе, чтобы понять, почему редкий O(n) resize раскладывается на множество дешёвых операций, определить, когда производительность хеш-таблицы деградирует до O(n) (плохая функция хеша или враждебный вход), и различать производительность в среднем и в худшем случае.

The idea

Проблема: что происходит, когда два ключа коллизируют?

Представь функцию хеша для таблицы размером 5: она отображает ключи в индексы 0–4.

function hash(key) {
  return key.charCodeAt(0) % 5;
}

hash('Alice')    // 'A' (65) % 5 = 0
hash('April')    // 'A' (65) % 5 = 0  ← коллизия!
hash('Bob')      // 'B' (66) % 5 = 1
hash('Ben')      // 'B' (66) % 5 = 1  ← коллизия!
hash('Charlie')  // 'C' (67) % 5 = 2

Alice и April оба отображаются в индекс 0. Ben и Bob оба отображаются в индекс 1. Где хранить второй ключ, если корзина уже занята?

Разделённое цепочками (separate chaining): храни связный список в каждой корзине.

Самое простое решение — сделать каждую корзину связным списком. Когда коллизия происходит, добавь пару ключ–значение в список в той корзине.

// Концептуально, хеш-таблица — это массив связных списков:
// table[0] -> (Alice, 555-1234) -> (April, 555-9999) -> null
// table[1] -> (Bob, 555-5678) -> (Ben, 555-4321) -> null
// table[2] -> (Charlie, 555-0000) -> null
// table[3] -> null
// table[4] -> null

Чтобы вставить Alice в индекс 0: помести пару (Alice, phone) в начало списка в table[0]. Чтобы вставить April: захеши April, получи индекс 0, добавь (April, phone) в список в table[0].

Чтобы найти Alice: захеши Alice, получи индекс 0, просканируй список в table[0] пока не найдёшь “Alice”. Среднее время: O(длина цепочки).

Длина цепочки зависит от коэффициента заполнения.

Коэффициент заполнения — это отношение количества элементов к количеству корзин: α = элементы ÷ корзины.

Если у тебя 10 элементов и 20 корзин, α = 0.5. Элементы распределены по многим корзинам, цепочки короткие. Если у тебя 10 элементов и 2 корзины, α = 5. Элементы скучены в несколько корзин, цепочки длинные.

С разделённым цепочками:

Средняя длина цепочки = α (коэффициент заполнения).
Среднее время поиска = O(1 + α).
Если α держать маленьким (например, ≤ 0.75), то поиск O(1 + constant) = O(1) в среднем.

Расширение и переэширование: держи низкий коэффициент заполнения.

По мере вставок, коэффициент заполнения растёт. Цепочки удлиняются, поиск замедляется. Чтобы исправить это, когда коэффициент заполнения превышает пороговое значение (например, 0.75), таблица выделяет новый, больший массив (обычно вдвое больше), и переэширует каждый ключ в новый массив.

// Перед переэшированием: 10 элементов, 5 корзин, α = 2.0
// Выделяем новую таблицу с 10 корзинами

// Для каждой пары (key, value) в старой таблице:
//   newIndex = hash(key, 10)  // Переэширируем с новым размером таблицы
//   вставляем в новую table[newIndex]

// Результат: 10 элементов, 10 корзин, α = 1.0
// Цепочки снова короче; поиск остаётся O(1) в среднем

Переэширование дорого — оно просматривает каждый элемент и переэширует его, стоимость O(n) для n элементов. Но это происходит редко. Каждый элемент переэширируется лишь несколько раз за свою жизнь. Амортизированно по многим дешёвым вставкам, редкий O(n) resize становится O(1) амортизировано за вставку. Поэтому вставка в хеш-таблицу O(1) амортизировано, хотя отдельные вставки редко вызывают O(n) resize.

Худший случай: когда коллизии не редкие.

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

Пример: плохая функция хеша, использующая только первый символ, вызовет коллизию всех слов, начинающихся с ‘A’.

Реальное обещание O(1):

Хеш-таблицы достигают O(1) в среднем при поиске, когда:

Функция хеша распределяет ключи равномерно (случайноподобные индексы).
Коэффициент заполнения держится маленьким (через переэширование).

При этих условиях вероятность, что поиск встретит длинную цепочку, пренебрежимо мала, и O(1) в среднем держится на практике.

The code

Построение хеш-таблицы с цепочками (симуляция):

class ChainedHashTable {
  constructor(size = 5) {
    this.buckets = Array.from({ length: size }, () => []);  // Массив списков
    this.size = size;
    this.count = 0;
  }

  hash(key) {
    let h = 0;
    for (let char of key) {
      h = (h * 31 + char.charCodeAt(0)) % this.size;
    }
    return h;
  }

  set(key, value) {
    const index = this.hash(key);
    const bucket = this.buckets[index];

    // Проверь, существует ли ключ
    for (let [k, v] of bucket) {
      if (k === key) {
        v = value;  // Обновить существующий
        return;
      }
    }

    // Добавить новую пару ключ–значение
    bucket.push([key, value]);
    this.count++;
  }

  get(key) {
    const index = this.hash(key);
    const bucket = this.buckets[index];

    // Просканируй цепочку на предмет ключа
    for (let [k, v] of bucket) {
      if (k === key) return v;
    }
    return undefined;
  }

  has(key) {
    return this.get(key) !== undefined;
  }

  get loadFactor() {
    return this.count / this.size;
  }
}

// Пример использования
const table = new ChainedHashTable(5);
table.set("Alice", "555-1234");
table.set("April", "555-9999");   // Коллизия в индексе 0
table.set("Bob", "555-5678");

console.log(table.get("Alice"));  // "555-1234" (просканируй цепочку длины 2)
console.log(table.get("April"));  // "555-9999" (найдена после 1 скана)
console.log(table.get("Bob"));    // "555-5678" (цепочка длины 1)
console.log(table.loadFactor);    // 0.6 (3 элемента, 5 корзин)

Попробуй симуляцию:

class ChainedHashTable {
constructor(size = 5) {
  this.buckets = Array.from({ length: size }, () => []);
  this.size = size;
  this.count = 0;
}

hash(key) {
  let h = 0;
  for (let char of key) {
    h = (h * 31 + char.charCodeAt(0)) % this.size;
  }
  return h;
}

set(key, value) {
  const index = this.hash(key);
  const bucket = this.buckets[index];
  for (let [k, v] of bucket) {
    if (k === key) {
      v = value;
      return;
    }
  }
  bucket.push([key, value]);
  this.count++;
}

get(key) {
  const index = this.hash(key);
  const bucket = this.buckets[index];
  for (let [k, v] of bucket) {
    if (k === key) return v;
  }
  return undefined;
}

get loadFactor() {
  return this.count / this.size;
}
}

const table = new ChainedHashTable(5);
table.set("Alice", "555-1234");
table.set("April", "555-9999");
table.set("April2", "555-8888");
table.set("Bob", "555-5678");
table.set("Ben", "555-4321");

console.log("Поиск Alice:", table.get("Alice"));
console.log("Поиск April:", table.get("April"));
console.log("Поиск April2:", table.get("April2"));
console.log("Коэффициент заполнения:", (table.count / table.size).toFixed(2));
console.log("Содержимое корзин:");
for (let i = 0; i < table.size; i++) {
console.log(`  Индекс ${i}: [${table.buckets[i].map(([k,v]) => k).join(", ")}]`);
}

Вывод

Step-by-step trace

Давайте проследим поиск в таблице с цепочками. Мы ищем “April” в таблице с коллизией в индексе 0:


      1
      function lookup(key) {
    

      2
        const index = hash(key);
    

      3
        const bucket = table[index];
    

      4
        for (let [k, v] of bucket) {
    

      5
          if (k === key) return v;
    

      6
        }
    

      7
        return undefined;
    

      8
      }

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

Complexity

Операции хеш-таблицы с цепочками:

Операция	Время (в среднем)	Время (худший)	Примечания
Поиск / Has	O(1 + α)	O(n)	α = коэффициент заполнения; O(1) если α мала
Вставка	O(1 + α) амортизировано	O(n)	Изредка O(n) для resize, но амортизировано O(1)
Удаление	O(1 + α)	O(n)	Как поиск + удаление

Где α = элементы / корзины и n = всего элементов.

Амортизированный анализ расширения:

Когда коэффициент заполнения превышает пороговое значение (например, 0.75), таблица удваивается в размере и каждый элемент переэширивается. Одна вставка, вызывающая переэширование, стоит O(n). Но это редко: таблица не может удвоиться более чем O(log n) раз. Во время последовательности n вставок, начиная с маленькой таблицы, общая работа по переэшированию O(n) + O(n/2) + O(n/4) + … = O(2n), или O(1) на вставку в среднем.

Худший случай: O(n) поиск.

Если все n ключей отображаются в один индекс (плохая функция хеша, враждебный вход, или невезение), вся таблица становится одной длинной цепочкой, и поиск становится O(n).

Пример: если ты хешируешь только первый символ, все слова, начинающиеся с ‘A’, коллизируют.

На практике:

С хорошей функцией хеша (например, умножение на большое простое число, сворачивание битов), коллизии редки и цепочки короткие.
Коэффициент заполнения ≤ 0.75 типичен; цепочки в среднем 0.75 элементов.
O(1) в среднем поиск надёжен для типичных (не враждебных) входов.

Практика 0 / 5

В хеш-таблице с цепочками, коллизия происходит когда два разных ключа отображаются в одинаковый индекс. Как коллизия разрешается?

Хеш-таблица имеет 100 элементов и 20 корзин. Какой коэффициент заполнения?

С разделённым цепочками, средняя длина цепочки равна коэффициенту заполнения. Если коэффициент заполнения ≤ 0.75, какова средняя длина цепочки?

Когда коэффициент заполнения хеш-таблицы превышает пороговое значение (например, 0.75), что происходит во время переэширования?

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

Edge cases

Пустые корзины: В хеш-таблице с разделённым цепочками, некоторые корзины могут остаться пустыми если функция хеша не распределяет ключи равномерно. Это нормально и не признак неудачи; это просто означает, что те индексы были невезучими.

Очень высокий коэффициент заполнения: Если ты вставляешь без переэширования и коэффициент заполнения растёт без ограничений (например, α = 100), цепочки становятся очень длинными и среднее время поиска O(1 + α) становится O(101), фактически медленный линейный сканирование. Поэтому реальные хеш-таблицы переэширивают.

Удаление и сжатие: Когда элементы удаляются, коэффициент заполнения уменьшается. Некоторые реализации сжимают таблицу (например, когда α < 0.25) чтобы избежать потери памяти. Сжатие также требует O(n) переэширования.

lesson.inset.misconception

“Все ключи в конце концов коллизируют если таблица полна.” Не совсем. Даже если коэффициент заполнения высок (скажем, 2.0), не все ключи коллизируют; они распределены по корзинам, с некоторыми корзинами содержащими 0, 1, 2, или больше ключей. Коэффициент заполнения это средняя длина цепочки, не гарантия что все коллизируют. Однако, высокий коэффициент заполнения означает более длинные цепочки в среднем, поэтому переэширование чтобы снизить коэффициент заполнения важно.

“Переэширование это потраченная работа.” Переэширование это O(n) на resize, но размеры удваиваются, поэтому ты переэшириваешь O(log n) раз в итого. Амортизированная стоимость O(1) на вставку. Эта маленькая постоянная накладка стоит выгоды от держания цепочек короткими.

Check yourself

Викторина

Почему поиск в хеш-таблице O(1) в среднем но O(n) в худшем случае?

Recap

Коллизия происходит когда два разных ключа отображаются в одинаковый индекс. Разделённые цепочками разрешают коллизии, сохраняя связный список в каждой корзине; когда коллизия происходит, добавь новую пару ключ–значение в список. Чтобы найти ключ, захеши его, затем сканируй короткий список в той корзине.

Ключевые факты:

Коэффициент заполнения α = элементы / корзины. Он равен средней длине цепочки. Держи его маленьким (≤ 0.75) чтобы сохранять короткие цепочки.
Среднее время поиска = O(1 + α). С хорошей функцией хеша и малым α, это O(1).
Переэширование: Когда α превышает пороговое значение, выделить больший массив и переэширить каждый элемент. Стоимость: O(n) за переэширование, но амортизировано O(1) за вставку на протяжении многих операций.
Амортизированный анализ: Один O(n) resize дорог, но происходит редко. На протяжении последовательности n вставок, общая работа resize это O(n), поэтому O(1) на вставку в среднем.
Худший случай O(n): Если все ключи коллизируют в одну корзину (плохая функция хеша или враждебный вход), поиск становится линейным сканированием. Это редко с хорошей функцией хеша.
Хорошая функция хеша: Распределяет ключи равномерно, делая коллизии редкими и цепочки короткими. Защищает от деградации в худший случай.

Хеш-таблицы O(1) в среднем и O(n) в худшем. С правильным дизайном (хорошая функция хеша, управление коэффициентом заполнения, переэширование), они надёжны и быстры на практике.

Продолжить восхождение ↑Хеширование: тест с выбором ответа