c++ - 与 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功能对于这个数据集表现不佳。您可以使用此代码进行测试，该代码显示一百万个测试条目的近 600,000 次冲突。

这是一个简单的修复：

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

幻数是接近 2^32 * (sqrt(5)-1)/2 的素数——请参阅Knuth以了解为什么它可以扩大区间。