如何对无序的std::pair进行std::hash

Question

我希望能够在unordered_container中使用std::pair作为键。我知道可以按照以下方式实现：

template<typename T>
void
hash_combine(std::size_t &seed, T const &key) {
  std::hash<T> hasher;
  seed ^= hasher(key) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

namespace std {
  template<typename T1, typename T2>
  struct hash<std::pair<T1, T2>> {
    std::size_t operator()(std::pair<T1, T2> const &p) const {
      std::size_t seed(0);
      ::hash_combine(seed, p.first);
      ::hash_combine(seed, p.second);
      return seed;
    }
  };
}

然而，我希望哈希算法不考虑std::pair中元素的顺序（即对于std::pair<A, B>和std::pair<B, A>)返回相同的种子).

我想到的一种方法是在创建我的std::pair<A, B>时应用某种排序（即某种自定义的std::make_pair）。但这太过严格，因为对象A，B可能没有任何顺序。

Q：

是否有标准的方法可以哈希一个std::pair，使元素的顺序被忽略并且对于std::pair<A, B>和std::pair<B, A>返回相同的种子？

- 101010

---

您可以使用 ^ 来组合哈希值。请参见 https://dev59.com/RG025IYBdhLWcg3wpHl_ 编辑：再想一想：这对于 std::pair<A, A> 可能不是很好，因为所有具有相等值的对都将具有哈希值 0。 - Wintermute

@Wintermute 感谢您的回复，我已经看到了那个帖子，但正如您已经提到的，由于您也提到的恶化情况，这并不适合我的需求。 ;) - 101010

“为std::pair<A, B>和std::pair<B, A>返回相同的种子”，不介意我问一下，您试图解决什么问题，这个（相当不寻常的）属性会有所帮助？ - Igor Tandetnik

@IgorTandetnik 没关系，这是为了一个碰撞跟踪器。 - 101010

为什么不直接使用 hash(first) + hash(second) 呢？ - Howard Hinnant

Answer 1

不要对键值对进行排序，要对哈希表进行排序：

namespace std {
  template<typename T1, typename T2>
  struct hash<std::pair<T1, T2>> {
    std::size_t operator()(std::pair<T1, T2> const &p) const {
      std::size_t seed1(0);
      ::hash_combine(seed1, p.first);
      ::hash_combine(seed1, p.second);

      std::size_t seed2(0);
      ::hash_combine(seed2, p.second);
      ::hash_combine(seed2, p.first);

      return std::min(seed1, seed2);
    }
  };
}

[现场示例]

- Angew is no longer proud of SO

---

您也可以通过type_info::before进行订购，这将消除一半的哈希计算（甚至可能连“if”检查也省略掉，具体取决于优化器的效果）。 - Nevin

@Nevin，你能提供一个实时示例吗？ - 101010

该解决方案无法从任意长度的二元组扩展到元组。 - Jakub Klinkovský