如何为QSet<SomeClass*>容器编写qHash？

Question

我需要在我的应用程序中实现一组集合。在自定义类中使用QSet需要提供一个qHash()函数和一个operator==。

代码如下：

    class Custom{
        int x;
        int y;
        //some other irrelevant here
    }
    inline uint qHash(Custom* c){
        return (qHash(c->x) ^ qHash(c->y));
    }
    bool operator==(Custom &c1, Custom &c2){
        return ((c1.x==c2.x) && (c1.y == c2.y));
    }

    //now I can use: QSet<Custom*>

为了能够使用QSet< QSet<SomeClass*> >，我如何实现qHash(QSet<Custom*>)

编辑：

附加问题:在我的应用程序中，“集合集合”最多可以包含15000个集合。每个子集最多25个自定义类指针。如何保证qHash(QSet<Custom*>)足够独特？

Answer 1

对容器进行散列的一种常见方法是组合所有元素的散列。Boost为此提供了hash_combine and hash_range。这应该会让您了解如何为qHash的结果实现此功能。

因此，给定Custom的qHash

uint qHash(const QSet<Custom*>& c) {
  uint seed = 0;

  for(auto x : c) {
    seed ^= qHash(x) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
  }

  return seed;
}

Answer 2

你不能用boost::hash_range/boost::hash_combine实现qHash (这是pmr的答案，有效地做到了这一点)，因为QSet是std::unordered_set的Qt等价物，并且，顾名思义，这些容器是无序的，而Boost Documentation声明hash_combine是依赖于顺序的，即。它会将排列散列为不同的散列值。

这是一个问题，因为如果您天真地按存储顺序对元素进行散列组合，则无法保证比较相等的两个集合确实相等，这是散列函数的要求之一：

For all x, y:   x == y => qHash(x) == qHash(y)

因此，如果您的散列组合函数需要为输入值的任何排列生成相同的输出，则它需要是可交换的。幸运的是，(无符号的)加法和xor运算都符合要求：

template <typename T>
inline uint qHash(const QSet<T> &set, uint seed=0) {
    return std::accumulate(set.begin(), set.end(), seed,
                           [](uint seed, const T&value) {
                               return seed + qHash(value); // or ^
                           });
}