Пользовательский ключ: struct Key, operator== и std::hash<Key>

1. Зачем нужен пользовательский ключ

Когда вы впервые видите unordered_map, кажется, что это история про «ключ = int или string». Но жизнь быстро подкидывает сюжеты вроде: «найди задачу по (пользователь, тег)» или «кешируй результат по (город, дата)». И вот тут один int уже не спасает — нужен составной ключ из нескольких полей.

Представьте наше учебное мини‑приложение (условно назовём его TaskBook): мы храним задачи, у каждой есть id, ownerId (кто владелец) и tag (тег типа "cpp" или "home"). Нам хочется сделать быстрый индекс:

• (ownerId, tag) → набор id задач

Технически это означает: ключ должен содержать два значения. А значит, мы создаём свой тип ключа — struct Key.

Наглядная схема, что вообще происходит при поиске в unordered_map:

flowchart LR
    A["Ключ (ownerId, tag)"] --> B["hash(key) -> число"]
    B --> C["выбор корзины (bucket)"]
    C --> D["проверка кандидатов через operator=="]
    D --> E["нашли значение или нет"]

2. Проектируем struct Key

Составной ключ — это не «структура на все случаи жизни», а именно паспорт уникальности. То есть он должен содержать ровно те поля, по которым мы различаем записи. Если вы добавите лишнее поле, вы усложните жизнь и можете «раздробить» индекс на слишком много вариантов. Если не добавите важное поле — индекс начнёт путать разные сущности.

В нашем TaskBook ключом индекса будет пара: ownerId и tag.

#include <string>

struct OwnerTagKey {
    int ownerId{};
    std::string tag;
};

Обратите внимание на простую мысль: ключ — это обычно «маленький» объект, который удобно копировать и сравнивать. Здесь int и string — нормально. Если бы ключ был гигантским (например, включал бы длинный текст задачи), это было бы странно: ключом обычно делают то, что действительно идентифицирует запись, а не всё подряд.

Ещё один важный нюанс из практики: ключ должен вести себя «стабильно». Если вы вставили элемент в unordered_map под ключом (1, "cpp"), а потом каким‑то образом «поменяли ключ», контейнер бы просто сошёл с ума. Поэтому в ассоциативных контейнерах ключи фактически считаются неизменяемыми (и в unordered_map ключ внутри пары вообще хранится как const).

3. Пишем operator==

Теперь контейнеру нужно уметь отвечать на вопрос: «Эти два ключа — один и тот же ключ?». Для unordered_* это делается через сравнение на равенство (обычно operator==).

Важно не философствовать. Для ключа «(ownerId, tag)» равенство звучит буквально: равны ownerId и равны tag.

#include <string>

struct OwnerTagKey {
    int ownerId{};
    std::string tag;
};

bool operator==(const OwnerTagKey& a, const OwnerTagKey& b) {
    return a.ownerId == b.ownerId && a.tag == b.tag;
}

Если вы вдруг решите «а сравнивать будем только ownerId, теги не важны» — это будет означать, что (1, "cpp") и (1, "home") с точки зрения контейнера одинаковые ключи. И тогда ваш индекс «(ownerId, tag) → ...» превращается в «(ownerId) → ...». Иногда так и надо, но тогда и ключ должен быть другим.

Мини‑проверка на «не сошли ли мы с ума»:

#include <iostream>
#include <string>

struct OwnerTagKey {
    int ownerId{};
    std::string tag;
};

bool operator==(const OwnerTagKey& a, const OwnerTagKey& b) {
    return a.ownerId == b.ownerId && a.tag == b.tag;
}

int main() {
    OwnerTagKey k1{1, "cpp"};
    OwnerTagKey k2{1, "cpp"};
    OwnerTagKey k3{1, "home"};

    std::cout << (k1 == k2) << '\n'; // 1
    std::cout << (k1 == k3) << '\n'; // 0
}

4. Контракт std::hash<T> и согласованность с operator==

Хеш‑функция — это способ превратить ключ в число типа std::size_t. Контейнер использует это число, чтобы быстро найти «примерное место», где лежит элемент. Важно понимать, что хеш — это не «уникальный отпечаток». Коллизии возможны и допустимы: два разных ключа могут иметь один и тот же хеш, и это не конец света — контейнер потом уточнит через ==.

Но есть железное правило (контракт), без которого unordered_map работать корректно не сможет:

Если a == b, то обязательно hash(a) == hash(b).

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

Кстати, сама тема коллизий — не только про производительность, но и про безопасность. В истории стандарта обсуждались риски атак на std::hash, когда злоумышленник подбирает много ключей с одинаковыми хешами, чтобы контейнер деградировал по времени работы.

