具有关联属性的boost :: hash_combine替代方案是什么？

Question

我正在寻找一种具有可交换性质的hash_combine函数。

例如，我希望能够将值a、b、c、d依次组合以获得序列的哈希键，或者将a和b组合，然后将c和d组合，再将结果组合。这两种方法应该得到相同的结果。

boost::hash_combine没有这个属性：

  // a * b * c * d                                                                                                                                                                                        
  std::size_t seed = 0;
  boost::hash_combine(seed, 234);
  boost::hash_combine(seed, 62);
  boost::hash_combine(seed, 675);
  boost::hash_combine(seed, 916);
  std::cout << seed << std::endl; // 706245846748881

  // (a * b) * (c * d)                                                                                                                                                                                    
  std::size_t seed1 = 0;
  boost::hash_combine(seed1, 234);
  boost::hash_combine(seed1, 62);
  std::size_t seed2 = 0;
  boost::hash_combine(seed2, 675);
  boost::hash_combine(seed2, 916);
  boost::hash_combine(seed1, seed2); // 11337801211148

有没有好的 hash_combine 函数呢？

附注：我这样做的原因是我将哈希键分配给在DAG中找到的序列。我正在运行动态规划，为所有状态对之间的（序列）寻找哈希键。

- Frank

Answer 1

纯异或怎么样？

std::size_t seed = 0;
seed ^= boost::hash_value(234);
seed ^= boost::hash_value(62);
...

- Baffe Boyois

---

谢谢，那会起作用。有人知道这个与hash_combine的行为相比，可能发生碰撞等方面的情况吗？ - Frank

参考文档中包含了boost::hash_combine所使用的确切公式。 - Baffe Boyois

你可以立即看到XOR的一个问题是对于任何A，A ^ A == 0。因此，[a，a]，[b，b]，[c，c] ...都具有相同的哈希值。此外，[a，b，c，a]与[b，c]具有相同的哈希值。在这些情况下，“+”比“^”更好。 - Baffe Boyois

嗯，有点棘手，我可能不想使用它... 关于 boost::hash_combine 的参考资料，它说 seed ^= hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);。 - Frank

这也介绍了可交换性质，但这可能不是理想的，因为它会为任何共享相同元素和相同数量的集合产生相同的哈希值，而且在重复时也会被取消。 - user13507303