前言本文探讨C STL 中unordered_map使用自定义类型作为 key 时的实现方式和注意事项。水平不高能力有限错漏之处还请见谅。欢迎友好讨论。环境信息操作系统版本ubuntu24.04CMake版本4.2.0Git版本2.43.0GCC版本gcc 13.3.0OpenSSL版本 3.0.13STL 中 unordered_map 使用自定义类型作为key的实现std::unordered_map的定义template class Key, class T, class Hash std::hashKey, class KeyEqual std::equal_toKey, class Allocator std::allocatorstd::pairconst Key, T class unordered_map;其中Key哈希表key的类型T 哈希表值的类型Hash针对Key的哈希函数默认是std::hashKeyKeyEqual相等判断子Equality Predicate用于判断两个key是否相等默认值是std::equal_toKey。Allocator分配器模板参数用于控制容器如何分配和释放内存一般不用关注在使用自定义类型作为key时需要关注的是Hash和KeyEqual。可以看到这两个模版参数都给出了默认值。下面分别来分析。Hash的默认值是std::hashKey。STL只为内置类型整型、浮点、指针等和少数标准库类型字符串类型、智能指针等提供了std::hash的特化。所以在使用自定义类型作为key的时候要提供哈希函数。可以通过特化std::hashKey或显式传入自定义仿函数/闭包实现。KeyEqual的默认值是std::equal_toKey。std::equal_toKey除非被特化否则会调用Key上的operator。比如我的实验环境的std::equal_to的实现为templatetypename _Tp struct equal_to : public binary_function_Tp, _Tp, bool { _GLIBCXX14_CONSTEXPR bool operator()(const _Tp __x, const _Tp __y) const { return __x __y; } };因此如果要使用自定义类型作为key自定义类型必须提供operator可以使得std::equal_toKey可用或自定义相等判断子Equality Predicate。自定义类型作为key示例按照Hash和KeyEqual实现的不同给出以下几种示例作为参考。特化std::hashKey 定义operator这就相当于补全实现调用走默认的std::hashKey和std::equal_toKey。示例如下#include functional // std::hash #include iostream #include string #include unordered_map struct Point { int x; int y; }; // 在 std 命名空间中特化 std::hash // 注意, 根据 Effective C 第25条: 为用户定义类型进行std templates // 全特化是好的但千万不要尝试在std内加入某些对std而言全新的东西 namespace std { template struct hashPoint { std::size_t operator()(const Point p) const noexcept { std::size_t h1 std::hashint{}(p.x); std::size_t h2 std::hashint{}(p.y); return h1 ^ (h2 1); // 简单组合 } }; } // namespace std // 定义operator bool operator(const Point a, const Point b) { return a.x b.x a.y b.y; } int main() { std::unordered_mapPoint, std::string m; m[{1, 2}] A; m[{3, 4}] B; std::cout m[{1, 2}] , m[{3, 4}] \n; return 0; } /* g -stdc17 custom_key_1.cpp -o custom_key_1 */运行输出如下ubuntuVM-4-13-ubuntu:~/blog_code/c/stl/unordered_map_custom_key$ ./custom_key_1 A, B自定义 Hash 仿函数 KeyEqual 仿函数作为模板参数都是自定义仿函数实现如下#include cstddef #include iostream #include unordered_map struct Point { int x; int y; }; struct PointHash { std::size_t operator()(const Point p) const noexcept { std::size_t h1 std::hashint{}(p.x); std::size_t h2 std::hashint{}(p.y); return h1 ^ (h2 1); // 简单组合 } }; struct PointEqual { bool operator()(const Point a, const Point b) const noexcept { return a.x b.x a.y b.y; } }; int main() { std::unordered_mapPoint, std::string, PointHash, PointEqual m; m[{1, 2}] A; m[{3, 4}] B; std::cout m[{1, 2}] , m[{3, 4}] \n; return 0; } /* g -stdc17 custom_key_2.cpp -o custom_key_2 */运行输出如下ubuntuVM-4-13-ubuntu:~/blog_code/c/stl/unordered_map_custom_key$ ./custom_key_2 A, B使用 lambda decltype传入lambda函数作为哈希函数和相等判断子。#include iostream #include string #include unordered_map struct Point { int x; int y; }; int main() { auto hash [](const Point p) { std::size_t h1 std::hashint{}(p.x); std::size_t h2 std::hashint{}(p.y); return h1 ^ (h2 1); // 简单组合 }; auto equal [](const Point a, const Point b) { return a.x b.x a.y b.y; }; // C17 写法必须显式传入 lambda 实例 std::unordered_mapPoint, std::string, decltype(hash), decltype(equal) m( 13 /*bucket 提示*/, hash, equal); // C20写法: 无需再把 lambda 传给构造函数 // std::unordered_mapPoint, std::string, decltype(hash), decltype(equal) // m; m[{1, 2}] A; m[{3, 4}] B; std::cout m[{1, 2}] , m[{3, 4}] \n; return 0; } /* g -stdc17 custom_key_3.cpp -o custom_key_3 g -stdc20 custom_key_3.cpp -o custom_key_3 */运行输出如下ubuntuVM-4-13-ubuntu:~/blog_code/c/stl/unordered_map_custom_key$ ./custom_key_3 A, B注意示例中C17和C20实现的区别C17 中lambda 闭包类型的默认构造函数和拷贝赋值运算符都是被删除的deleted因此unordered_map的默认构造函数被隐式删除必须写m(13, hash, equal)显式传实例C20让无捕获 lambda 的闭包类型获得了 defaulted 的默认构造函数和拷贝赋值于是unordered_map的默认构造函数不再被删除可直接写m。值得注意的是对有捕获的 lambdaC20 仍规定其没有默认构造函数拷贝赋值为 deleted因此这种情况即使在 C20 也必须显式传入实例。可以发现这种实现方案有细节的语法问题如果lambda存在捕获行为则更加复杂。建议还是使用前两种实现方式更好一些。如何实现好的哈希函数一个好的哈希函数应该满足以下几点确定性同一个 key每次调用必须返回相同的哈希值与相等一致如果KeyEqual判断key1和key2相等则必须有Hash(key1) Hash(key2)。反过来则不必因为允许哈希冲突哈希值分布均匀哈希值应尽量均匀散布避免大量 key 挤在少数桶里退化成链表O(n)以这三点去判断前面例子中的hash函数struct Point { int x; int y; }; struct PointHash { std::size_t operator()(const Point p) const noexcept { std::size_t h1 std::hashint{}(p.x); std::size_t h2 std::hashint{}(p.y); return h1 ^ (h2 1); // 简单组合 } };对整形来说std::hash实现上一般直接把值 static_cast 成 size_t然后返回。比如在我的测试环境中就是这样实现// Explicit specializations for integer types. #define _Cxx_hashtable_define_trivial_hash(_Tp) \ template \ struct hash_Tp : public __hash_basesize_t, _Tp \ { \ size_t \ operator()(_Tp __val) const noexcept \ { return static_castsize_t(__val); } \ };第一、二点是满足的但是可以判断出PointHash的实现冲突概率很高因此在第三点上表现并不好。目前业界比较通用的做法来自Boost早期实现用一个混合函数hash_combine示例如下template class T inline void HashCombine(std::size_t seed, const T v) { std::hashT hasher; // 0x9e3779b97f4a7c15 是黄金分割比的 64 位定点表示 seed ^ hasher(v) 0x9e3779b97f4a7c15 (seed 6) (seed 2); } struct Point { int x; int y; }; struct PointHash { std::size_t operator()(const Point p) const noexcept { std::size_t seed 0; HashCombine(seed, p.x); HashCombine(seed, p.y); return seed; } };为什么是0x9e3779b97f4a7c15 它约等于 ⌊2^64 / φ⌋其中 φ (1√5)/2 是黄金分割比。这样实现能让加入的位与已有种子充分打散配合 6和 2的移位混合使得每个输入字段都能均匀影响到最终哈希的所有比特位显著降低碰撞率。在32位系统下应该是0x9e3779b9。可以参考https://stackoverflow.com/questions/4948780/magic-number-in-boosthash-combine。注意实现中HashCombine是个函数模版可以支持对std::hash特化过的所有类型的计算。且这种实现计算轻量性能高。总结八股问答问C STL 中unordered_map使用自定义类型作为 key 时需要注意什么答主要有以下几点自定义类型必须提供operator或自定义相等判断子因为哈希冲突时底层需要比较key是否真的相等。自定义类型必须提供哈希函数标准库的std::hash并未针对自定义类型进行特化必须通过特化std::hashKey或显式传入自定义仿函数/闭包 来计算哈希值。哈希函数要尽量确保哈希值分布均匀且计算轻量。一旦元素被插入到 unordered_map 中其key的内部状态绝不能修改。实际上本身获取std::unordered_map的key的时候就是const类型不能修改但是如果用const_cast可以强行绕过。如果修改了key的成员变量导致 hash(key) 的返回值发生变化但节点依然挂在旧的桶bucket中。此时 find() 会去新桶查找找不到而 erase() 也释放不了旧节点导致 未定义的行为Undefined behaviorUB不一定会内存泄漏因为clear或者析构的时候还是会释放。因此如果必须修改key必须执行 “先删除改值再重新插入” 。其他说明文中的模版定义来自于 https://zh.cppreference.com/本文示例代码可以在仓库 https://github.com/EarthlyImmortal/blog_code 的c/stl/unordered_map_custom_key文件夹下找到参考资料deepseek官方网站(https://www.deepseek.com/)辅助https://zh.cppreference.com/cpp/container/unordered_maphttps://zh.cppreference.com/cpp/utility/functional/equal_tohttps://zh.cppreference.com/cpp/utility/hash如果本文对您有所帮助欢迎点赞、关注、评论和转发。如果您有相关使用经验或见解也欢迎在评论区分享交流。我将持续更新 C 后台开发相关的技术知识感谢您的阅读与支持