unordered_*: hash, равенство, load factor, rehash

1. Как работает поиск: hash → bucket → ==

Если вы не понимаете, как контейнер устроен внутри, вы легко попадаете в типовые ловушки:

• «почему внезапно стало медленно» (почти всегда это про коллизии и плотность),
• «почему отвалились итераторы» (обычно где-то случился rehash),
• «почему порядок обхода “прыгает”» (потому что он не гарантируется контрактом).

Понимание внутренних терминов (bucket, load_factor, rehash) — это не «теория ради теории», а способ писать код, который не ломается при росте данных.

В std::map ключи упорядочены (дерево), и поиск идёт по сравнениям. В unordered_* другая философия: ключ превращается в число (хеш), и по этому числу мы быстро выбираем «коробку», где этот ключ должен лежать.

Два шага поиска

И вот здесь важный момент, который ломает ожидания новичка: хеш не доказывает, что ключ найден. Он только говорит «смотри вон в ту коробку». После этого контейнер делает второй шаг: сравнивает ключи через == (точнее, через объект-предикат равенства).

В требованиях к unordered_* это обычно описывают как наличие Hash и Pred, то есть «хешер» и «проверка равенства».

Если коротко, unordered_map делает примерно так:

key -> hash(key) -> номер bucket -> линейный поиск внутри bucket через ==

И именно поэтому нам нужны и hash, и равенство одновременно.

3. Buckets и коллизии

Поговорим про слово bucket. На русском это обычно переводят как «корзина» или «ведро». И честно говоря, «ведро» даже ближе по духу: мы берём ключи и «закидываем» в ведра по номеру.

Что такое bucket

Контейнер держит некоторое количество корзин: bucket_count(). Каждая корзина хранит ноль или несколько элементов.

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

Коллизии — это нормальная ситуация

Коллизия — это когда разные ключи дают один и тот же хеш (или попадают в одну и ту же корзину). Это не «ошибка» и не «ужас-ужас», это штатный режим работы хеш-таблицы. Поэтому unordered_map не может сказать «хеш совпал, значит ключ тот же». Он обязан проверить равенство.

Схема, чтобы было наглядно:

flowchart TD
    A["Ключ: 'alice'"] --> B["hash('alice') = 123456"]
    C["Ключ: 'bob'"] --> D["hash('bob') = 123999"]
    E["Ключ: 'ALICE'"] --> F["hash('ALICE') = 123456 (коллизия)"]

    B --> G["bucket = hash % bucket_count"]
    D --> G
    F --> G

    G --> H["Внутри bucket: сравнение ключей через == (KeyEqual)"]

4. Load factor и rehash

Теперь самое полезное слово дня: load factor. Если у вас ощущение, что это термин из стиральной машины — вы не одиноки. По смыслу похоже: «насколько мы забили барабан».

load_factor(): «плотность» хеш-таблицы

У unordered_* есть метод load_factor(). Идея очень простая:

load_factor ≈ size() / bucket_count()

То есть «сколько элементов в среднем приходится на одну корзину».

Если load_factor маленький, то в среднем в корзине мало элементов, и поиск внутри корзины (через ==) короткий.

Если load_factor большой, корзины переполнены, внутри каждой корзины приходится сравнивать много элементов. И тогда unordered_map начинает вести себя неприятно: вроде бы вы ожидали «почти O(1)», а получаете «что-то подозрительно похожее на O(N)».

Важно: в учебных задачах это часто не критично. Но как только вы начинаете хранить много данных (тысячи и десятки тысяч), разница становится заметной даже без профилировщика — просто «программа стала ощутимо задумчивой».

max_load_factor(): порог, после которого контейнер расширяется

У контейнера есть ещё и настройка: max_load_factor(). Это «порог плотности», после которого контейнер считает, что пора расширяться (то есть увеличивать число корзин).

На практике это работает так: вы вставляете элементы, size() растёт, load_factor() растёт, и когда он становится больше max_load_factor, контейнер может сделать rehash (перестроение).

Что делает rehash и почему это “с последствиями”

Когда контейнер делает rehash, он:

• меняет (обычно увеличивает) количество корзин,
• для каждого элемента пересчитывает, «в какую корзину он теперь попадает»,
• перекладывает элементы по новым корзинам.

Почему это ускоряет работу? Потому что bucket_count вырос, и load_factor обычно падает. Элементы распределяются по большему числу корзин, и внутри каждой корзины становится меньше сравнений.

Самая практическая часть: при перестройке итераторы могут стать недействительными. Даже если «вам кажется», что элемент всё тот же, он мог переехать.

Стандартные гарантии по инвалидированию итераторов и деталям поведения контейнеров уточняются и «доводятся» годами. Но базовая инженерная мысль для unordered_* очень простая: если контейнер может перестроиться, то хранить итераторы «на потом» опасно, особенно при активных вставках.

5. Управление ростом: reserve, rehash и мини-диагностика

Вектор вы уже «приручали» через reserve, чтобы не было лишних перевыделений памяти. В unordered_* похожая идея, но смысл чуть другой: мы заранее просим контейнер подготовить достаточно корзин под ожидаемое число элементов, чтобы реже происходил rehash.

reserve и rehash — это не одно и то же

С точки зрения интерфейса вы увидите два похожих метода:

• rehash(n) — попросить минимум n корзин (bucket count),
• reserve(n) — попросить подготовиться к n элементам (size), учитывая текущий max_load_factor.

