How to write qHash for a QSet<SomeClass*> container?

Question

I need to implement a set of sets in my application. Using QSet with a custom class requires providing a qHash() function and an operator==.

The code is as follows:

    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*>

How can I implement qHash(QSet<Custom*>), to be able to use QSet< QSet<SomeClass*> >?

Edit:

Additional question: In my application the "set of sets" can contain up to 15000 sets. Each subset up to 25 Custom class pointers. How to guarantee that qHash(QSet<Custom*>) will be unique enough?

Answer 1

You cannot implement qHash with boost::hash_range/boost::hash_combine (which is what pmr's answer does, effectively), because QSet is the Qt equivalent of std::unordered_set, and, as the STL name suggests, these containers are unordered, whereas the Boost Documentation states that hash_combine is order-dependent, ie. it will hash permutations to different hash values.

This is a problem because if you naively hash-combine the elements in stored order you cannot guarantee that two sets that compare equal are, indeed, equal, which is one of the requirements of a hash function:

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

So, if your hash-combining function needs to produce the same output for any permutation of the input values, it needs to be commutative. Fortunately, both (unsigned) addition and the xor operation just fit the bill:

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

A common way to hash containers is to combine the hashes of all elements. Boost provides hash_combine and hash_range for this purpose. This should give you an idea how to implement this for the results of your qHash.

So, given your qHash for Custom:

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

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

  return seed;
}