c++ - std::unordered_set 中 hasher 与 key_equal 的关系

Question

我想说，hasher 和 key_equal 之间一定有关系。如果两个元素相同(调用 equal 返回 true)它们必须具有相同的散列，否则将在错误的桶中搜索元素。

但是http://www.cplusplus.com/reference/unordered_set/unordered_set/也没有写这样的东西或 http://en.cppreference.com/w/cpp/container/unordered_set

但它显然不能正常工作。参见示例，当我尝试过滤独立于元素顺序的对时(1,2 == 2,1)

#include <iostream>
#include <functional>
#include <unordered_set>

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

namespace std
{
  template<typename S, typename T>
  struct hash<pair<S, T>>
  {
    inline size_t operator()(const pair<S, T> & v) const
    {
      size_t seed = 0;
      ::hash_combine(seed, v.first);
      ::hash_combine(seed, v.second);
      return seed;
    }
  };
}

int main() 
{
   typedef std::pair<int, int> Pair;
    Pair pa = std::make_pair(7,5);
    Pair pb = std::make_pair(5,7);
    Pair pc = std::make_pair(5,1);
    Pair pd = std::make_pair(4,3);
    Pair pe = std::make_pair(5,7);

    struct PairEq
    {
        inline bool operator()(const Pair & p1, const Pair & p2) const
        {
            return (p1.first == p2.first && p1.second == p2.second)
                || (p1.first == p2.second && p1.second == p2.first);
        }
    };

    std::unordered_set<Pair, std::hash<Pair>> h;

    h.insert(pa);
    h.insert(pb);
    h.insert(pc);
    h.insert(pd);
    h.insert(pe);

   for(auto & p : h)
   {
      std::cout << p.first << " " << p.second << "\n";
   }

   // note 5,7 AND 7,5 is outputted
}

假设通常的散列属性安全吗:如果两个元素相等，则它们具有相同的哈希值。两个相同的哈希值不代表相同的元素吗？

Answer 1

是的，根据 C++ 标准，第 § 23.2.5/5 节 [unord.req] -(无序关联容器，强调我的)，这种关系是必需的

The container’s object of type Hash — denoted by hash — is called the hash function of the container. The container’s object of type Pred — denoted by pred — is called the key equality predicate of the container.

Two values k1 and k2 of type Key are considered equivalent if the container’s key equality predicate returns true when passed those values. If k1 and k2 are equivalent, the container’s hash function shall return the same value for both.

---

请注意，此要求代表所有无序关联容器，而不仅仅是 std::unordered_set。