В учебной практике вам почти всегда удобнее reserve, потому что вы мыслите «сколько элементов я сейчас загружу», а не «сколько корзин мне нужно для счастья».

Смотрим bucket_count и load_factor вживую

Сейчас сделаем маленький «диагностический» фрагмент. Он не про бизнес-логику, а про понимание поведения контейнера.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;

    std::cout << m.bucket_count() << '\n'; // например: 1 (зависит от реализации)
    m[10] = 1;
    m[20] = 2;

    std::cout << m.load_factor() << '\n';  // например: 0.5
}

Числа могут отличаться на разных компиляторах/библиотеках — и это нормально. Смысл не в том, чтобы «запомнить магическое число 13 корзин», а в том, чтобы понять: контейнер реально живёт своей жизнью, и эта жизнь выражается в bucket_count и load_factor.

Мини-пример: видно, что rehash может случиться автоматически

Покажем мысль «rehash — это событие» на коротком примере. Мы не будем ловить «плохие итераторы» (это легко превратить в UB-цирк), а просто увидим, что bucket_count может прыгать.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> s;

    std::cout << s.bucket_count() << '\n'; // было
    for (int i = 0; i < 100; ++i) s.insert(i);
    std::cout << s.bucket_count() << '\n'; // стало (часто больше)
}

Смысл такой: вставки увеличивают size(), растёт load_factor, и контейнер может расшириться, чтобы не превратиться в «одну корзину на всё человечество».

6. Практика: индекс по id и порядок обхода

Чтобы примеры не были «в вакууме», продолжим условное учебное приложение, которое мы развиваем по курсу: TaskBoard — консольная программа для хранения задач.

Быстрый индекс по id

Пусть у нас есть модель:

#include <string>

struct Task {
    int id{};
    std::string title;
};

Мы храним задачи в std::vector<Task> tasks; (потому что это удобно для обхода, печати, сортировок и т.д.). Но нам нужно быстро находить задачу по id. Для этого делаем индекс:

#include <cstddef>
#include <unordered_map>
#include <vector>

std::vector<Task> tasks;
std::unordered_map<int, std::size_t> pos_by_id; // id -> позиция в vector

Теперь ключевой момент: если мы загружаем много задач (например, из ввода), мы заранее знаем примерное количество. Значит, можем подготовить unordered_map:

#include <unordered_map>

void prepare_index(std::unordered_map<int, std::size_t>& pos_by_id, std::size_t n) {
    pos_by_id.reserve(n);           // меньше rehash при росте
    pos_by_id.max_load_factor(0.7f); // чуть более «разреженно»
}

Да, это уже похоже на «инженерию», но на самом деле это просто привычка: если вы заранее знаете размер данных, вы снижаете количество внутренних перестроений.

Почему нельзя рассчитывать на порядок в unordered_*

Если у std::map порядок обхода определён компаратором, то у unordered_* порядок обхода не гарантируется.

Это следует из самой природы «корзин»: элементы лежат «по хешам», а не «по возрастанию ключа». Более того, после rehash порядок может заметно измениться, потому что корзины другие, распределение другое, и внутреннее устройство может перестроиться.

Практическое правило простое: если вы хотите «вывести все элементы по ключу красиво», вы либо используете map, либо отдельно сортируете данные перед выводом.

7. Типичные ошибки при работе с unordered_*

Ошибка №1: думать, что hash(a) == hash(b) означает a == b.
Это одна из самых частых логических ловушек. Хеш — это способ быстро выбрать корзину, а не доказательство равенства. Коллизии нормальны, поэтому unordered_* всегда делает проверку равенства внутри корзины. Если держать это в голове, становится понятнее, почему «плохой хеш» замедляет контейнер: он создаёт много коллизий и заставляет делать много сравнений.

Ошибка №2: игнорировать load_factor и удивляться деградации скорости.
Новичок часто мыслит так: «unordered — значит всегда быстро». Но если таблица становится слишком плотной (мало корзин на много элементов), то внутри каждой корзины поиск становится длинным. Это не «сломалось», это контейнер честно выполняет свою работу, просто ему стало тесно. Понимание load_factor() и идеи max_load_factor() убирает мистику.

Ошибка №3: хранить итераторы/ссылки на элементы и потом активно вставлять новые.
Даже если вы не вызываете rehash() руками, он может случиться автоматически при росте контейнера. После этого итераторы могут стать недействительными. В результате появляются баги, которые выглядят как «рандомные падения» или «иногда пропадает элемент». Правильная привычка — либо не хранить итераторы, либо заранее делать reserve, если вы точно знаете масштаб вставок.

Ошибка №4: ожидать, что обход unordered_map будет упорядоченным.
Иногда пишут код, который «случайно работает», потому что на маленьких данных порядок выглядит стабильным. Потом добавили ещё 50 элементов — и вывод поехал. У unordered_* порядок — побочный эффект реализации, а не контракт. Если вам нужен стабильный порядок, выбирайте структуру данных под требование, а не под надежду.

Ошибка №5: путать reserve и «резерв памяти под значения».
У unordered_* reserve(n) — это не про «хочу заранее выделить память под значения так же, как у vector». Это про подготовку корзин так, чтобы при вставке n элементов не случалось слишком много перестроений. В голове полезно держать простую ассоциацию: vector::reserve борется с перевыделениями массива, unordered_map::reserve — с частыми rehash и ростом плотности.