一个好的向量散列函数

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_map 但是我有几个问题

1. 哈希多久计算一次，只有一个，一些随机数或次数？
2. 使用 == 和散列函数创建一个包装器对象来记忆散列并避免它被计算多次是否有意义？

在进行分析时，我注意到我的大量 cpu 时间花在查找无序地图上，这并不是最佳的:(

原文由 Martin Kristiansen 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

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;
}

原文由 see 发布，翻译遵循 CC BY-SA 4.0 许可协议