0Pricing
C++ Academy · Lekcja

Niestandardowe funkcje haszujące

Haszuj własne typy

Niestandardowe funkcje haszujące to bezpłatna lekcja C++ Academy na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C++ Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C++ Academy zawiera 4 lekcji w sumie.

Po co własne funkcje haszujące?

Kontenery nieuporządkowane potrzebują sposobu haszowania kluczy. Typy wbudowane i std::string mają już własne funkcje haszujące, ale własne typy ich nie mają. Należy dostarczyć taką funkcję.

#include <iostream>
#include <unordered_set>
#include <string>

int main() {
    std::unordered_set<std::string> s{"hi"};
    std::cout << s.count("hi") << '\n';
    return 0;
}

Szablon std::hash

std::hash to funktor, który odwzorowuje wartość na typ size_t. Wywołuje się go tak jak funkcję.

#include <iostream>
#include <functional>
#include <string>

int main() {
    std::hash<std::string> h;
    std::cout << "hash exists and returns a size_t\n";
    std::size_t v = h("hello");
    std::cout << (v != 0 ? "non-zero hash" : "zero") << '\n';
    return 0;
}

Struktura do haszowania

Załóżmy, że mamy obiekt Point zawierający dwie wartości typu int. Aby przechowywać go w unordered_set, potrzebujemy zarówno równości, jak i funkcji haszującej.

#include <iostream>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

int main() {
    Point a{1, 2}, b{1, 2};
    std::cout << std::boolalpha << (a == b) << '\n';
    return 0;
}

Pisanie funktora haszującego

Funktor haszujący to struktura z operator(), który zwraca size_t. Należy połączyć hasze pól, często za pomocą XOR i przesunięcia.

#include <iostream>
#include <functional>

struct Point { int x, y; };

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    PointHash h;
    std::cout << "hashed: " << (h({3, 4}) != 0 ? "ok" : "zero") << '\n';
    return 0;
}

Używanie funktora haszującego

Funktor haszujący należy przekazać jako drugi argument szablonu kontenera nieuporządkowanego.

#include <iostream>
#include <unordered_set>
#include <functional>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    std::unordered_set<Point, PointHash> pts;
    pts.insert({1, 2});
    pts.insert({1, 2});
    std::cout << pts.size() << '\n';
    return 0;
}

Równość również jest wymagana

Dwa klucze trafiają do tego samego kubełka, gdy ich hasze kolidują. Kontener używa wtedy operator==, aby je rozróżnić, dlatego równość jest niezbędna.

#include <iostream>
#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x * 31 + p.y);
    }
};

int main() {
    std::unordered_set<Point, PointHash> s{{1, 1}, {2, 2}};
    std::cout << s.count({1, 1}) << '\n';
    return 0;
}

Haszowanie jako klucz mapy

Ta sama własna funkcja haszująca pozwala użyć struktury jako klucza w unordered_map.

#include <iostream>
#include <unordered_map>
#include <functional>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    std::unordered_map<Point, std::string, PointHash> m;
    m[{0, 0}] = "origin";
    std::cout << m[{0, 0}] << '\n';
    return 0;
}

Łączenie wielu pól

Typowy pomocniczy mechanizm łączy hasze, przetwarzając po jednym polu i używając wzorca mnożenia i dodawania podobnego do boost::hash_combine.

#include <iostream>
#include <functional>

std::size_t combine(std::size_t seed, std::size_t v) {
    return seed ^ (v + 0x9e3779b9 + (seed << 6) + (seed >> 2));
}

int main() {
    std::size_t h = 0;
    h = combine(h, std::hash<int>()(10));
    h = combine(h, std::hash<int>()(20));
    std::cout << (h != 0 ? "combined ok" : "zero") << '\n';
    return 0;
}

Dobre rozłożenie haszy

Nieprawidłowa funkcja haszująca, która zwraca stałą wartość, umieszcza wszystko w jednym kubełku, obniżając wydajność do O(n). Należy dobrze mieszać bity wszystkich pól.

#include <iostream>
#include <functional>

struct Bad { std::size_t operator()(int) const { return 0; } };
struct Good { std::size_t operator()(int x) const { return std::hash<int>()(x); } };

int main() {
    std::cout << Bad()(5) << ' ' << (Good()(5) != 0 ? "varies" : "0") << '\n';
    return 0;
}

Specjalizacja std::hash

Alternatywnie można specjalizować std::hash dla własnego typu, aby działał bez jawnego przekazywania funktora.

#include <iostream>
#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

namespace std {
    template <> struct hash<Point> {
        std::size_t operator()(const Point& p) const {
            return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
        }
    };
}

int main() {
    std::unordered_set<Point> s{{1, 2}};
    std::cout << s.count({1, 2}) << '\n';
    return 0;
}

Lambda jako funkcja haszująca

W C++20 można nawet użyć bezstanowej lambdy jako funkcji haszującej, przekazując jej typ.

#include <iostream>
#include <unordered_set>

int main() {
    auto h = [](int x) { return std::hash<int>()(x * 2654435761u); };
    std::unordered_set<int, decltype(h)> s(8, h);
    s.insert(42);
    std::cout << s.count(42) << '\n';
    return 0;
}

Szybkie sprawdzenie

Proszę sprawdzić swoje zrozumienie własnego haszowania.

Podsumowanie

Dowiedzieli się Państwo, jak haszować własne typy:

  • należy dostarczyć funktor haszujący (lub specjalizację std::hash) zwracający size_t
  • należy również dostarczyć operator==, aby rozróżniać kolidujące klucze
  • należy dobrze łączyć hasze pól, aby uzyskać dobre rozłożenie

Następnie poznają Państwo wydajność kubełków i współczynnika wypełnienia.

Często zadawane pytania

Czy lekcja „Niestandardowe funkcje haszujące” jest bezpłatna?

Tak — pełny tekst „Niestandardowe funkcje haszujące” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C++ Academy, przejdź na CoddyKit PRO. Kurs C++ Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Niestandardowe funkcje haszujące”?

Haszuj własne typy Ćwiczysz C++ Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć C++ Academy?

Nie wymagamy żadnego doświadczenia. C++ Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.

Ile czasu zajmuje lekcja „Niestandardowe funkcje haszujące”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji C++ Academy?

Tak. Każda lekcja C++ Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. std::unordered_map
  2. unordered_set
  3. Niestandardowe funkcje haszujące
  4. Kwestie wydajności
← Powrót do C++ Academy