C++ Academy · Lektion

Benutzerdefinierte Hashfunktionen

Eigene Typen hashen

Benutzerdefinierte Hashfunktionen ist eine kostenlose C++ Academy-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des C++ Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der C++ Academy-Kurs umfasst insgesamt 4 Lektionen.

Warum benutzerdefinierte Hashes?

Ungeordnete Container benötigen eine Möglichkeit, ihre Schlüssel zu hashen. Für integrierte Typen und std::string gibt es bereits Hashes, für Ihre eigenen Typen jedoch nicht. Sie müssen einen bereitstellen.

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

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

Das std::hash-Template

std::hash ist ein Funktor, der einen Wert auf einen size_t abbildet. Sie rufen ihn wie eine Funktion auf.

#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;
}

Ein zu hashendes Struct

Nehmen wir an, wir haben einen Point mit zwei Integers. Um ihn in einem unordered_set zu speichern, benötigen wir sowohl Gleichheit als auch einen Hash.

#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;
}

Einen Hash-Funktor schreiben

Ein Hash-Funktor ist ein Struct mit operator(), das size_t zurückgibt. Kombinieren Sie die Hashes der Felder, häufig mit XOR und einer Verschiebung.

#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;
}

Den Hash-Funktor verwenden

Übergeben Sie den Hash-Funktor als zweites Template-Argument des ungeordneten Containers.

#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;
}

Auch Gleichheit ist erforderlich

Zwei Schlüssel landen im selben Bucket, wenn ihre Hashes kollidieren. Der Container verwendet dann operator==, um sie zu unterscheiden. Daher ist Gleichheit zwingend erforderlich.

#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;
}

Hashing als Map-Schlüssel

Mit demselben benutzerdefinierten Hash kann ein Struct der Schlüssel einer unordered_map sein.

#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;
}

Mehrere Felder kombinieren

Eine gängige Hilfsfunktion kombiniert Hashes Feld für Feld mithilfe eines Musters aus Multiplikation und Addition, ähnlich wie 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;
}

Gute Hash-Verteilung

Ein schlechter Hash, der eine Konstante zurückgibt, legt alles in einen Bucket und verschlechtert die Laufzeit auf O(n). Vermischen Sie die Bits aller Felder gründlich.

#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;
}

std::hash spezialisieren

Alternativ können Sie std::hash für Ihren Typ spezialisieren, sodass er funktioniert, ohne einen Funktor ausdrücklich zu übergeben.

#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 als Hash

In C++20 können Sie sogar ein zustandsloses Lambda als Hash verwenden, indem Sie dessen Typ übergeben.

#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;
}

Kurze Überprüfung

Testen Sie Ihr Verständnis des benutzerdefinierten Hashings.

Zusammenfassung

Sie haben gelernt, eigene Typen zu hashen:

Stellen Sie einen Hash-Funktor bereit (oder spezialisieren Sie std::hash), der size_t zurückgibt.
Stellen Sie außerdem operator== bereit, damit kollidierende Schlüssel unterschieden werden können.
Kombinieren Sie die Hashes der Felder sinnvoll, um eine gute Verteilung zu erzielen.

Als Nächstes untersuchen Sie Buckets und die Performance des Auslastungsfaktors.

Häufig gestellte Fragen

Ist die Lektion „Benutzerdefinierte Hashfunktionen“ kostenlos?

Ja — der vollständige Text von „Benutzerdefinierte Hashfunktionen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des C++ Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der C++ Academy-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Benutzerdefinierte Hashfunktionen“?

Eigene Typen hashen Du übst C++ Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um C++ Academy zu starten?

Keine Vorkenntnisse erforderlich. C++ Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.

Wie lange dauert die Lektion „Benutzerdefinierte Hashfunktionen“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser C++ Academy-Lektion Code schreiben und ausführen?

Ja. Jede C++ Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

← Zurück zu C++ Academy