一个适用于向量的良好哈希函数

Question

我有一些整数向量，希望能够在C++11的unordered_map中高效地存储，我的问题是：

如何最好地存储它们并优化查找?

我想到了以下哈希函数:

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 时间花费在 unordered map 的查找上，这不是非常理想的 :(

- Martin Kristiansen

---

哈希表在每次插入和查找时都会执行一次，而且在底层表格调整大小时，每个对象可能会再次执行哈希。 - RichardPlunkett

澄清一下，系统不会对已经在表中的内容进行哈希处理，仅仅因为你正在查找某些东西，而是只对你用于查找的键进行哈希处理。 - RichardPlunkett

顺便提一下，异或是一个令人震惊的哈希组合器。 - RichardPlunkett

以下是对@RichardPlunkett评论中“xor是一种不好的组合器”的进一步解释：如果两个向量具有相同的数据但顺序不同，则它们将具有相同的哈希值。如果向量中有多个相同的值，则其中大部分值将不会影响组合后的哈希值（它们相互抵消）。如果值通常较小（或者使用uint32_t的所有位中的范围不太大），则组合后的哈希值将不使用最高有效位。 - Michael Burr

@Martin，排序不太可能有帮助，除非它意味着一个特别糟糕的例子不会出现，但还有许多其他例子存在。 - RichardPlunkett

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

似乎起作用了。

编辑：看看这个答案稍微慢一点，但确实产生更好的哈希分布。我会选择那一个。

- HolKann

---

这是一个起始种子。它很快会被异或操作(^=)改变。vec.size()(第二行)可能更好，因为它考虑了更多向量信息。我已经调整了回复。 - HolKann

std::accumulate也可以应用。https://gcc.godbolt.org/z/vaK4h4dce - Ayxan Haqverdili

根据向量分量的分布特性，将它们全部组合起来可能会过度。 - user1196549

Answer 2

目前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

---

不错。我最近也使用了Thomas Mueller的答案。也许可以扩展你的答案，加入一个64位版本？ - HolKann

Answer 3

boost::hash_combine的效果还算不错，但并不是特别好 HolKann的回答已经足够好了，但我建议为每个条目使用一个好的哈希函数，然后再将它们组合起来。问题在于std::hash不是一个好的哈希函数，而boost::hash_combine也不足以弥补这一点。

template<typename T>
T xorshift(const T& n,int i){
  return n^(n>>i);
}

uint32_t hash(const uint32_t& v) {
  uint32_t p = 0x55555555ul; // pattern of alternating 0 and 1
  uint32_t c = 3423571495ul; // random uneven integer constant; 
  return c*xorshift(p*xorshift(n,16),16);
}

// if c++20 rotl is not available:
template <typename T,typename S>
typename std::enable_if<std::is_unsigned<T>::value,T>::type
constexpr rotl(const T n, const S i){
  const T m = (std::numeric_limits<T>::digits-1);
  const T c = i&m;
  return (n<<c)|(n>>((T(0)-c)&m)); // this is usually recognized by the compiler to mean rotation, also c++20 now gives us rotl directly
}

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 = rotl(ret,11)^hash(i);
    }
    return ret;
  }
};

- Wolfgang Brehm

Answer 4

我尝试了解决一个 LeetCode 问题的方法，参考了 see 的答案。但是对于某些输入，该函数会溢出 ints。所以，我回到了你的方法。但是，如果有像 {0}，{0, 0}，{0, 0, 0} 这样的元素，因为 int 的哈希值是数字本身，所有这些元素的哈希值都为 0，导致你的函数会产生很多冲突。

我稍微修改了一下，包括索引来降低冲突率：

struct hash {
    std::size_t operator()(std::vector<int> const& vec) const {
        std::hash<uint32_t> h;
        std::size_t ret = vec.size();
        for(auto& i : vec) {
            ret ^= h(i) | i;
        }
        return ret;
    }
};

我只是将哈希值与索引进行“或”运算，所以 {0}，{0, 0}，{0, 0, 0} 会产生不同的哈希值。这是一个非常糟糕的哈希函数，但它对我的目的很有效 :P

- Hemil

---

如果您只是将所有的int强制转换为uint32_t，会发生什么？那么see的答案仍然有效，我猜这比std hash更快且碰撞更少（基于Thomas Mueller的论点）。 - HolKann

@HolKann 我不知道。但我猜答案应该仍然是一样的，因为整数的哈希值就是整数的值。 - Hemil