Хеш-таблиця чи дерево

1. Контейнер «ключ → значення»

Якщо у std::vector усе влаштовано за принципом «елементи лежать підряд, і кожен має індекс», то в реальних задачах часто потрібно інше: знайти не «елемент № 7», а «користувача з id=42», «налаштування з імʼям "theme"», «товар за артикулом» або «лічильник для слова "apple"». І зробити це хочеться швидко, без перегляду всього списку щоразу.

Уявіть, що ви ведете невеликий консольний застосунок TaskBook — наш навчальний мініпроєкт. Ви зберігаєте задачі, у кожної є id і текст. Якщо задач лише 10, їх іще можна шукати лінійно. А коли їх 10 000, лінійний пошук перетворюється на обовʼязкову ранкову зарядку для процесора. Він, звісно, радий, але користувач — не завжди.

Ідея асоціативних контейнерів у C++ проста: ми зберігаємо дані так, щоб швидко відповідати на запитання «чи є такий ключ?» і «яке значення відповідає цьому ключу?».

Модель: «словник», де елемент — пара

Перш ніж порівнювати map і unordered_map, важливо домовитися про базову модель. В обох контейнерах ми зберігаємо пари: ключ і значення. Ключ — це те, за чим ми шукаємо, а значення — те, що отримуємо.

Наприклад: «імʼя → вік», «id → задача», «слово → кількість», «код_помилки → текст». У памʼяті це приблизно виглядає як набір записів такого виду:

key1 -> value1
key2 -> value2
...

У C++ всередині це зазвичай зберігається як std::pair<const Key, Value>. Не потрібно завчати це як заклинання, але корисно памʼятати: під час обходу контейнера ми отримуємо і ключ, і значення. Тому тут особливо зручні structured bindings: менше стрілочок first/second, більше людської мови.

2. std::map: впорядкований словник

std::map<Key, Value> — це асоціативний контейнер, який зберігає елементи у порядку ключів. З погляду поведінки він схожий на телефонну книгу: ви можете швидко знайти запис за імʼям, а коли «гортаєте» книгу, імена йдуть за абеткою.

Під капотом map зазвичай реалізовано як збалансоване дерево (часто згадують червоно-чорне дерево). Зараз вам не потрібно вміти малювати його на співбесіді, але корисно розуміти наслідки: операції пошуку, вставки й видалення мають складність O(log N), оскільки на кожному кроці дерево звужує область пошуку.

Мінікартинка: інтуїтивно

Якщо дуже спрощено, дерево схоже на «опитувальник»:

• ключ менший за поточний — ідемо ліворуч
• більший — ідемо праворуч
• збігся — знайшли

І так кілька кроків, доки не знайдемо потрібний ключ або не впремося в «порожньо».

Коли map справді зручний

map обирають, коли:

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

4. std::unordered_map: словник без порядку

std::unordered_map<Key, Value> розвʼязує ту саму задачу «ключ → значення», але робить це інакше: замість дерева він зазвичай використовує хеш-таблицю. У стандарті це сімейство контейнерів так і називається — unordered associative containers.

Головна ідея така: ми беремо ключ, обчислюємо для нього число (хеш) і за цим числом приблизно визначаємо, де шукати. Якщо все складається вдало, пошук, вставка й видалення в середньому працюють за O(1) (тобто це «майже константа», яка не залежить лінійно від кількості елементів). На практиці це часто означає просто «дуже швидко».

Мінікартинка: інтуїтивно

Хеш-таблицю можна уявити як масив «кошиків» (buckets):

1. ключ перетворюється на число (хеш)
2. за ним вибирається кошик
3. усередині кошика уточнюємо результат (на випадок колізій)

Колізії — це ситуація, коли різні ключі потрапляють в один кошик. Це нормально: контейнер однаково перевірить рівність ключів і знайде правильний.

Коли unordered_map справді зручний

unordered_map обирають, коли:

• потрібен швидкий доступ за ключем і порядок не важливий;
• ви робите лічильники, індекси або таблиці відповідностей;
• вам важлива швидкість на великих обсягах даних.

5. Порівняння map і unordered_map: таблиця

Щоб не намагатися тримати все це в оперативній памʼяті одночасно, зведімо відмінності в таблицю:

std::map

std::unordered_map

6. Практика: операції та поведінка

Тепер приємна частина: користуватися map і unordered_map дуже схоже. Так зроблено навмисно, щоб вам не доводилося страждати й переписувати пів проєкту, коли захочеться замінити один контейнер на інший. Але є нюанс: однаковий синтаксис інколи породжує різні очікування, особливо навколо operator[].

Нижче — операції, які ви використовуватимете найчастіше: find, contains, insert/emplace, erase, operator[].

Обхід: map виводить у порядку ключів

Зробімо невеликий приклад «імʼя → вік». Зверніть увагу на обхід: імена будуть відсортовані (зазвичай лексикографічно, тобто як у словнику).

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> ages;
    ages.emplace("Bob", 25);
    ages.emplace("Ann", 20);

    for (const auto& [name, age] : ages) {
        std::cout << name << " -> " << age << '\n';
        // Ann -> 20
        // Bob -> 25
    }
}

