Klucz użytkownika: struct Key, operator== i std::hash<Key>

1. Po co potrzebny klucz użytkownika

Gdy po raz pierwszy widzisz unordered_map, wydaje się, że to historia o „klucz = int albo string”. Ale życie szybko przynosi scenariusze typu: „znajdź zadanie po (uzytkownik, tag)” albo „cacheuj wynik po (miasto, data)”. I wtedy jeden int już nie wystarcza — potrzebny jest klucz złożony z kilku pól.

Wyobraź sobie nasze małe szkolne mini‑aplikację (umownie nazwiemy ją TaskBook): przechowujemy zadania, każde ma id, ownerId (kto jest właścicielem) i tag (tag typu "cpp" lub "home"). Chcemy zbudować szybki indeks:

• (ownerId, tag) → zbiór id zadań

Technicznie to oznacza: klucz powinien zawierać dwie wartości. Zatem tworzymy własny typ klucza — struct Key.

Schematycznie, co się dzieje przy wyszukiwaniu w unordered_map:

flowchart LR
    A["Klucz (ownerId, tag)"] --> B["hash(key) -> liczba"]
    B --> C["wybor koszyka (bucket)"]
    C --> D["sprawdzenie kandydatow przez operator=="]
    D --> E["znaleziono wartosc czy nie"]

2. Projektujemy struct Key

Klucz złożony — to nie „struktura na każdą okazję”, lecz dokładnie paszport unikalnosci. Czyli powinien zawierać dokładnie te pola, po których rozróżniamy wpisy. Jeśli dodasz zbędne pole, skomplikujesz sprawę i możesz „rozsypać” indeks na zbyt wiele wariantów. Jeśli nie dodasz istotnego pola — indeks zacznie mylić różne byty.

W naszym TaskBook kluczem indeksu będzie para: ownerId i tag.

#include <string>

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

Zwróć uwagę na prostą myśl: klucz to zwykle „mały” obiekt, który wygodnie kopiować i porównywać. Tutaj int i string — w porządku. Gdyby klucz był gigantyczny (np. zawierałby długi tekst zadania), to byłoby dziwne: kluczami robi się zwykle to, co rzeczywiście identyfikuje wpis, a nie wszystko po kolei.

Jeszcze jeden ważny niuans z praktyki: klucz musi zachowywać się „stabilnie”. Jeśli wstawiłeś element do unordered_map pod kluczem (1, "cpp"), a potem w jakiś sposób „zmieniłeś klucz”, kontener po prostu oszalałby. Dlatego w kontenerach asocjacyjnych klucze są praktycznie niezmienne (a w unordered_map klucz w parze jest przechowywany jako const).

3. Pisanie operator==

Teraz kontener musi umieć odpowiedzieć na pytanie: „Czy te dwa klucze to ten sam klucz?”. Dla unordered_* robi się to przez porównanie na równość (zwykle operator==).

Ważne, by nie filozofować. Dla klucza „(ownerId, tag)” równość brzmi dosłownie: równe są ownerId i równe są 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;
}

Jeśli nagle postanowisz „porównywać będziemy tylko ownerId, tagi nieistotne” — to będzie znaczyć, że (1, "cpp") i (1, "home") z punktu widzenia kontenera są takimi samymi kluczami. Wtedy twój indeks „(ownerId, tag) → ...” zamieni się w „(ownerId) → ...”. Czasami tak trzeba, ale wtedy i klucz powinien być inny.

Mini‑sprawdzenie, czy się nie pogubiliśmy:

#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. Kontrakt std::hash<T> i zgodnosc z operator==

Funkcja hashujaca — to sposób na zamianę klucza w liczbę typu std::size_t. Kontener używa tej liczby, aby szybko znaleźć „przybliżone miejsce”, gdzie leży element. Ważne rozumieć, że hash nie jest „unikalnym odciskiem”. Kolizje są możliwe i dopuszczalne: dwa różne klucze mogą mieć ten sam hash, i to nie koniec świata — kontener potem rozstrzygnie przez ==.

Ale jest żelazna zasada (kontrakt), bez której unordered_map nie będzie działać poprawnie:

Jeśli a == b, to koniecznie hash(a) == hash(b).

