unordered_map采用链式寻址解决哈希冲突，当键哈希到同一桶时，元素被存入该桶的链表中；查找、插入、删除操作平均时间复杂度为O(1)，前提是哈希函数均匀分布键值；若哈希函数不佳或数据集中，大量键落入同一桶，链表变长，操作退化为O(N)；为此需选择均匀、确定、高效的哈希函数，尤其在自定义键类型时应合理组合成员哈希值；同时，负载因子（元素数/桶数）控制桶的拥挤程度，默认阈值为1.0，超过后触发rehash；rehash通过扩容桶数组并重新分配元素来降低冲突，恢复O(1)性能，但代价为O(N)时间开销，因此可预先调用reserve避免运行时性能抖动。
C++
unordered_map
在处理哈希冲突时，主要采用的是链式寻址（Separate Chaining）策略。简单来说，当不同的键经过哈希函数计算后得到相同的哈希值，并指向同一个桶（bucket）时，这些键值对不会互相覆盖，而是被存储在该桶内部的一个链表（或类似结构）中。
解决方案
unordered_map
的哈希表冲突解决机制，核心就是链式寻址。想象一下，哈希表内部其实是一系列“桶”组成的数组。每个桶，最初可能只是一个空位。当一个键值对被插入时，它的键会先通过一个哈希函数计算出一个哈希值，这个哈希值决定了它应该去哪个桶。如果这个桶是空的，那它就直接住进去。但如果这个桶已经有东西了，也就是发生了哈希冲突，
unordered_map
并不会去寻找下一个空桶（那是开放寻址），而是会在这个桶内部维护一个数据结构，通常是一个链表（或者在某些实现中，为了效率会用红黑树，但标准库的
unordered_map
更倾向于链表或类似结构），把新的键值对添加到这个链表的末尾。
这意味着，即使多个键最终哈希到了同一个桶，它们也能和平共处，各自在桶内的链表中占据一席之地。查找、插入或删除一个元素时，我们首先根据键计算哈希值，找到对应的桶，然后遍历该桶内的链表，通过
operator==
逐一比较键来找到目标元素。这种方式的好处是实现相对简单，且在哈希函数表现良好的情况下，平均操作时间复杂度能保持在 O(1)。当然，前提是桶内的链表不能太长。
立即学习“C++免费学习笔记（深入）”；
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 { size_t operator()(const MyCustomKey& k) const { // 结合多个成员的哈希值 // 常见做法是使用 boost::hash_combine 或类似逻辑 size_t h1 = hash()(k.id); size_t h2 = hash()(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()(k.id); size_t h2 = std::hash()(k.name); return h1 ^ (h2 << 1); }};std::unordered_map 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实现 哈希表冲突解决的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1473562.html
微信扫一扫 
支付宝扫一扫 
