与hash_combine发生太多碰撞

Question

我正在使用boost::unordered_map一个自定义结构，该结构或多或少是整数向量，并具有一个自定义散列函数，如下所示：

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功能对此数据集效果不佳。您可以使用此代码进行测试，该代码显示了100万个测试条目的近60万次碰撞。

这是一个简单的解决方法：

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

幻数是接近2 ^ 32 *（sqrt（5）-1）/ 2的质数- 有关为什么此方法可以扩大间隔的说明，请参见Knuth。