C++ unordered_map实现 哈希表冲突解决

unordered_map采用链式寻址解决哈希冲突，当键哈希到同一桶时，元素被存入该桶的链表中；查找、插入、删除操作平均时间复杂度为O(1)，前提是哈希函数均匀分布键值；若哈希函数不佳或数据集中，大量键落入同一桶，链表变长，操作退化为O(N)；为此需选择均匀、确定、高效的哈希函数，尤其在自定义键类型时应合理组合成员哈希值；同时，负载因子（元素数/桶数）控制桶的拥挤程度，默认阈值为1.0，超过后触发rehash；rehash通过扩容桶数组并重新分配元素来降低冲突，恢复O(1)性能，但代价为O(N)时间开销，因此可预先调用reserve避免运行时性能抖动。

C++

unordered_map

解决方案

unordered_map

unordered_map

unordered_map

这意味着，即使多个键最终哈希到了同一个桶，它们也能和平共处，各自在桶内的链表中占据一席之地。查找、插入或删除一个元素时，我们首先根据键计算哈希值，找到对应的桶，然后遍历该桶内的链表，通过

operator==

立即学习“C++免费学习笔记（深入）”；

为什么

unordered_map

这其实是哈希表设计的一个固有特性，也是链式寻址策略下最直观的性能体现。我们说

unordered_map

然而，现实往往不那么理想。最坏情况就是，如果所有的键，或者大部分键，经过哈希函数计算后都落到了同一个桶里。这可能是因为哈希函数设计得不够好，对某些特定类型的数据分布产生了“偏见”，导致哈希值扎堆；也可能是因为恶意构造的输入数据，专门针对哈希函数进行攻击。一旦出现这种情况，某个桶内的链表就会变得非常长，甚至包含了

unordered_map

unordered_map

如何选择一个好的哈希函数来优化

unordered_map

选择或设计一个好的哈希函数，是发挥

unordered_map

1. 均匀分布（Uniform Distribution）：这是最重要的。它应该能够将不同的键尽可能均匀地映射到哈希表的各个桶中，减少冲突的发生。键值分布越均匀，桶内的链表就越短，O(1) 的平均性能才能得到保证。
2. 确定性（Deterministic）：对于相同的输入键，哈希函数必须始终产生相同的哈希值。否则，你将无法再次找到之前插入的元素。
3. 计算效率（Fast Computation）：哈希函数的计算本身不应该成为性能瓶颈。如果哈希函数计算复杂耗时，即使它能完美分散键，整体性能也可能不佳。

对于标准库提供的基本类型（如

int

string

std::hash

unordered_map

爱图表

AI驱动的智能化图表创作平台

99

查看详情

• 特化

  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

unordered_map

max_load_factor

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

1. 创建一个新的、更大的桶数组（通常是当前桶数量的两倍或一个素数倍）。
2. 遍历旧哈希表中的所有元素。
3. 对每个元素重新计算哈希值（因为桶的数量变了，哈希值对桶的映射也会变）。
4. 将元素插入到新的桶数组中对应的位置。

rehash

然而，

rehash

unordered_map

rehash

reserve()

rehash()

以上就是C++ unordered_map实现 哈希表冲突解决的详细内容，更多请关注php中文网其它相关文章！