Kodlo-chan
238 lines
20 KiB
Markdown
238 lines
20 KiB
Markdown
# Задача 10 — хеш-таблица с открытой адресацией
|
||
|
||
> Перед этой задачей прочитай урок `lessons/D1_algo.md` (разделы 3 и 5) — там разобран
|
||
> принцип и есть рабочий образец с цепочками. Здесь то же самое, но сложнее: коллизии
|
||
> разрешаются **внутри массива**.
|
||
|
||
## Глава I. Общая информация
|
||
|
||
- **Цель:** научиться писать контейнер, который используется в реальном коде (кэши,
|
||
таблицы маршрутизации, счётчики в логах) и который спрашивают на собеседовании в формате
|
||
«а сам сможешь?».
|
||
- **Почему это в Eltex:** таблицы MAC-адресов, FDB коммутатора, кэши сессий — всё это
|
||
хеш-таблицы с открытой адресацией и жёсткими требованиями к памяти.
|
||
- **Время:** 1,5–2,5 часа со ступенями. Если больше 3 часов — не долби в одиночку, скажи мне.
|
||
- **Что сдаётся:** файл `solution.cpp`, проходящий `python3 grade.py 10`.
|
||
|
||
**Факты для карточек**
|
||
- base | Сколько времени закладывается на задачу 10? — 1,5–2,5 часа со ступенями
|
||
- base | Какой командой проверяется решение? — `python3 grade.py 10`
|
||
- deep | Где в реальных устройствах используется похожая структура? — таблицы MAC-адресов (FDB) коммутатора, кэши сессий — открытая адресация с жёсткими ограничениями по памяти
|
||
|
||
Почему дальше: прежде чем писать код, нужно понять, почему индекс считается через `&`,
|
||
а не через `%`, и что физически происходит при коллизии.
|
||
|
||
## Глава II. Механизм: индекс, зондирование, tombstone, load factor
|
||
|
||
**Индекс через маску.** `idx = hash & (cap - 1)` работает как «остаток от деления», только
|
||
если `cap` — степень двойки. Причина: у степени двойки `cap - 1` в двоичном виде — это
|
||
подряд идущие единицы во всех младших битах (например, `cap = 8 = 0b1000` → `cap-1 = 0b0111`).
|
||
Операция `AND` с такой маской обнуляет все биты хеша выше этой границы и оставляет ровно
|
||
младшие `log2(cap)` бит — а это математически то же самое, что `hash mod cap`. Пример:
|
||
`cap = 8` (маска `0b111`), `hash = 19` (`0b10011`) → `19 & 7 = 3`.
|
||
`%` работает для любой ёмкости, но требует инструкции деления (на некоторых платформах
|
||
дороже, чем сдвиг/AND); отсюда практика ограничивать ёмкость степенью двойки и считать
|
||
индекс битовой маской.
|
||
|
||
**Линейное зондирование.** Если ячейка `idx` занята, пробуем `(idx+1) & (cap-1)`, потом
|
||
`(idx+2) & (cap-1)` и так по кругу, пока не найдём свободную ячейку (для вставки) или
|
||
нужный ключ (для поиска). Механически это обход массива по кругу начиная с `idx`.
|
||
|
||
**Tombstone.** Удалять «в ноль» (ставить `EMPTY`) нельзя: если между началом зондирования
|
||
и искомым элементом появится пустая ячейка, поиск остановится на ней раньше, чем дойдёт до
|
||
элемента — элемент физически на месте, но недостижим для `get`. Поэтому удалённая ячейка
|
||
помечается **tombstone** — «здесь был элемент, поиск должен идти дальше», но **вставка**
|
||
может переиспользовать tombstone-ячейку под новый ключ.
|
||
|
||
**Load factor и длина пробега.** `load = size / capacity`. По формуле среднего числа проб
|
||
при линейном зондировании (Кнут): удачный поиск — `0.5·(1 + 1/(1-load))` проб,
|
||
неудачный — `0.5·(1 + 1/(1-load)²)`. При `load = 0.7`: удачный поиск ≈ 2,2 пробы,
|
||
неудачный ≈ 6,1. При `load = 0.9`: удачный ≈ 5,5, неудачный ≈ 50,5 — рост нелинейный,
|
||
именно поэтому порог держат на 0.7, а не поднимают его «для экономии памяти».
|
||
|
||
**Факты для карточек**
|
||
- base | Почему `hash & (cap-1)` эквивалентно `hash % cap`? — только если `cap` — степень двойки: `cap-1` в двоичном виде — маска из всех младших бит, AND с ней даёт тот же результат, что остаток от деления
|
||
- base | Пример: `cap=8` (маска `0b111`), `hash=19` (`0b10011`). Индекс? — `19 & 7 = 3`
|
||
- core | Среднее число проб при удачном поиске, load factor 0.7? — ≈2,2 (формула Кнута `0.5·(1+1/(1-0.7))`)
|
||
- core | То же при load factor 0.9? — ≈5,5 — рост почти в 2,5 раза от значения при 0.7
|
||
- deep | Среднее число проб при НЕудачном поиске, load factor 0.9? — ≈50,5 (`0.5·(1+1/(1-0.9)²)`) — на порядок хуже удачного поиска
|
||
- core | Почему `EMPTY` вместо `TOMBSTONE` после удаления ломает поиск чужих ключей? — поиск идёт по цепочке проб до первой `EMPTY`; если такая ячейка появляется раньше искомого ключа, элементы за ней в этой цепочке становятся ненаходимыми, хотя физически на месте
|
||
|
||
Почему дальше: механизм понятен — теперь нужен точный интерфейс и числа, по которым
|
||
`grade.py` проверяет решение.
|
||
|
||
## Глава III. Задание
|
||
|
||
Свой контейнер, `std::unordered_map` использовать нельзя. Интерфейс ровно такой:
|
||
|
||
```c++
|
||
class HashTable {
|
||
public:
|
||
explicit HashTable(std::size_t initial_capacity = 16);
|
||
void put(int key, int value); // обновляет значение, если ключ уже есть
|
||
bool get(int key, int& out) const; // false — ключа нет
|
||
bool erase(int key); // false — ключа не было
|
||
std::size_t size() const;
|
||
std::size_t capacity() const; // степень двойки, >= 16
|
||
};
|
||
```
|
||
|
||
Требования:
|
||
|
||
- **ключи с совпадающими младшими битами обязаны находиться** — тест вставляет 512 ключей,
|
||
кратных 16, то есть все они попадают в одну-две стартовые ячейки. Это проверка
|
||
зондирования, а не «повезло с хешем»;
|
||
- `put` 100 000 ключей суммарно быстрее 2 секунд;
|
||
- после вставок `capacity()` растёт (степень двойки), загрузка остаётся ≤ 0.7;
|
||
- `size()` честно считает элементы: повторный `put` того же ключа **не** увеличивает `size`;
|
||
- `erase` работает: после удаления ключ не находится, но поиск другого ключа, стоявшего
|
||
за ним в цепочке зондирования, по-прежнему работает;
|
||
- удаление и последующая вставка не должны «терять» элементы, а `size()` после удаления
|
||
и вставки возвращается к правильному значению.
|
||
|
||
**Факты для карточек**
|
||
- base | Сколько ключей вставляет тест на кластеризацию и какие они? — 512 ключей, кратных 16
|
||
- base | За какое время должны пройти 100 000 вставок? — быстрее 2 секунд
|
||
- base | Какой порог load factor держит таблица? — ≤ 0.7
|
||
- base | Минимальная ёмкость таблицы по умолчанию? — 16, степень двойки
|
||
|
||
## Глава IV. Ступени (делай по одной, после каждой — прогон)
|
||
|
||
Не пытайся написать всё сразу. Каждая ступень проверяется отдельно, и это нормальный
|
||
порядок работы инженера.
|
||
|
||
**Ступень 1. Хеш-функция и индекс (20 минут).**
|
||
Напиши `size_t hash_of(int key)` и `size_t index_of(int key) const`. Для целых ключей
|
||
хорошая хеш-функция — перемешать биты умножением на большую нечётную константу:
|
||
`h = (uint64_t)key * 2654435761u;` (это `2^32 / φ` при золотом сечении `φ ≈ 1.618`,
|
||
классика — умножение на нечётную константу обратимо по модулю `2^32` и «размазывает»
|
||
младшие биты ключа по всей ширине результата, поэтому соседние по младшим битам ключи
|
||
после умножения расходятся по разным индексам).
|
||
Проверь себя на бумаге или в маленькой программе: для `cap = 16` ключи 16, 32, 48 должны
|
||
дать **разные** индексы. Если дают одинаковые — ты забыл перемешать биты, и все кратные 16
|
||
свалятся в одну ячейку.
|
||
|
||
**Ступень 2. Массивы и конструктор (15 минут).**
|
||
Нужны три вещи: массив значений, массив признаков состояния ячейки и счётчик размера.
|
||
Признаки: `EMPTY`, `OCCUPIED`, `TOMBSTONE`. Ёмкость в конструкторе приводи к степени двойки
|
||
(16 по умолчанию) — тест ожидает `capacity() >= 16` и степень двойки.
|
||
После этого прогон должен уже собираться, а часть проверок на пустой таблице — проходить.
|
||
|
||
**Ступень 3. Вставка без перехеширования (30 минут).**
|
||
Идёшь по ячейкам от `index_of(key)`, пока не найдёшь: свой ключ (обновить значение),
|
||
`EMPTY` или `TOMBSTONE` (вставить). **Важно:** если ключ найден — не увеличивай `size()`.
|
||
Tombstone можно переиспользовать под вставку, но тогда его признак меняется на `OCCUPIED`.
|
||
|
||
**Ступень 4. Поиск (15 минут).**
|
||
Идёшь так же, но: свой ключ — нашли; `EMPTY` — стоп, ключа нет; `TOMBSTONE` — идём дальше
|
||
(здесь легко ошибиться и вернуть `false` раньше времени).
|
||
|
||
**Ступень 5. Удаление через tombstone (20 минут).**
|
||
Нашёл ключ → ставим `TOMBSTONE`, `size--`. Если ключа нет — `false`, ничего не меняем.
|
||
|
||
**Ступень 6. Перехеширование (30 минут).**
|
||
Когда `size * 10 > capacity * 7` (то есть `load > 0.7`), создай массив вдвое больше и
|
||
**заново вставь все занятые ключи** (tombstone не переносим — в новой таблице пусто).
|
||
Учти: после этого `size` не должен измениться, а пробеги станут короче (см. формулу проб
|
||
из главы II — вдвое большая ёмкость при том же `size` резко снижает `load`, а с ним и
|
||
среднее число проб). Прогон: `python3 grade.py 10`.
|
||
|
||
**Ступень 7. Прогон под санитайзерами (10 минут).**
|
||
`grade.py` уже собирает с ASAN/UBSAN — если он зелёный, память чистая. Отдельно проверь,
|
||
что деструктор освобождает ровно то, что выделил конструктор (или не выделяй вручную вовсе,
|
||
а используй `std::vector` — так короче и безопаснее).
|
||
|
||
## Глава V. Критерии приёмки
|
||
|
||
Задача сдана, когда `python3 grade.py 10` печатает `PASS` — это значит: сборка без
|
||
предупреждений, ASAN/UBSAN чистые, все проверки `ok`, включая 512 ключей, кратных 16,
|
||
перехеширование, удаление из середины цепочки и повторные вставки.
|
||
|
||
## Глава VI. Подсказки (открывать после первой честной попытки)
|
||
|
||
<details>
|
||
<summary>Не находит ключи, кратные 16</summary>
|
||
|
||
Ты используешь `key & (cap-1)` без перемешивания. Ключи 16, 32, 48, … в маске дают 0 —
|
||
все в одну ячейку, пробег растёт, а при большом числе ключей ты упираешься в «таблица
|
||
полна». Лечится хеш-функцией: умножить ключ на большую нечётную константу перед маской.
|
||
</details>
|
||
|
||
<details>
|
||
<summary>size() растёт от повторных put</summary>
|
||
|
||
Сначала ищи существующий ключ. Нашёл — обнови значение и выйди, `size++` не делай.
|
||
Увеличивай счётчик только когда записал в пустую или tombstone-ячейку.
|
||
</details>
|
||
|
||
<details>
|
||
<summary>После erase пропадают соседние ключи</summary>
|
||
|
||
Ты ставишь `EMPTY` вместо `TOMBSTONE`, и поиск обрывается на этом месте. `EMPTY` — только
|
||
для никогда не занятых ячеек; после удаления — `TOMBSTONE`.
|
||
</details>
|
||
|
||
<details>
|
||
<summary>Зацикливается при полной таблице</summary>
|
||
|
||
Цикл зондирования обязан ограничиться `capacity` шагами. Если таблица переполнилась —
|
||
значит не сработал порог перехеширования (0.7) или ты неверно считаешь `size`.
|
||
</details>
|
||
|
||
## Глава VII. Ловушки
|
||
|
||
- Забыть перемешать хеш (использовать `key` напрямую как индекс) → ключи, кратные 16,
|
||
все попадают в одну-две ячейки → кластеризация, пробег растёт линейно с числом таких
|
||
ключей → тест на 512 ключей, кратных 16, падает по таймауту или по «not found».
|
||
- Забыть про tombstone при rehash (перенести признак `TOMBSTONE` в новую таблицу вместо
|
||
того, чтобы его отбросить) → «мёртвые» ячейки переезжают и занимают место в новой
|
||
таблице без необходимости → эффективная ёмкость меньше заявленной, load factor растёт
|
||
быстрее ожидаемого.
|
||
- Хранить ключ отдельно от значения в параллельных массивах и перепутать индекс при
|
||
перестановке → ASAN поймает не сразу, а в момент обращения к рассинхронизированной
|
||
ячейке; надёжнее держать ключ и значение в одной структуре ячейки.
|
||
- Проверять `size == capacity` вместо load factor (`size * 10 > capacity * 7`) → таблица
|
||
почти полностью заполняется, пробеги становятся длиной в десятки-сотни ячеек (см. формулу
|
||
неудачного поиска при load → 1), суммарное время `put` уходит за лимит 2 секунды на
|
||
100 000 ключей.
|
||
|
||
## Проверь себя
|
||
|
||
<details>
|
||
<summary>1. Почему `cap = 17` был бы плохим выбором ёмкости таблицы?</summary>
|
||
`cap-1 = 16 = 0b10000` — не маска из подряд идущих единиц, поэтому `hash & (cap-1)`
|
||
перестаёт быть эквивалентно `hash % cap`: часть значений индекса становится недостижимой,
|
||
а распределение по ячейкам — неравномерным. Степень двойки — обязательное условие, при
|
||
котором работает битовая маска вместо деления.
|
||
</details>
|
||
|
||
<details>
|
||
<summary>2. Во сколько раз в среднем растёт число проб при удачном поиске, если load factor
|
||
вырастет с 0.7 до 0.9?</summary>
|
||
Примерно в 2,5 раза: `0.5·(1+1/(1-0.7)) ≈ 2,2` против `0.5·(1+1/(1-0.9)) ≈ 5,5`.
|
||
Для неудачного поиска рост ещё резче — с ≈6,1 до ≈50,5, то есть почти в 8 раз.
|
||
</details>
|
||
|
||
<details>
|
||
<summary>3. Почему при вставке нельзя сразу увеличивать `size`, не проверив, есть ли уже
|
||
такой ключ?</summary>
|
||
`put` обязан обновлять значение существующего ключа, а не создавать дубликат. Если
|
||
инкрементировать `size` без предварительного поиска ключа по цепочке зондирования,
|
||
повторная вставка одного и того же ключа завысит `size()` и тест на честный подсчёт
|
||
элементов упадёт.
|
||
</details>
|
||
|
||
<details>
|
||
<summary>4. Почему tombstone-ячейки не переносятся в новую таблицу при перехешировании?</summary>
|
||
В новой, увеличенной вдвое таблице нет старых цепочек зондирования — переносятся только
|
||
реально занятые ключи, вставленные заново с нуля. Перенос tombstone бессмысленно тратил бы
|
||
место в и без того более просторной таблице и не даёт никакого выигрыша, поскольку сами
|
||
цепочки проб после rehash пересчитываются заново.
|
||
</details>
|
||
|
||
## После сдачи
|
||
|
||
Разбор со мной: почему ёмкость — степень двойки; чем открытая адресация лучше цепочек по
|
||
кэшу и хуже по кластеризации; как tombstone-метки спасают поиск после удаления; как это
|
||
устроено в реальных FDB коммутаторов (там обычно хеш с цепочками и ограничением глубины).
|