为什么 boost::hash_combine 不是在 C 中组合哈希值的最佳方法？

在 C 中组合哈希值的最佳方式：揭秘 boost::hash_combine

在 C 世界中，boost::hash_combine 经常是被誉为组合哈希值的最佳方法。这就引出了一个问题：为什么这是最好的方法？

理解 boost::hash_combine

boost::hash_combine 函数有两个参数：一个种子值和一个要散列的值。然后，它使用一系列位操作来组合这些值，从而产生一个包含先前哈希的熵的新种子。

template <class T>
inline void hash_combine(std::size_t& seed, const T& v)
{
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

为什么它不是最好的？

令人惊讶的是，boost::hash_combine 并不像它可能的那样最优

1. 分布不良：当与 std::hash 等分布不良的哈希函数结合使用时，boost::hash_combine 会表现出很高的冲突率。
2. 熵损失：如果所有熵都集中在种子中，则可能会出现一些熵

更好的替代方案

另一种哈希组合函数可以提供良好的分布和熵保存：

template <class T>
inline size_t hash_combine(std::size_t& seed, const T& v)
{
    return rotl(seed, std::numeric_limits<size_t>::digits/3) ^ distribute(std::hash<T>{}(v));
}

此函数利用：

• 位旋转： 旋转种子以使哈希计算顺序相关。
• 良好分布： 使用自定义分布函数以获得更好的哈希分布。
• 保留熵： 在组合之前旋转种子以防止熵

性能注意事项

虽然 boost::hash_combine 很快，但替代函数牺牲了一些速度来提高哈希质量。然而，对于大多数应用程序来说，这种速度权衡通常可以忽略不计。

以上是为什么 boost::hash_combine 不是在 C 中组合哈希值的最佳方法？的详细内容。更多信息请关注PHP中文网其他相关文章！