向量的良好散列函数

Question

我有一些整数向量,我想在c ++ 11中的unordered_map中高效存储我的问题是:

如何最好地存储这些并优化.find查询？

我想出了以下的哈希:

class uint32_vector_hasher {
public:
  std::size_t operator()(std::vector<uint32_t> const& vec) const {
    std::size_t ret = 0;
    for(auto& i : vec) {
      ret ^= std::hash<uint32_t>()(i);
    }
    return ret;
  }
};

然后将对象存储在unordered_mapI中然而有几个问题

1. 哈希计算的频率是多少,只有一个,一些随机数或一些？
2. 是否有意义创建一个包含==和哈希函数的包装器对象来记忆哈希并避免多次计算？

在进行性能分析时,我注意到我的cpu时间相当大,花费在无序地图上进行查找,这不是最佳的:(

Answer 1

所以,当不想使用boost时,Michael Blurr的评论导致了以下哈希函数的实现:

std::size_t operator()(std::vector<uint32_t> const& vec) const {
  std::size_t seed = vec.size();
  for(auto& i : vec) {
    seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
  }
  return seed;
}

似乎工作.

Answer 2

请尽可能与专家联系:http: //www.boost.org/doc/libs/release/doc/html/hash/reference.html#boost.hash_combine

Answer 3

HolKann 当前得票最高的答案中的哈希函数会导致大量向量发生高冲突率，这些向量都包含来自小型连续分布的元素。

为了解决这个问题，每个元素的位被均匀分布（算法取自Thomas Mueller 的答案）。

std::size_t operator()(std::vector<uint32_t> const& vec) const {
  std::size_t seed = vec.size();
  for(auto x : vec) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    seed ^= x + 0x9e3779b9 + (seed << 6) + (seed >> 2);
  }
  return seed;
}