Коллизии через пробирование (открытая адресация)

Tier 1Бесплатно

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

Уровень

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

1. Задача

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

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

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

Возьми три ключа из тестов: "a", "i" и "q". В таблице из 8 ячеек все три начинают с ячейки 1. "a" занимает ячейку 1. "i" видит, что ячейка 1 занята, и идёт дальше, в ячейку 2. "q" видит занятыми ячейки 1 и 2 и попадает в ячейку 3.

Чтобы найти "q", начинаешь с ячейки 1 и идёшь вперёд тем же путём: в ячейке 1 лежит "a", в ячейке 2 "i", в ячейке 3 "q". Ты останавливаешься, когда нашёл ключ или дошёл до ячейки, которой никогда не пользовались. Такая ячейка значит, что ключа в таблице нет: иначе он занял бы именно её.

Теперь сложная часть. Удали "i" и просто очисти ячейку 2. Ищи "q" снова: в ячейке 1 лежит "a", ячейка 2 пуста, поиск останавливается и отвечает «такого ключа нет». А "q" лежит в ячейке 3. Решение такое: оставить в ячейке 2 метку «здесь что-то было, сейчас пусто». Такую метку называют надгробием. Поиск проходит мимо надгробия и идёт дальше. А новый ключ на место надгробия класть можно.

3. Идея

Все записи лежат в одном массиве постоянного размера. Его размер называют вместимостью (capacity), здесь она равна 8. В каждом слоте одно из трёх: пусто, настоящая пара [ключ, значение] или надгробие (tombstone). Надгробие это метка «здесь раньше жил ключ».

Чтобы положить ключ, сначала находим его стартовый слот. Хеш считаем как раньше: сумма кодов символов ключа, остаток от деления на вместимость. Код "a" равен 97, 97 % 8 равно 1, поэтому "a" начинает со слота 1. Этот первый слот называют домашним слотом (home slot) ключа.

Если домашний слот занят другим ключом, это коллизия. Её решает линейное пробирование (linear probing): идём вперёд по одному слоту, 2, потом 3 и так далее. После последнего слота (7) переходим на слот 0. Идём, пока не найдём пустой слот или тот же самый ключ. В пустой слот кладём пару. Если нашли тот же ключ, заменяем его значение на месте, а счётчик записей не меняем.

get и has идут тем же путём: начинают с домашнего слота и шагают вперёд. Как только нашли ключ, возвращают значение. Как только дошли до пустого слота, останавливаются и отвечают «такого ключа нет». Почему пустой слот это доказательство: при вставке ключ занял бы первый свободный слот на своём пути. Значит, если ключ есть, он стоит раньше пустого слота.

Надгробие нужно именно в delete. Сделать удалённый слот пустым нельзя: пустой слот останавливает любой будущий поиск. Тогда любой ключ, который при вставке прошёл мимо этого слота дальше, вдруг станет ненаходимым. Поэтому при удалении в слот пишут надгробие. Поиск проходит мимо надгробий и идёт дальше. А set может положить новый ключ на место надгробия.

Проследим на вместимости 8. set("a", 10): домашний слот 1 пуст, кладём туда. set("i", 20): код "i" равен 105, 105 % 8 равно 1. Слот 1 занят "a", поэтому шагаем в слот 2, он пуст, кладём туда. set("q", 30): код "q" равен 113, 113 % 8 тоже равно 1. Проходим "a" в слоте 1 и "i" в слоте 2 и кладём "q" в слот 3. Теперь delete("i"): в слоте 2 появляется надгробие. get("q"): начинаем со слота 1, там "a", не то. Шагаем в слот 2, там надгробие, проходим мимо. Шагаем в слот 3, там "q", нашли. Ключ по-прежнему находится, и это заслуга надгробия. Пустой слот 2 остановил бы поиск, и get("q") вернул бы «ничего».

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

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

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

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

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

Открытую адресацию используют многие хеш-таблицы в рабочих системах. На ней работает dict в CPython (основной версии Python), а он есть почти в каждой программе на Python. При удалении dict оставляет надгробия (их там называют «dummy») ровно по той причине, которую ты только что разобрал. Быстрые таблицы на C++, например flat_hash_map из библиотеки Abseil от Google и более старая dense_hash_map, хранят записи в одном плоском массиве, чтобы хорошо работать с кэшем процессора. Её часто выбирают, когда нужна быстрая таблица в памяти и важно, как данные лягут в кэш. Примеры: таблицы маршрутизации, таблицы символов в компиляторах, пулы интернирования (хранилища, где каждая строка лежит в одном экземпляре). И каждому автору такой таблицы пришлось решать задачу удаления через надгробия.

На LeetCode

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

706.Design HashMap (откроется в новой вкладке)Лёгкая
Напиши её с линейным пробированием и надгробиями, чтобы remove не ломал поиск ключей, которые лежат дальше.
705.Design HashSet (откроется в новой вкладке)Лёгкая
То же пробирование по одному плоскому массиву, только с ключами.
622.Design Circular Queue (откроется в новой вкладке)Средняя
Переход дальше через (i + 1) % capacity устроен так же, как переход пробирования после последней ячейки.

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

Собери класс HashMap поверх одного плоского списка из 8 слотов. Методы: set, get, has, delete и свойство size. Конструктор и вспомогательный метод _hash уже даны.

Каждый слот хранит одно из трёх: пусто, метку удаления (надгробие) или пару [key, value]. При коллизии иди к следующему слоту по формуле (home + step) % 8: после слота 7 она даёт слот 0.

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

Шаги:

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

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

set("a",1), set("b",2) -> get("a") -> 1, has("a") -> true, size -> 2
set("a",10), set("i",20), set("q",30) попадают в один домашний слот, но все три находятся, например get("q") -> 30
set("a",1), затем set("a",9) -> get("a") -> 9, size -> 1 (замена на месте)
после delete("i") ключ, который стоит за ним, всё ещё находится: get("q") -> 30, has("i") -> false
заполни все 8 слотов, тогда новый set("i",99) ничего не делает: get("i") -> undefined, size -> 8
пустая таблица: get("x") -> undefined, delete("x") -> false, size -> 0

Практика

Hash map by open addressing (linear probing + tombstone delete)

class HashMap { set(key, value); get(key) -> value|undefined; has(key) -> bool; delete(key) -> bool; get size -> int }

const CAPACITY = 8;
const TOMB = Symbol('tombstone');

export class HashMap {
  constructor() {
    this.slots = new Array(CAPACITY).fill(null);
    this._size = 0;
  }

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

  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() {
    // Your code here. The task is described in the box above the editor.
  }
}

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

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

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

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

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

НазадКоллизии, решённые цепочками ДалееЗаполненность и расширение таблицы