C++
unordered_map在处理哈希冲突时，主要采用的是链式寻址（Separate Chaining）策略。简单来说，当不同的键经过哈希函数计算后得到相同的哈希值，并指向同一个桶（bucket）时，这些键值对不会互相覆盖，而是被存储在该桶内部的一个链表（或类似结构）中。
解决方案
unordered_map的哈希表冲突解决机制，核心就是链式寻址。想象一下，哈希表内部其实是一系列“桶”组成的数组。每个桶，最初可能只是一个空位。当一个键值对被插入时，它的键会先通过一个哈希函数计算出一个哈希值，这个哈希值决定了它应该去哪个桶。如果这个桶是空的，那它就直接住进去。但如果这个桶已经有东西了，也就是发生了哈希冲突，
unordered_map并不会去寻找下一个空桶（那是开放寻址），而是会在这个桶内部维护一个数据结构，通常是一个链表（或者在某些实现中，为了效率会用红黑树，但标准库的
unordered_map更倾向于链表或类似结构），把新的键值对添加到这个链表的末尾。
这意味着，即使多个键最终哈希到了同一个桶，它们也能和平共处，各自在桶内的链表中占据一席之地。查找、插入或删除一个元素时，我们首先根据键计算哈希值，找到对应的桶，然后遍历该桶内的链表，通过
operator==逐一比较键来找到目标元素。这种方式的好处是实现相对简单，且在哈希函数表现良好的情况下，平均操作时间复杂度能保持在 O(1)。当然，前提是桶内的链表不能太长。
为什么
unordered_map的查找效率通常是 O(1)，但在最坏情况下会退化到 O(N)？
这其实是哈希表设计的一个固有特性，也是链式寻址策略下最直观的性能体现。我们说
unordered_map的平均时间复杂度是 O(1)，是基于一个理想假设：哈希函数能够将所有键均匀地分布到各个桶中。在这种理想状态下，每个桶里的链表都非常短，可能只有一个或两三个元素。那么，查找、插入或删除一个元素时，我们只需计算哈希值，定位到桶，然后遍历一个极短的链表，这个操作的时间开销可以被认为是常数级的，所以是 O(1)。
然而，现实往往不那么理想。最坏情况就是，如果所有的键，或者大部分键，经过哈希函数计算后都落到了同一个桶里。这可能是因为哈希函数设计得不够好，对某些特定类型的数据分布产生了“偏见”，导致哈希值扎堆；也可能是因为恶意构造的输入数据，专门针对哈希函数进行攻击。一旦出现这种情况，某个桶内的链表就会变得非常长，甚至包含了
unordered_map中几乎所有的元素。此时，寻找一个特定元素就意味着需要遍历这个长链表，其时间复杂度就退化成了 O(N)，N 是
unordered_map中元素的总数。这和在普通链表中查找元素没什么两样了，完全失去了哈希表应有的性能优势。我个人觉得，理解这一点对于在实际项目中预估和优化性能至关重要，它提醒我们不能盲目相信 O(1)，而是要关注哈希函数的质量和数据分布。
如何选择一个好的哈希函数来优化
unordered_map的性能？
选择或设计一个好的哈希函数，是发挥
unordered_map性能优势的关键。一个“好”的哈希函数，在我看来，需要满足几个核心标准：
- 均匀分布（Uniform Distribution）：这是最重要的。它应该能够将不同的键尽可能均匀地映射到哈希表的各个桶中，减少冲突的发生。键值分布越均匀，桶内的链表就越短，O(1) 的平均性能才能得到保证。
- 确定性（Deterministic）：对于相同的输入键，哈希函数必须始终产生相同的哈希值。否则，你将无法再次找到之前插入的元素。
- 计算效率（Fast Computation）：哈希函数的计算本身不应该成为性能瓶颈。如果哈希函数计算复杂耗时，即使它能完美分散键，整体性能也可能不佳。
对于标准库提供的基本类型（如
int,
string等），
std::hash已经提供了相当优秀的默认实现，通常无需我们操心。但当你使用自定义类型作为
unordered_map的键时，就必须提供自己的哈希函数。这通常有两种方式：
-
特化
std::hash
模板：这是最推荐的做法，让你的自定义类型能够被std::hash
识别。struct MyCustomKey { int id; std::string name; // ... 其他成员 bool operator==(const MyCustomKey& other) const { return id == other.id && name == other.name; } }; namespace std { template <> struct hash<MyCustomKey> { size_t operator()(const MyCustomKey& k) const { // 结合多个成员的哈希值 // 常见做法是使用 boost::hash_combine 或类似逻辑 size_t h1 = hash<int>()(k.id); size_t h2 = hash<string>()(k.name); return h1 ^ (h2 << 1); // 一个简单的组合方式 } }; }这里需要注意的是，除了哈希函数，你还必须为自定义类型提供
operator==
重载，因为在哈希冲突发生后，unordered_map
最终会用operator==
来比较链表中的键是否与目标键匹配。 -
作为
unordered_map
的模板参数传入：struct MyCustomHasher { size_t operator()(const MyCustomKey& k) const { size_t h1 = std::hash<int>()(k.id); size_t h2 = std::hash<std::string>()(k.name); return h1 ^ (h2 << 1); } }; std::unordered_map<MyCustomKey, ValueType, MyCustomHasher> myMap;
在实际操作中，组合多个成员的哈希值时，简单地异或（XOR）可能不是最好的策略，因为它容易导致冲突。更健壮的方法是使用一些位移和乘法操作，例如
boost::hash_combine的思路，它通过一个素数乘法和异或来混合哈希值，以减少冲突。总之，一个好的哈希函数，它的目标就是让哈希值尽可能散开，这样才能真正让
unordered_map跑起来。
unordered_map的
load_factor和
rehash机制在冲突解决中扮演什么角色？
load_factor（负载因子）和
rehash（重新哈希）是
unordered_map内部用来动态管理哈希表大小，以维持性能的关键机制。它们直接影响着冲突解决的效率。
load_factor(负载因子)： 负载因子是
unordered_map中元素数量与桶数量的比值 (
element_count / bucket_count)。它直观地反映了每个桶平均承载的元素数量。当负载因子过高时，意味着每个桶内的链表可能会变得很长，从而导致查找、插入和删除操作的平均时间复杂度从 O(1) 逐渐退化。
unordered_map有一个
max_load_factor（最大负载因子）属性，默认值通常是 1.0。这意味着，当平均每个桶的元素数量超过 1 时，
unordered_map就会考虑进行扩容。你可以通过
max_load_factor()方法获取当前设置，并通过
max_load_factor(float ml)方法修改它。在我看来，调整
max_load_factor是一个权衡空间和时间的决策。一个较低的
max_load_factor会导致更多的桶，占用更多内存，但可以保证更短的链表，从而提升性能；而较高的
max_load_factor则相反。
rehash(重新哈希)： 当
unordered_map的
load_factor超过了
max_load_factor时，它就会触发一次
rehash操作。这个过程包括：
- 创建一个新的、更大的桶数组（通常是当前桶数量的两倍或一个素数倍）。
- 遍历旧哈希表中的所有元素。
- 对每个元素重新计算哈希值（因为桶的数量变了，哈希值对桶的映射也会变）。
- 将元素插入到新的桶数组中对应的位置。
rehash的目的是为了减少每个桶中的元素数量，从而缩短链表，将平均操作时间复杂度重新拉回到 O(1)。这是一个非常重要的自动优化机制。
然而，
rehash操作本身是一个非常耗时的操作，其时间复杂度是 O(N)，其中 N 是
unordered_map中元素的总数。因为所有的元素都需要重新计算哈希并重新插入。如果在程序运行的关键路径上频繁发生
rehash，可能会导致性能抖动。为了避免这种情况，如果你知道将要插入大量元素，可以通过
reserve()方法预先分配足够的桶空间，或者通过
rehash()方法手动触发一次扩容，这样可以在非关键时刻完成耗时操作，避免在高峰期出现性能瓶颈。这就像是提前给餐厅扩建，而不是在客满时才手忙脚乱地加桌子。
以上就是C++ unordered_map实现 哈希表冲突解决的详细内容，更多请关注知识资源分享宝库其它相关文章！
发表评论:
◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。