unordered_*: хеш, рівність, load factor, rehash

1. Як працює пошук: hash → bucket → ==

Якщо ви не розумієте, як контейнер улаштований усередині, вам легко потрапити в типові пастки:

• «чому раптом усе стало повільно» (зазвичай причина в колізіях і щільності),
• «чому ітератори раптом стали недійсними» (зазвичай десь стався rehash),
• «чому порядок обходу постійно змінюється» (тому що контракт цього не гарантує).

Розуміння внутрішніх термінів (bucket, load_factor, rehash) — це не «теорія заради теорії», а спосіб писати код, який не ламається зі збільшенням обсягу даних.

У std::map ключі впорядковані (це дерево), і пошук виконується через порівняння. В unordered_* інша філософія: ключ перетворюється на число (хеш), і за цим числом ми швидко визначаємо «коробку», де цей ключ має бути.

Два кроки пошуку

Тут є важливий момент, на якому новачки часто спотикаються: хеш не доводить, що ключ знайдено. Він лише каже: «шукайте он у тій коробці». Після цього контейнер робить другий крок: порівнює ключі через == (точніше, через обʼєкт-предикат рівності).

У вимогах до unordered_* це зазвичай формулюють через наявність Hash і Pred, тобто хешера та предиката рівності.

Якщо коротко, unordered_map працює приблизно так:

key -> hash(key) -> номер bucket -> лінійний пошук усередині bucket через ==

І саме тому нам одночасно потрібні і хеш, і перевірка рівності.

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 і мінідіагностика

Ви вже «приручали» vector через 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 і зростанням щільності.