c++ - 与 hash_combine 发生太多冲突

我将 boost::unordered_map 与自定义结构一起使用，该结构或多或少是整数 vector ，并具有如下所示的自定义哈希函数:

std::size_t seed = 0;

for (int i = 0; i < myvec.size(); ++i)
  boost::hash_combine(seed, myvec[i]);

return seed;

当 myvec 的大小为 3 并且我用 1M 元素 1:100 x 1:100 x 1:100 填充散列时(因此 myvec 的每个元素都是 1 到 100 的整数)，我得到大约 330,000 次碰撞。

发生这么多碰撞是否正常，我该怎么做才能避免这种情况？

最佳答案

你是对的。 Boost 的 hash_combine 函数对于这个数据集表现不佳。您可以使用 this code 进行测试，它显示了 100 万个测试条目的近 600,000 次碰撞。

这是一个简单的修复:

for (int i = 0; i < myvec.size(); ++i)
  boost::hash_combine(seed, myvec[i] * 2654435761);

魔数(Magic Number)是接近 2^32 * (sqrt(5)-1)/2 的质数——请参阅 Knuth 以解释为什么它可以扩展间隔。

关于c++ - 与 hash_combine 发生太多冲突，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19966041/