Как выглядит поломка контракта на практике

Есть два типа проблем с хешем, и их полезно различать по ощущениям.

Первый тип — «хеш плохой». Тогда программа корректна, но может внезапно стать медленной на больших данных. Например, вы сделали return 0;, и все ключи упали в одну корзину. Всё работает, но грустно.

Второй тип — «контракт сломан». Это когда operator== и hash используют разные наборы полей. Тогда может ломаться корректность: вы вставили элемент, а потом не можете его найти. Это уже не «медленно», это «неправильно».

Например, вот так делать нельзя: == смотрит только на ownerId, а хеш — на ownerId и tag. Тогда возможна ситуация, когда два ключа считаются равными, но их хеши разные. Это прямое нарушение правила a == b ⇒ hash(a) == hash(b).

#include <string>

struct OwnerTagKey {
    int ownerId{};
    std::string tag;
};

bool operator==(const OwnerTagKey& a, const OwnerTagKey& b) {
    return a.ownerId == b.ownerId; // tag игнорируется — плохо для нашего ключа
}

А если ваш hash при этом использует tag, вы получаете ключи, которые «равны», но живут в разных корзинах. Контейнер начинает вести себя непредсказуемо (точнее, предсказуемо плохо).

Практическая диагностика тут простая: если unordered_map «теряет» элементы, первым делом проверьте согласованность == и hash. Это почти всегда причина.

5. Хеш для составного ключа: как смешивать поля

Для базовых типов стандарт уже даёт std::hash<int>, std::hash<std::string> и так далее. Значит, для нашего ключа логика такая:

1. посчитать h1 = hash(ownerId)
2. посчитать h2 = hash(tag)
3. как‑то аккуратно смешать h1 и h2 в один size_t

Для учебных целей достаточно простого смешивания. Например:

• умножить h1 на константу,
• прибавить h2.

#include <cstddef>

std::size_t CombineHash(std::size_t h1, std::size_t h2) {
    return h1 * 31u + h2;
}

Почему это «не магия», а просто практика? Потому что мы хотим, чтобы разные пары значений давали «обычно разные» результаты. Константа 31 — популярный выбор в учебных примерах, потому что проста и исторически часто встречается. Это не «идеальная формула вселенной», но как минимум лучше, чем return h1 + h2;, где слишком много разных пар могут схлопнуться одинаково.

Плохой хешер (пример «как делать не надо, но почему-то делают»):

#include <cstddef>

std::size_t VeryBadHash() {
    return 0; // все ключи в одной корзине
}

С таким хешем корректность не сломается (если == нормальный), но смысл unordered_* почти исчезнет: контейнер начнёт вести себя как плохо написанный список.

6. Как подключить хеш к unordered_map

Свой хешер-объект и явное указание в unordered_map

Часто самый простой и понятный путь — не трогать std::hash<Key> напрямую, а передать контейнеру «как хешировать» третьим шаблонным параметром. Нам нужен функциональный объект — объект, который можно вызвать как функцию через operator().

#include <cstddef>
#include <functional>
#include <string>

struct OwnerTagKey {
    int ownerId{};
    std::string tag;
};

bool operator==(const OwnerTagKey& a, const OwnerTagKey& b) {
    return a.ownerId == b.ownerId && a.tag == b.tag;
}

std::size_t CombineHash(std::size_t h1, std::size_t h2) {
    return h1 * 31u + h2;
}

struct OwnerTagKeyHash {
    std::size_t operator()(const OwnerTagKey& k) const {
        std::size_t h1 = std::hash<int>{}(k.ownerId);
        std::size_t h2 = std::hash<std::string>{}(k.tag);
        return CombineHash(h1, h2);
    }
};

Теперь контейнер можно объявить так:

#include <unordered_map>
#include <unordered_set>
#include <string>

std::unordered_map<OwnerTagKey, std::unordered_set<int>, OwnerTagKeyHash> index;

Этот способ хорош тем, что всё видно прямо в месте объявления: какой ключ, какое значение, какой хешер. И вам не нужно залезать в namespace std.

Специализация std::hash<Key>

Иногда хочется, чтобы ключ выглядел «как родной» для unordered_map, без явного третьего параметра. Для этого можно специализировать std::hash для своего типа. Для пользовательских типов это разрешённая практика: стандартная библиотека прямо ожидает, что вы иногда так сделаете.

Синтаксис выглядит «страшнее», чем смысл. Смысл всё тот же: вернуть size_t и использовать те же поля, что и в operator==.

#include <cstddef>
#include <functional>
#include <string>

struct OwnerTagKey {
    int ownerId{};
    std::string tag;
};

