Fonctions de hachage personnalisées
Hacher vos propres types
Fonctions de hachage personnalisées est une leçon C++ Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage C++ Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours C++ Academy comprend 4 leçons au total.
Pourquoi utiliser des hachages personnalisés ?
Les conteneurs non ordonnés ont besoin d’un moyen de hacher leurs clés. Les types intégrés et std::string possèdent déjà des fonctions de hachage, mais ce n’est pas le cas de vos propres types. Vous devez en fournir une.
#include <iostream>
#include <unordered_set>
#include <string>
int main() {
std::unordered_set<std::string> s{"hi"};
std::cout << s.count("hi") << '\n';
return 0;
}Le modèle std::hash
std::hash est un foncteur qui associe une valeur à un size_t. Vous l’appelez comme une fonction.
#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;
}Une structure à hacher
Supposons que nous ayons un Point composé de deux entiers. Pour le stocker dans un unordered_set, nous avons besoin à la fois de l’égalité et d’un hachage.
#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;
}Écrire un foncteur de hachage
Un foncteur de hachage est une structure dont le operator() renvoie un size_t. Combinez les hachages des champs, souvent avec XOR et un décalage.
#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;
}Utiliser le foncteur de hachage
Transmettez le foncteur de hachage comme deuxième argument de modèle du conteneur non ordonné.
#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;
}L’égalité est également nécessaire
Deux clés se retrouvent dans le même bucket lorsque leurs hachages entrent en collision. Le conteneur utilise ensuite operator== pour les différencier ; l’égalité est donc obligatoire.
#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;
}Hacher comme clé d’une map
Le même hachage personnalisé permet à une structure de servir de clé dans un 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;
}Combiner plusieurs champs
Un utilitaire courant combine les hachages champ par champ, en utilisant un schéma de multiplication et d’addition similaire à 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;
}Bonne répartition du hachage
Un mauvais hachage qui renvoie une constante place tout dans un seul bucket, ce qui dégrade les performances jusqu’à O(n). Mélangez correctement les bits de tous les champs.
#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;
}Spécialiser std::hash
Vous pouvez également spécialiser std::hash pour votre type afin qu’il fonctionne sans transmettre explicitement un foncteur.
#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;
}Une lambda comme hachage
En C++20, vous pouvez même utiliser une lambda sans état comme hachage en transmettant son 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;
}Vérification rapide
Vérifiez votre compréhension du hachage personnalisé.
Récapitulatif
Vous avez appris à hacher des types personnalisés :
- fournir un foncteur de hachage (ou spécialiser
std::hash) qui renvoie unsize_t - fournir également operator== afin de différencier les clés entrant en collision
- bien combiner les hachages des champs pour obtenir une bonne répartition
Ensuite, vous étudierez les buckets et les performances liées au facteur de charge.
Questions Fréquemment Posées
La leçon « Fonctions de hachage personnalisées » est-elle gratuite ?
Oui — le texte complet de « Fonctions de hachage personnalisées » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours C++ Academy, passe à CoddyKit PRO. Le cours C++ Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Fonctions de hachage personnalisées » ?
Hacher vos propres types Tu pratiques C++ Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer C++ Academy ?
Aucune expérience préalable n'est requise. C++ Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Fonctions de hachage personnalisées » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon C++ Academy ?
Oui. Chaque leçon C++ Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- std::unordered_map
- unordered_set
- Fonctions de hachage personnalisées
- Considérations de performance