Обхід: unordered_map — швидко, але без гарантії порядку

Той самий приклад, але з unordered_map. Важливий момент: вивід може бути в будь-якому порядку. Не намагайтеся «впіймати закономірність» — це як намагатися передбачити, де опиниться шкарпетка після прання. Іноді здається, що порядок є. А потім раптом виявляється, що його немає.

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> ages;
    ages.emplace("Bob", 25);
    ages.emplace("Ann", 20);

    for (const auto& [name, age] : ages) {
        std::cout << name << " -> " << age << '\n';
        // Порядок НЕ гарантовано
    }
}

find: безпечне читання без побічних ефектів

Коли ви хочете прочитати значення за ключем і водночас не змінювати контейнер, найнадійніший шлях — find.

Зазвичай це роблять так:

1. auto it = m.find(key);
2. якщо it == m.end() — ключа немає
3. інакше it->second — це значення

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> score{{"Ann", 10}, {"Bob", 12}};

    if (auto it = score.find("Eve"); it != score.end()) {
        std::cout << it->second << '\n';
    } else {
        std::cout << "немає такого ключа\n"; // немає такого ключа
    }
}

Чому це важливо: find не створює нових елементів. Він лише шукає.

contains: коли потрібно просто «є/немає»

У C++20 асоціативні контейнери мають contains(key) — це коротка форма перевірки. Повертає true/false. Для початківців це часто читається простіше, ніж find, особливо коли саме значення вам не потрібне.

#include <iostream>
#include <map>

int main() {
    std::map<int, int> m{{1, 100}, {2, 200}};

    std::cout << m.contains(2) << '\n'; // 1
    std::cout << m.contains(3) << '\n'; // 0
}

Якщо вам потрібне значення — беріть find. Якщо потрібно лише відповісти на запитання «чи існує ключ», contains зазвичай ідеальний.

operator[]: дуже зручно… і тому небезпечно

Ось головний «мем» (у доброму сенсі) про map і unordered_map.

m[key] — це операція «отримати або створити»:

• якщо ключ вже є — ви отримуєте посилання на значення;
• якщо ключа немає — він створюється, а значення стає «за замовчуванням».

Через це operator[] чудово підходить для лічильників, але погано — для сценарію «просто перевірити наявність».

Приклад: лічильник слів — operator[] чудовий

#include <iostream>
#include <string>
#include <unordered_map>

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

    cnt["apple"] += 1; // було 0 (створилося), стало 1
    cnt["apple"] += 1; // стало 2

    std::cout << cnt["apple"] << '\n'; // 2
}

Приклад: «просто прочитаю, що там» — і раптово змінив контейнер

#include <iostream>
#include <unordered_map>

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

    std::cout << m[2] << '\n';     // 0  (і ключ 2 тепер існує!)
    std::cout << m.size() << '\n'; // 2
}

Саме така зміна розміру — типова причина запитання «чому в мене в контейнері раптом зʼявилися зайві ключі?».

insert/emplace: вставка без перезапису та результат операції

Коли ви вставляєте елемент у map/unordered_map, часто хочеться знати: «вставилося чи ключ уже був?». І контейнер чесно повертає результат: std::pair<iterator, bool>.

bool показує, чи справді відбулася вставка.

#include <iostream>
#include <unordered_map>

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

    auto [it1, ok1] = m.emplace(1, 10);
    auto [it2, ok2] = m.emplace(1, 99);

    std::cout << ok1 << ' ' << ok2 << '\n'; // 1 0
    std::cout << m[1] << '\n';              // 10
}

Зверніть увагу: другий emplace не перезаписав значення, тому що ключ уже існував.

erase: видалення за ключем і «скільки реально видалили»

erase(key) повертає кількість видалених елементів. Для map/unordered_map це зазвичай 0 або 1, тому що ключі унікальні.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m{{1, 10}, {2, 20}};

    std::size_t removed = m.erase(2);
    std::cout << removed << '\n'; // 1
}

Це зручно: можна не робити окрему перевірку через contains, якщо вам важливо лише зрозуміти, чи було що видаляти.

7. Як «дерево» відрізняється від «хеш-таблиці»: схема на пальцях

Іноді допомагає візуалізація, особливо якщо ви поки що не любите абстракції. І це нормально: самі собою вони не надто «тактильні».

flowchart LR
    A[Ключ] --> B{map: порівняння}
    B --> C[вліво/вправо по дереву]
    C --> D[знайшли значення]

    A --> E{unordered_map: хеш}
    E --> F[номер кошика]
    F --> G[пошук у кошику]
    G --> D

У map головний інструмент — порівняння ключів і логарифмічна навігація структурою. У unordered_map головний інструмент — хешування й потрапляння «приблизно в потрібне місце».

8. TaskBook: швидкий доступ до задачі за id

