# Задача 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. Подсказки (открывать после первой честной попытки)
Не находит ключи, кратные 16 Ты используешь `key & (cap-1)` без перемешивания. Ключи 16, 32, 48, … в маске дают 0 — все в одну ячейку, пробег растёт, а при большом числе ключей ты упираешься в «таблица полна». Лечится хеш-функцией: умножить ключ на большую нечётную константу перед маской.
size() растёт от повторных put Сначала ищи существующий ключ. Нашёл — обнови значение и выйди, `size++` не делай. Увеличивай счётчик только когда записал в пустую или tombstone-ячейку.
После erase пропадают соседние ключи Ты ставишь `EMPTY` вместо `TOMBSTONE`, и поиск обрывается на этом месте. `EMPTY` — только для никогда не занятых ячеек; после удаления — `TOMBSTONE`.
Зацикливается при полной таблице Цикл зондирования обязан ограничиться `capacity` шагами. Если таблица переполнилась — значит не сработал порог перехеширования (0.7) или ты неверно считаешь `size`.
## Глава 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 ключей. ## Проверь себя
1. Почему `cap = 17` был бы плохим выбором ёмкости таблицы? `cap-1 = 16 = 0b10000` — не маска из подряд идущих единиц, поэтому `hash & (cap-1)` перестаёт быть эквивалентно `hash % cap`: часть значений индекса становится недостижимой, а распределение по ячейкам — неравномерным. Степень двойки — обязательное условие, при котором работает битовая маска вместо деления.
2. Во сколько раз в среднем растёт число проб при удачном поиске, если load factor вырастет с 0.7 до 0.9? Примерно в 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 раз.
3. Почему при вставке нельзя сразу увеличивать `size`, не проверив, есть ли уже такой ключ? `put` обязан обновлять значение существующего ключа, а не создавать дубликат. Если инкрементировать `size` без предварительного поиска ключа по цепочке зондирования, повторная вставка одного и того же ключа завысит `size()` и тест на честный подсчёт элементов упадёт.
4. Почему tombstone-ячейки не переносятся в новую таблицу при перехешировании? В новой, увеличенной вдвое таблице нет старых цепочек зондирования — переносятся только реально занятые ключи, вставленные заново с нуля. Перенос tombstone бессмысленно тратил бы место в и без того более просторной таблице и не даёт никакого выигрыша, поскольку сами цепочки проб после rehash пересчитываются заново.
## После сдачи Разбор со мной: почему ёмкость — степень двойки; чем открытая адресация лучше цепочек по кэшу и хуже по кластеризации; как tombstone-метки спасают поиск после удаления; как это устроено в реальных FDB коммутаторов (там обычно хеш с цепочками и ограничением глубины).