bool operator==(const OwnerTagKey& a, const OwnerTagKey& b) {
    return a.ownerId == b.ownerId && a.tag == b.tag;
}

std::size_t CombineHash(std::size_t h1, std::size_t h2) {
    return h1 * 31u + h2;
}

namespace std {
    template <>
    struct hash<OwnerTagKey> {
        std::size_t operator()(const OwnerTagKey& k) const noexcept {
            std::size_t h1 = std::hash<int>{}(k.ownerId);
            std::size_t h2 = std::hash<std::string>{}(k.tag);
            return CombineHash(h1, h2);
        }
    };
}

Обратите внимание на noexcept. В учебном коде это не всегда критично, но в библиотечных обсуждениях явно поднимался вопрос о том, что хеш‑функции желательно делать noexcept, чтобы контейнерам было проще давать гарантии и оптимизировать поведение.

После такой специализации контейнер можно писать проще:

#include <unordered_map>
#include <unordered_set>

std::unordered_map<OwnerTagKey, std::unordered_set<int>> index;

И да, выглядит приятно: ключ стал «понятен» стандартной библиотеке.

7. Пример: индекс TaskBook по владельцу и тегу

Теперь давайте соберём небольшой, но связный кусок нашего учебного приложения. Мы сделаем две структуры хранения:

1. первичное хранилище: id → Task
2. вторичный индекс: (ownerId, tag) → набор id

Пусть у задачи пока будет ровно один тег. Так проще, а «много тегов» — это просто цикл, идея та же.

#include <string>

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

А теперь — «скелет» хранилища:

#include <unordered_map>
#include <unordered_set>

std::unordered_map<int, Task> tasksById;
std::unordered_map<OwnerTagKey, std::unordered_set<int>> tasksByOwnerTag;

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

#include <utility>

void AddTask(const Task& t) {
    tasksById.emplace(t.id, t);

    OwnerTagKey key{t.ownerId, t.tag};
    tasksByOwnerTag[key].insert(t.id); // operator[] здесь осознанный: создаём набор при отсутствии
}

Обратите внимание на operator[]: это ровно тот случай, когда он уместен. Если для пары (ownerId, tag) ещё нет набора задач, мы хотим его создать, потому что добавляем туда первую задачу.

Поиск задач по владельцу и тегу — это классический паттерн find → проверить → использовать:

#include <iostream>

void PrintCountByOwnerTag(int ownerId, const std::string& tag) {
    OwnerTagKey key{ownerId, tag};

    if (auto it = tasksByOwnerTag.find(key); it != tasksByOwnerTag.end()) {
        std::cout << it->second.size() << '\n'; // например: 3
    } else {
        std::cout << 0 << '\n'; // 0
    }
}

Если позже мы дойдём до полноценного CRUD (добавить/удалить/переименовать/сменить тег), то именно такие индексы дадут нам скорость и простоту логики: мы не будем каждый раз пробегать весь tasksById в поисках «всех задач пользователя с тегом cpp».

8. Типичные ошибки при пользовательских ключах и std::hash

Ошибка №1: operator== сравнивает не те поля, что реально определяют ключ.
Часто это происходит из благих намерений: «Ну тег — это же просто подпись, давайте его игнорировать». Но если вы строите индекс (ownerId, tag), то игнорировать tag нельзя: контейнер начнёт склеивать разные ключи и «прятать» элементы.

Ошибка №2: hash и operator== используют разные поля.
Это самая опасная ошибка, потому что она ломает не скорость, а корректность. Вставка может пройти, а find внезапно не найдёт элемент. Если ощущения «контейнер меня газлайтит» возникли — вы почти наверняка нарушили правило согласованности.

Ошибка №3: слишком “ленивый” хеш (например, константа или хеш только одного поля).
Такой код часто «нормально работает на маленьких тестах», а потом начинает тормозить на реальных данных. Коллизии допустимы, но когда они становятся массовыми, unordered_map теряет смысл и превращается в дорогой список.

Ошибка №4: использование operator[] там, где вы хотели просто проверить наличие.
Это классическая ловушка: tasksByOwnerTag[key] создаст пустой набор, даже если ключа не было. В результате вы можете незаметно «раздуть» индекс мусорными пустыми записями. Для проверки существования используйте find/contains, а operator[] оставляйте для сценариев «создать или обновить».

Ошибка №5: хранить в ключе view-типы без гарантий времени жизни (например, std::string_view).
string_view не владеет строкой. Если вы положили в ключ string_view, а исходная строка умерла или изменилась, ключ превратится в ссылку на «что-то уже не то». На практике для ключей в хеш‑контейнерах почти всегда безопаснее хранить полноценный std::string.