Jeśli złamiesz to regułę, dostaniesz tajemnicze zachowanie: element „wstawiony”, ale „nie znajduje się”. To ten rzadki przypadek, gdy naprawdę poczujesz się jak bohater horroru: widzisz, że dane są, ale wyszukiwanie ich „nie widzi”.

Swoją drogą, temat kolizji to nie tylko wydajność, ale też bezpieczeństwo. W historii standardu dyskutowano ryzyka ataków na std::hash, gdy napastnik dobiera wiele kluczy o tych samych hashach, żeby spowolnić działanie kontenera.

Jak wygląda złamanie kontraktu w praktyce

Są dwa typy problemów z hashem i warto je rozróżnić po symptomach.

Pierwszy typ — „zły hash”. Wtedy program jest poprawny, ale może niespodziewanie zwolnić przy dużych danych. Na przykład, zwróciłeś return 0;, i wszystkie klucze trafiły do jednego koszyka. Wszysko działa, ale smutno.

Drugi typ — „kontrakt złamany”. To gdy operator== i hash używają różnych zestawów pól. Wtedy może się popsuć poprawność: wstawiłeś element, ale potem nie możesz go znaleźć. To już nie „wolno”, to „niepoprawnie”.

Na przykład, tak robić nie wolno: == patrzy tylko na ownerId, a hash — na ownerId i tag. Wtedy możliwa jest sytuacja, że dwa klucze są uznawane za równe, ale mają różne hashe. To bezpośrednie naruszenie reguły 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 jest ignorowany — zle dla naszego klucza
}

A jeśli twój hash przy tym używa tag, otrzymasz klucze, które „sa rowne”, ale mieszkaja w roznych koszykach. Kontener zaczyna zachowywać się nieprzewidywalnie (dokładniej: przewidywalnie źle).

Praktyczna diagnoza jest prosta: jeśli unordered_map „gubi” elementy, najpierw sprawdź zgodnosc == i hash. To prawie zawsze przyczyna.

5. Hash dla klucza złożonego: jak mieszać pola

Dla typów podstawowych standard już daje std::hash<int>, std::hash<std::string> itd. Zatem dla naszego klucza logika jest taka:

1. obliczyć h1 = hash(ownerId)
2. obliczyć h2 = hash(tag)
3. jakoś ostrożnie wymieszać h1 i h2 w jeden size_t

Dla celów nauki wystarczy proste mieszanie. Na przykład:

• pomnozyc h1 przez stałą,
• dodać h2.

#include <cstddef>

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

Dlaczego to „nie magia”, a praktyka? Bo chcemy, żeby różne pary wartości dawały „zazwyczaj różne” wyniki. Stała 31 to popularny wybór w przykładach, bo jest prosty i historycznie często używany. To nie „idealny wzór wszechświata”, ale przynajmniej lepsze niż return h1 + h2;, gdzie zbyt wiele par może się skleić do tego samego wyniku.

Zly hasher (przyklad „jak nie robic, ale jednak czasem robia”):

#include <cstddef>

std::size_t VeryBadHash() {
    return 0; // wszystkie klucze w jednym koszyku
}

Z takim hashem poprawność się nie złamie (jeśli == jest ok), ale sens unordered_* niemal zniknie: kontener zacznie zachowywać się jak źle napisany list.

6. Jak podłączyć hash do unordered_map

Wlasny obiekt haszujacy i jawne wskazanie w unordered_map

Często najprostsza i najbardziej czytelna droga to nie ruszać std::hash<Key> bezposrednio, a przekazać kontenerowi „jak hashowac” jako trzeci parametr szablonu. Potrzebujemy obiektu funkcyjnego — obiektu, który można wywołać jak funkcję przez 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);
    }
};

Teraz kontener można zadeklarować tak:

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

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

Ten sposób jest dobry, bo wszystko widać od razu przy deklaracji: jaki klucz, jaka wartość, jaki hasher. I nie trzeba wchodzić do namespace std.

Specjalizacja std::hash<Key>

Czasem chcemy, żeby klucz wyglądał „jak rodzimy” dla unordered_map, bez jawnego trzeciego parametru. Można wtedy specjalizować std::hash dla własnego typu. Dla typów użytkownika to dozwolona praktyka: biblioteka standardowa wręcz oczekuje, że czasem tak zrobisz.

