C++中struct作unordered_map键时性能骤降的原因及解决方法

你的性能问题100%来自极差的自定义哈希函数，和unordered_map本身无关：

• 你当前实现的哈希return o.i ^ o.j ^ o.k;有两个致命缺陷：
  1. 异或满足交换律，只要三个坐标值的集合相同，不管顺序如何，哈希值完全一致，比如(1,2,3)、(2,1,3)、(3,2,1)的哈希值完全相同
  2. 你的测试用例中坐标范围是0-99，99的二进制最高位为64（2^6），三个数异或的结果最大仅为127，也就是说100100100=100万个键，只会落到最多128个哈希桶中，平均每个桶挂载近8000个元素
• 这种级别的哈希碰撞会让unordered_map的时间复杂度从期望的O(1)直接退化为O(n)，因此数据量增长10倍时，耗时增长100倍完全符合复杂度退化的表现。
• Python版本性能正常的原因是Python内置的tuple哈希实现了雪崩效应，不同输入的哈希值分布均匀，几乎不会出现大规模碰撞。

按收益从高到低排序：

• 第一优先级：替换为高质量哈希函数，不要用简单异或凑哈希。可以参考通用哈希组合方式实现，示例代码如下：

#include <functional>
struct key_hash
{
    size_t operator()(const key& o) const {
        size_t seed = 0;
        // 0x9e3779b9是黄金分割比对应的魔数，用于打散哈希值分布
        seed ^= std::hash<int>()(o.i) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        seed ^= std::hash<int>()(o.j) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        seed ^= std::hash<int>()(o.k) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        return seed;
    }
};

仅替换哈希函数后，100100100规模的插入耗时会降到0.1秒级别，性能反超Python版本。

• 低门槛优化：插入前提前预留哈希表空间，避免插入过程中多次rehash。在三层循环前添加一行代码：

  memory.reserve(I * J * K);
  

  可以减少30%左右的扩容开销。
• 最高性能方案：如果你的三维坐标是连续范围，完全不需要用哈希表，直接用连续数组存储，性能比最优哈希表还高3-10倍。示例：

  #include <vector>
  std::vector<int> memory(I*J*K);
  // 访问时按下标定位
  memory[i*J*K + j*K + k] = i+j+k;
  

  这种方式没有任何哈希计算、碰撞处理开销，且内存连续缓存命中率极高。
• 进阶优化：如果确实需要哈希表的稀疏键存储能力，可以替换标准库unordered_map为高性能 flat hash 实现，相比标准库实现通常有2-5倍的性能提升。

内容的提问来源于stack exchange，提问作者littleqjy