Тепер привʼяжімо це до нашого навчального застосунку. Припустімо, що маємо модель:

#include <string>

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

Раніше ми могли зберігати задачі у std::vector<Task> tasks; і шукати їх за id лінійно.

Лінійний пошук: працює, але може бути повільним

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> ids{10, 20, 30};

    int want = 20;
    auto it = std::find(ids.begin(), ids.end(), want);

    std::cout << (it != ids.end()) << '\n'; // 1
}

Для задач усе буде приблизно так само, тільки з find_if і лямбдою — ви це вже зустрічали.

Індекс id → Task на unordered_map

Якщо наша типова операція — «за id швидко знайти задачу», логічніше зберігати індекс:

#include <iostream>
#include <string>
#include <unordered_map>

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

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

    by_id.emplace(1, Task{1, "Почитати книгу з C++"});
    by_id.emplace(2, Task{2, "Виправити баги (або створити нові)"});

    std::cout << by_id[2].text << '\n'; // Виправити баги (або створити нові)
}

Тут я навмисно використав operator[] для читання, щоб ви відчули «слизьке місце»: це безпечно лише тоді, коли ви впевнені, що ключ існує. Інакше ви випадково створите порожню задачу. Тому в реальному коді значення частіше читають через find.

Безпечне читання задачі за id: через find

#include <iostream>
#include <string>
#include <unordered_map>

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

int main() {
    std::unordered_map<int, Task> by_id{{1, {1, "Читати"}}, {2, {2, "Писати"}}};

    int id = 3;
    if (auto it = by_id.find(id); it != by_id.end()) {
        std::cout << it->second.text << '\n';
    } else {
        std::cout << "Немає задачі з id=" << id << '\n'; // Немає задачі з id=3
    }
}

9. Що обрати: map чи unordered_map?

Зробімо чесне прикладне правило — без містики.

Якщо вам потрібен упорядкований вивід і ви хочете, щоб контейнер сам тримав усе «за ключами», беріть map. Наприклад, якщо ви завжди друкуєте задачі за id, користувачеві так буде просто зручніше.

Якщо вам потрібен швидкий доступ і ви не хочете платити log N за кожне звернення, а порядок не важливий, беріть unordered_map.

Якщо ви вагаєтеся, то на практиці часто починають з unordered_map, тому що це «словник за замовчуванням» для швидкого доступу. А коли раптом зʼявляється вимога «виводити за ключем у відсортованому порядку», переходять на map (або сортують окремо, але це вже інша історія).

І ще невелика формальність: у unordered_map є вимоги до ключа (хеш і рівність), а у map — до порядку (порівняння). Ми детально розберемо ці «контракти ключів» у наступних лекціях цього дня; у матеріалах стандарту для unordered-контейнерів для них навіть виділяють окремі вимоги.

10. Типові помилки під час вибору та використання map/unordered_map

Помилка № 1: очікувати від unordered_map «порядку під час обходу».
Новачок створює unordered_map, наповнює його даними, друкує, бачить «майже відсортовано» й починає покладатися на цей порядок. Потім додається ще один елемент, змінюється компілятор, режим збирання або просто фаза місяця — і порядок уже інший. На порядок обходу unordered_map покладатися не можна: якщо він важливий, обирайте map.

Помилка № 2: використовувати operator[] для перевірки наявності ключа.
Класика: пишуть if (m[key] == ...) або просто m[key], щоб «подивитися, чи є». У підсумку ключ створюється зі значенням за замовчуванням, контейнер змінюється, зʼявляються «порожні» записи. Для перевірки використовуйте contains або find, а operator[] залишайте для сценаріїв «створити/оновити».

Помилка № 3: розіменувати результат find без перевірки на end().
Після auto it = m.find(key); не можна одразу звертатися до it->second, тому що it може виявитися рівним m.end(). У найкращому разі ви отримаєте падіння, у найгіршому — дивну поведінку. Корисно виробити простий ритуал: спочатку перевірка, потім розіменування.

Помилка № 4: обирати контейнер «за смаком», а не за вимогами задачі.
Іноді map беруть «бо звучить солідно», а unordered_map — «бо швидше». Правильніше починати із запитань: чи важливий порядок, чи потрібні часті пошуки, чи буде багато елементів. Якщо порядок важливий, map розвʼяже задачу простіше. Якщо порядок не важливий, але важлива швидкість, unordered_map зазвичай буде природнішим вибором.

Помилка № 5: зберігати дані так, що ключі «дублюють» сенс структури.
Наприклад, ви робите unordered_map<int, Task>, де всередині Task ще є поле id, а потім починаєте оновлювати одне, забуваючи про інше. Це не завжди помилка (іноді id в обʼєкті справді зручний), але це місце, де легко отримати розсинхрон. Добра звичка така: якщо id — ключ, стежте, щоб Task.id або завжди збігався з ним, або взагалі не використовувався як джерело істини. Інакше ви самі собі влаштуєте квест.