企业官网建设流程全解析

前言

本文探讨C++ STL 中unordered_map使用自定义类型作为 key 时的实现方式和注意事项。水平不高，能力有限，错漏之处，还请见谅。欢迎友好讨论。

环境信息

• 操作系统版本：ubuntu24.04

• CMake版本：4.2.0

• Git版本：2.43.0

• GCC版本：gcc 13.3.0

• OpenSSL版本： 3.0.13

STL 中 unordered_map 使用自定义类型作为key的实现

std::unordered_map的定义

template< class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class Allocator = std::allocator<std::pair<const Key, T>> > class unordered_map;

其中：

• Key：哈希表key的类型

• T： 哈希表值的类型

• Hash：针对Key的哈希函数，默认是std::hash<Key>

• KeyEqual：相等判断子（Equality Predicate），用于判断两个key是否相等，默认值是std::equal_to<Key>。

• Allocator：分配器模板参数，用于控制容器如何分配和释放内存，一般不用关注

在使用自定义类型作为key时，需要关注的是Hash和KeyEqual。可以看到这两个模版参数都给出了默认值。下面分别来分析。

Hash的默认值是std::hash<Key>。STL只为内置类型（整型、浮点、指针等）和少数标准库类型（字符串类型、智能指针等）提供了std::hash的特化。所以在使用自定义类型作为key的时候，要提供哈希函数。可以通过特化std::hash<Key>或显式传入自定义仿函数/闭包实现。

KeyEqual的默认值是std::equal_to<Key>。std::equal_to<Key>除非被特化，否则会调用Key上的operator==。比如，我的实验环境的std::equal_to的实现为：

template<typename _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_to<Key>可用）或自定义相等判断子（Equality Predicate）。

自定义类型作为key示例

按照Hash和KeyEqual实现的不同，给出以下几种示例作为参考。

特化std::hash<Key>+ 定义operator==

这就相当于补全实现，调用走默认的std::hash<Key>和std::equal_to<Key>。示例如下：

#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 hash<Point> { std::size_t operator()(const Point& p) const noexcept { std::size_t h1 = std::hash<int>{}(p.x); std::size_t h2 = std::hash<int>{}(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_map<Point, std::string> m; m[{1, 2}] = "A"; m[{3, 4}] = "B"; std::cout << m[{1, 2}] << ", " << m[{3, 4}] << "\n"; return 0; } /* g++ -std=c++17 custom_key_1.cpp -o custom_key_1 */

运行输出如下：

ubuntu@VM-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::hash<int>{}(p.x); std::size_t h2 = std::hash<int>{}(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_map<Point, 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++ -std=c++17 custom_key_2.cpp -o custom_key_2 */

运行输出如下：

ubuntu@VM-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::hash<int>{}(p.x); std::size_t h2 = std::hash<int>{}(p.y); return h1 ^ (h2 << 1); // 简单组合 }; auto equal = [](const Point& a, const Point& b) { return a.x == b.x && a.y == b.y; }; // C++17 写法：必须显式传入 lambda 实例 std::unordered_map<Point, std::string, decltype(hash), decltype(equal)> m( 13 /*bucket 提示*/, hash, equal); // C++20写法: 无需再把 lambda 传给构造函数 // std::unordered_map<Point, 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++ -std=c++17 custom_key_3.cpp -o custom_key_3 g++ -std=c++20 custom_key_3.cpp -o custom_key_3 */

运行输出如下：

ubuntu@VM-4-13-ubuntu:~/blog_code/c++/stl/unordered_map_custom_key$ ./custom_key_3 A, B

注意示例中C++17和C++20实现的区别，C++17 中，lambda 闭包类型的默认构造函数和拷贝赋值运算符都是被删除的（deleted），因此unordered_map的默认构造函数被隐式删除，必须写m(13, hash, equal)显式传实例；C++20让无捕获 lambda 的闭包类型获得了 defaulted 的默认构造函数和拷贝赋值，于是unordered_map的默认构造函数不再被删除，可直接写m。

值得注意的是，对有捕获的 lambda，C++20 仍规定其没有默认构造函数（拷贝赋值为 deleted），因此这种情况即使在 C++20 也必须显式传入实例。

可以发现这种实现方案有细节的语法问题，如果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::hash<int>{}(p.x); std::size_t h2 = std::hash<int>{}(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_base<size_t, _Tp> \ { \ size_t \ operator()(_Tp __val) const noexcept \ { return static_cast<size_t>(__val); } \ };

第一、二点是满足的，但是可以判断出PointHash的实现冲突概率很高，因此在第三点上表现并不好。目前业界比较通用的做法来自Boost早期实现，用一个混合函数hash_combine，示例如下：

template <class T> inline void HashCombine(std::size_t& seed, const T& v) { std::hash<T> 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::hash<Key>或显式传入自定义仿函数/闭包 来计算哈希值。哈希函数要尽量确保哈希值分布均匀，且计算轻量。

一旦元素被插入到 unordered_map 中，其key的内部状态绝不能修改。实际上本身获取std::unordered_map的key的时候就是const类型，不能修改，但是如果用const_cast可以强行绕过。如果修改了key的成员变量，导致 hash(key) 的返回值发生变化，但节点依然挂在旧的桶（bucket）中。此时 find() 会去新桶查找，找不到；而 erase() 也释放不了旧节点，导致 未定义的行为（Undefined behavior，UB）（不一定会内存泄漏，因为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_map

• https://zh.cppreference.com/cpp/utility/functional/equal_to

• https://zh.cppreference.com/cpp/utility/hash

如果本文对您有所帮助，欢迎点赞、关注、评论和转发。如果您有相关使用经验或见解，也欢迎在评论区分享交流。我将持续更新 C++ 后台开发相关的技术知识，感谢您的阅读与支持！