Коллизии, решённые цепочками

Tier 1Бесплатно

Elman HuseynovОбновлено 2026-10-21

Уровень

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

1. Задача

На шаге 14 хеш-функция превращала ключ в номер корзины. Поиск перестал проходить весь список и стал заглядывать в одну корзину. Но два разных ключа могут получить один и тот же номер корзины. Это коллизия. Если корзина вмещает только одно значение, второй ключ затрёт первый, и данные пропадут.

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

2. Простыми словами

Возьми два ключа из тестов, "a" и "i", и таблицу из 8 корзин. Хеш "a" равен 1, и хеш "i" тоже равен 1. Обоим ключам место в корзине 1.

Поэтому в корзине 1 лежит короткий список. В нём сначала ["a", 1], потом ["i", 2]: каждый ключ хранится рядом со своим значением. Чтобы прочитать "i", идёшь в корзину 1 и проходишь её список. У ["a", 1] ключ не тот, у ["i", 2] тот, ответ 2. Понадобилось две проверки. Остальные 7 корзин ты даже не открывал. Общая корзина не беда, пока ни одна корзина не переполнена.

3. Идея

Корзина это ячейка таблицы, в которую попадает ключ. Когда два ключа попадают в одну корзину, это коллизия. Метод цепочек решает её так: каждая корзина хранит небольшой список записей, а не одно значение. Этот список называют цепочкой.

Каждая запись в цепочке это пара из ключа и его значения: [ключ, значение]. Хранить нужно и ключ, и значение. В одной корзине может лежать несколько разных ключей, и отличить их можно только по ключу, который лежит рядом со значением.

Каждая операция начинается с двух одинаковых шагов. Сначала хешируем ключ и выбираем корзину. Потом идём по короткой цепочке этой корзины и сравниваем каждый сохранённый ключ с тем, который ищем.

set(key, value): идём по цепочке. Если запись с таким ключом уже есть, заменяем её значение. Если совпадения нет, добавляем новую пару [ключ, значение].
get(key) и has(key): идём по цепочке и возвращаем найденное значение (или «да» и «нет» для has). Если цепочка кончилась, а совпадения не было, такого ключа нет.
delete(key): идём по цепочке и убираем только пару с совпавшим ключом.

Хеш тот же, что на шаге 14: складываем коды символов ключа и берём остаток от деления на число корзин. В нашей таблице всегда 8 корзин, расти она пока не умеет.

Проследим по шагам. set("a", 1): код «a» равен 97, 97 % 8 = 1, корзина 1. Цепочка пуста, добавляем ["a", 1]. set("i", 2): код «i» равен 105, 105 % 8 = 1, снова корзина 1. Это коллизия. В цепочке есть только ["a", 1], ключ не совпадает, поэтому добавляем ["i", 2]. Теперь get("a"): корзина 1, первая же пара ["a", 1] совпала, возвращаем 1. get("i"): корзина 1, пара ["a", 1] не подходит, следующая ["i", 2] подходит, возвращаем 2. Оба ключа лежат в одной корзине, и оба находятся правильно.

4. Во что это обходится

Время в среднем O(1). Если хеш раскладывает ключи равномерно, каждая цепочка остаётся короткой, в ней пара записей. Хеш плюс короткий проход стоят примерно постоянное время, сколько бы ключей ни было в таблице.

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

Память O(n): по одной паре [ключ, значение] на каждый ключ плюс 8 списков-корзин. Это цена доступа за O(1) в среднем.

6. Где это встречается

Так устроены настоящие хеш-таблицы внутри языков. HashMap в Java использует метод цепочек. Когда цепочка становится слишком длинной, Java превращает её в сбалансированное дерево (структуру, где поиск идёт за O(log n)). Хранилища сессий так связывают токен входа с пользователем. На той же схеме из корзин и цепочек работают таблицы символов в компиляторах, таблицы маршрутов (какой код отвечает на какой адрес) и кэши в памяти. Когда ты один раз написал такую таблицу, map.get(key) перестаёт быть загадкой: это хеш и короткий проход по цепочке.

На LeetCode

Задачи с собеседований, где хеш-таблицу или хеш-множество нужно написать самому, и уточняющий вопрос о том, что будет, когда два ключа столкнутся.

706.Design HashMap (откроется в новой вкладке)Лёгкая
Каждая корзина хранит цепочку пар [key, value], а put, get и remove проходят по ней, как set, get и delete в уроке.
705.Design HashSet (откроется в новой вкладке)Лёгкая
Те же цепочки, только с одними ключами, ведь множество не хранит значений.
1.Two Sum (откроется в новой вкладке)Лёгкая
Реши её своей таблицей с цепочками вместо Map, храня каждое число с его индексом.

Твоя задача (Tier 1)

Допиши четыре метода класса HashMap: set, get, has и delete. Конструктор (8 корзин), вспомогательный метод _hash и свойство size уже написаны.

Два ключа могут попасть в одну корзину (коллизия). Метод цепочек решает это: каждая корзина это список пар [key, value]. Каждый метод хеширует ключ, берёт его корзину и идёт по её короткому списку.

Меняют таблицу: set и delete.
Возвращают: get даёт значение или ничего; has даёт true или false; delete даёт true или false.

Шаги:

set(key, value): найди корзину через _hash(key). Иди по её парам. Если у пары тот же ключ, замени её значение и закончи (размер не меняется). Если совпадения нет, добавь [key, value] в корзину и прибавь 1 к размеру.
get(key): иди по корзине ключа. Верни значение совпавшей пары или ничего (undefined), если совпадения нет.
has(key): иди по корзине ключа. Верни true, если ключ там есть, иначе false.
delete(key): иди по корзине ключа. Если у пары тот же ключ, убери ровно эту одну пару, отними 1 от размера и верни true. Если такой пары нет, верни false.

Готово, когда проходят все тесты:

set("a",1), set("b",2), затем get("a") -> 1, get("b") -> 2, size -> 2
set("a",99) поверх "a" -> get("a") -> 99, size остаётся 2 (замена значения, новой пары нет)
set("a",1), set("i",2) попадают в одну корзину, но get("a") -> 1 и get("i") -> 2 (коллизия, оба значения сохранены)
после delete("a"): has("a") -> false, get("i") всё ещё 2; второй delete("a") -> false
пустая таблица: get("anything") -> undefined, has("anything") -> false, delete("anything") -> false, size -> 0

Практика

HashMap with separate chaining

export class HashMap {
  constructor() {
    this.numBuckets = 8;
    this.buckets = Array.from({ length: this.numBuckets }, () => []);
    this._size = 0;
  }

  _hash(key) {
    let sum = 0;
    for (let i = 0; i < key.length; i++) sum += key.charCodeAt(i);
    return sum % this.numBuckets;
  }

  set(key, value) {
    // Your code here. The task is described in the box above the editor.
  }

  get(key) {
    // Your code here. The task is described in the box above the editor.
  }

  has(key) {
    // Your code here. The task is described in the box above the editor.
  }

  delete(key) {
    // Your code here. The task is described in the box above the editor.
  }

  get size() {
    return this._size;
  }
}

Ты здесь как гость

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

Завести бесплатный аккаунт Войти

Лестница подсказок

Застрял? Открывай по одной, но сначала попробуй сам.

НазадКак хеш-таблица находит ячейку ДалееКоллизии через пробирование (открытая адресация)