MiddleКодЧастоЕщё не отвечали
Как написать кастомный хеш для пользовательского ключа в unordered_map?
У вас есть пользовательский тип ключа Point { int x; int y; }, и вы хотите использовать его как ключ в std::unordered_map.
Ограничения:
- Хешируйте все поля (а не одно) и корректно их комбинируйте — тривиальный XOR даёт много коллизий.
- Хеш должен быть согласован с равенством: равные ключи должны иметь равный хеш.
- Сделайте тип пригодным для
unordered_mapбез явной передачи хеша.
struct Point { int x; int y; };
bool operator==(const Point& a, const Point& b);
namespace std {
template <>
struct hash<Point> {
std::size_t operator()(const Point& p) const noexcept {
// ваш код здесь
}
};
}Допишите реализацию.
Специализируйте std::hash<MyKey> в namespace std или передайте хеш-callable вторым шаблонным параметром. Комбинируйте поля через hash_combine (не тривиальный XOR) и предоставьте согласованный operator==.
- ✗Хешировать только одно поле структуры — высокий процент коллизий
- ✗Забывать согласованность
operator==и хеша (равные ключи — равный хеш) - ✗Специализировать
std::hashв другом namespace — её просто не найдут
- →На чём обычно основан
std::hash<std::string>(siphash, fnv и т.д.)? - →Как сделать transparent-хеш для heterogeneous lookup с
string_view?
