Brugerdefinerede hashfunktioner
Hash egne typer
Brugerdefinerede hashfunktioner er en gratis C++ Academy-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i C++ Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. C++ Academy-kurset indeholder 4 lektioner i alt.
Hvorfor brugerdefinerede hashfunktioner
Usorterede containere har brug for en måde at hashe deres nøgler på. Indbyggede typer og std::string har allerede hashfunktioner, men dine egne typer har ikke. Du skal levere en.
#include <iostream>
#include <unordered_set>
#include <string>
int main() {
std::unordered_set<std::string> s{"hi"};
std::cout << s.count("hi") << '\n';
return 0;
}Skabelonen std::hash
std::hash er en funktor, der omsætter en værdi til en size_t. Du kalder den som en funktion.
#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;
}En struct, der skal hashes
Antag, at vi har en Point med to int-værdier. Hvis vi vil gemme den i en unordered_set, skal vi bruge både lighed og en hashfunktion.
#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;
}Skrivning af en hash-funktor
En hash-funktor er en struct med operator(), der returnerer size_t. Kombinér hashværdierne for felterne, ofte med XOR og et bit-skift.
#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;
}Brug af hash-funktoren
Send hash-funktoren som det andet skabelonargument til den usorterede container.
#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;
}Lighed er også påkrævet
To nøgler havner i samme bucket, hvis deres hashværdier kolliderer. Containeren bruger derefter operator== til at skelne mellem dem, så lighed er obligatorisk.
#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 som map-nøgle
Den samme brugerdefinerede hashfunktion gør det muligt for en struct at være nøgle i en 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;
}Kombination af flere felter
En almindelig hjælpefunktion kombinerer hashværdier ét felt ad gangen ved hjælp af et mønster med multiplikation og addition, der minder om 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;
}God hashfordeling
En dårlig hashfunktion, der returnerer en konstant, placerer alt i én bucket, så ydeevnen falder til O(n). Bland bittene fra alle felter grundigt.
#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;
}Specialisering af std::hash
Alternativt kan du specialisere std::hash for din type, så den fungerer uden at sende en funktor eksplicit.
#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 som hashfunktion
I C++20 kan du endda bruge en tilstandsløs lambda som hashfunktion ved at sende dens type.
#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;
}Hurtig test
Test din forståelse af brugerdefineret hashing.
Opsummering
Du har lært at hashe brugerdefinerede typer:
- lever en hash-funktor (eller specialiser
std::hash), der returnerersize_t - lever også operator==, så kolliderende nøgler kan skelnes
- kombinér hashværdierne for felterne effektivt for at opnå en god fordeling
Dernæst undersøger du buckets og belastningsfaktorens betydning for ydeevnen.
Lær C++ med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 51
- Lektioner
- 203
Ofte stillede spørgsmål
Er lektionen “Brugerdefinerede hashfunktioner” gratis?
Ja — alle 3 lektioner i læringssporet C++ Academy, inklusive “Brugerdefinerede hashfunktioner”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. C++ Academy-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Brugerdefinerede hashfunktioner”?
Hash egne typer Du øver dig i C++ Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på C++ Academy?
Der kræves ingen tidligere erfaring. C++ Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.
Hvor lang tid tager lektionen “Brugerdefinerede hashfunktioner”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne C++ Academy-lektion?
Ja. Alle C++ Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- std::unordered_map
- unordered_set
- Brugerdefinerede hashfunktioner
- Ydelsesovervejelser