如何为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*>

我该如何实现qHash(QSet<Custom*>),能够使用QSet< QSet<SomeClass*> >？

编辑:

附加问题:在我的应用程序中,"集合集"最多可包含15000套.每个子集最多25个Custom类指针.如何保证qHash(QSet<Custom*>)足够独特？

Answer 1

你不能qHash用boost::hash_range/ 来实现boost::hash_combine(这是pmr的答案有效),因为QSet它是Qt的等价物std::unordered_set,并且,正如STL名称所暗示的那样,这些容器是无序的,而Boost文档声明它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 ^
                           });
}

Answer 2

对容器进行哈希处理的常见方法是组合所有元素的哈希值。为此，Boost 提供了hash_combine 和 hash_range 。这应该会让您了解如何针对您的qHash.

所以，考虑到你qHash的Custom：

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

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

  return seed;
}