为什么我的std::unordered_map中所有元素都存入了0号桶？

所有元素分配到0号桶的核心原因是哈希值低位无差异，和桶数取模后结果全部为0，具体逻辑如下：

• C标准库std::unordered_map的桶索引计算规则为：桶索引 = 哈希值 % 桶数量。主流STL实现（GCC libstdc、Clang libc++等）为了提升取模运算效率，会将桶数量始终维持为2的幂，此时取模操作等价于取哈希值的低log2(桶数)位。
• 你的当前桶数为512 = 2^9，所以仅会取哈希值的低9位计算桶索引。
• 你自定义的哈希函数直接返回了Int3Pos::morton字段，而你日志中所有元素的morton值都可以被512整除，低9位全部为0，因此取模后的结果永远是0，所有元素都会被分配到0号桶。

方案1：优化哈希函数（推荐） #

给morton值增加哈希扰动逻辑，将高位的差异信息扩散到低位，避免低位全0导致的哈希冲突，参考实现如下：

struct HashFunction
{
    size_t operator()(const Int3Pos& pos) const
    {
        uint64_t x = pos.morton;
        // 64位整数扰动算法，把高位特征混合到低位
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        x = x ^ (x >> 31);
        return static_cast<size_t>(x);
    }
};

该方案兼容性好，即使后续morton值的低位出现有效数据，也能保证哈希分布均匀。

方案2：直接移除无差异的低位 #

如果你业务场景下生成的morton值天生低9位都是无效的0，可以直接将morton右移9位后作为哈希值返回：

struct HashFunction
{
    size_t operator()(const Int3Pos& pos) const
    {
        return static_cast<size_t>(pos.morton >> 9);
    }
};

该方案性能更高，但需要你确保业务逻辑里morton的低9位永远不会出现有效数据。

如果你运行程序的是32位系统，size_t为32位长度，直接返回64位的morton值会直接截断高位，也可能导致哈希值无差异，上述两个方案都可以解决该问题。

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