How to write qHash for a QSet 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?

Are you sure about the `QSet`? Shouldn't that be `QSet`? Your `operator==` for `Custom` will never be called by `QHash`, since it uses the built-in equality operator for pointers. — Marc Mutz - mmutz, Sep 03 '15 at 12:29

Marc Mutz - mmutz · Answer 1 · 2014-03-17T14:49:03.487

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 ^
                           });
}

pmr · Accepted Answer · 2012-02-03T13:10:25.127

4

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;
}

edited Feb 03 '12 at 13:10

answered Feb 03 '12 at 09:41

pmr

58,701
10
113
156

That was my first idea, but can I be sure that the hash will be unique? Of course I can test it in my code, but maybe there is some theory behind that? – vikin9 Feb 03 '12 at 11:49
@piotr You might want to add this to your question. Now you only ask for an implementation. Here are some hints as to what this does: http://stackoverflow.com/questions/4948780/magic-numbers-in-boosthash-combine – pmr Feb 03 '12 at 13:13
1

@Piotr: you can _never_ be sure the hash is unique. In fact, it is guaranteed _not_ to be unique simply because the hash value doesn't have enough bits to represent all possible sets (which is infinite, at least theoretically). That's why you also need an `operator==` - to detect collisions and handle them correctly. – Mat Feb 03 '12 at 13:14

How to write qHash for a QSet container?

2 Answers2

Linked