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

Question

我将 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 次碰撞。

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

Answer 1

你是对的。 Boost 的 hash_combine 函数对这个数据集的表现很差。您可以使用 this code 进行测试对于一百万个测试条目，它显示了将近 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解释为什么这样可以扩大间隔。