Składnia wygląda „straszniej” niż sens. Sens jest ten sam: zwrócić size_t i użyć tych samych pól, co w 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);
        }
    };
}

Zwróć uwagę na noexcept. W kodzie edukacyjnym nie zawsze krytyczne, ale w dyskusjach bibliotekowych podniesiono, że funkcje hashujące warto oznaczać jako noexcept, aby ułatwić kontenerom zapewnianie gwarancji i optymalizację.

Po takiej specjalizacji zapis kontenera jest prostszy:

#include <unordered_map>
#include <unordered_set>

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

I tak, wygląda to ładnie: klucz stał się „rozpoznawalny” dla biblioteki standardowej.

7. Przykład: indeks TaskBook po wlascicielu i tagu

Złóżmy teraz niewielki, ale spójny fragment naszej szkolnej aplikacji. Zrobimy dwie struktury przechowywania:

1. magazyn podstawowy: id → Task
2. indeks wtórny: (ownerId, tag) → zbior id

Niech zadanie ma na razie dokładnie jeden tag. Tak prościej, a „wiele tagow” to po prostu pętla, idea jest ta sama.

#include <string>

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

A teraz — „szkielet” magazynu:

#include <unordered_map>
#include <unordered_set>

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

Dodanie zadania powinno aktualizować obie struktury. W prawdziwym projekcie lepiej ukryć to w funkcji, więc naszkicujemy prostą wersję:

#include <utility>

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

    OwnerTagKey key{t.ownerId, t.tag};
    tasksByOwnerTag[key].insert(t.id); // operator[] tutaj świadomy: tworzymy zbior gdy brak
}

Zwróć uwagę na operator[]: to dokładnie przypadek, gdy jest on stosowny. Jeśli dla pary (ownerId, tag) jeszcze nie ma zbioru zadan, chcemy go utworzyc, bo dodajemy pierwsze zadanie.

Wyszukiwanie zadan po wlascicielu i tagu to klasyczny wzorzec find → sprawdzic → użyć:

#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'; // np.: 3
    } else {
        std::cout << 0 << '\n'; // 0
    }
}

Jeśli później przejdziemy do pełnego CRUD (dodaj/usun/zmien nazwe/zmien tag), to właśnie takie indeksy dadzą nam szybkość i prostotę logiki: nie będziemy za każdym razem skanować całego tasksById w poszukiwaniu „wszystkich zadań użytkownika z tagiem cpp”.

8. Typowe błędy przy kluczach użytkownika i std::hash

Błąd nr 1: operator== porównuje nie te pola, które faktycznie definiują klucz.
Często wynika to z dobrych intencji: „Tag to przecież tylko podpis, zignorujmy go”. Ale jeśli budujesz indeks (ownerId, tag), to nie możesz ignorować tag: kontener zacznie sklejać różne klucze i „ukrywać” elementy.

Błąd nr 2: hash i operator== używają różnych pól.
To najgroźniejszy błąd, bo psuje nie wydajność, lecz poprawność. Wstawienie może się powieść, a find nagle nie znajdzie elementu. Jeśli masz wrażenie, że „kontener cię gaslightuje” — prawie na pewno złamałeś zasadę zgodności.

Błąd nr 3: zbyt „leniwy” hash (np. stała lub hash tylko jednego pola).
Taki kod często „działa” na małych testach, a potem zaczyna zwalniać na realnych danych. Kolizje są dopuszczalne, ale gdy stają się masowe, unordered_map traci sens i zamienia się w kosztowny list.

Błąd nr 4: używanie operator[] tam, gdzie chciałeś tylko sprawdzić obecność.
To klasyczna pułapka: tasksByOwnerTag[key] stworzy pusty zbior, nawet jeśli klucza nie było. W rezultacie możesz niechcący „nadmuchać” indeks pustymi wpisami. Do sprawdzania obecności używaj find/contains, a operator[] zostaw dla scenariuszy „stworz lub zaktualizuj”.

Błąd nr 5: trzymanie w kluczu typow view bez gwarancji czasu życia (np. std::string_view).
string_view nie posiada własności nad stringiem. Jeśli włożysz do klucza string_view, a oryginalny łańcuch umrze lub się zmieni, klucz stanie się referencją do „czegoś nie tego”. W praktyce dla kluczy w kontenerach haszujących zwykle bezpieczniej trzymać pełny std::string.