qHash function for QRect

Question

What is the best way to calculate the qHash value of a QRect? I need to use QRect (and maybe QRectF) as the key of QCache. Right now I am using something like this:

inline uint qHash(const QRect & r)
{
 return qHash(QByteArray::fromRawData((const char*)&r, sizeof(r)));
}

It seems to work but I don't like casting it into some raw bytes and since QRect is noy a simple struct, this may break sooner than later in future versions of Qt.

BTW. I don't store the hash values so it doesn't have to be persistent or cross-platform. But it does need to be reliable and fast.

Thanks.

Think twice before using QRectF as a QCache key... keep in mind that since QRectF contains floating point values, floating point errors can occur, and if they do they will affect the values returned by qHash(). — Jeremy Friesner, Nov 08 '10 at 01:51
@Jeremy: Thanks for the warning. I forgot about the floating point value issue. I will do the caching on the scaled pixmap with integer geometry. — Stephen Chu, Nov 08 '10 at 13:10
@Stephen But also don't be too paranoid of rounding errors. Often two slightly different numbers (due to rounding) just don't need to be treated as the same number semantically. — Christian Rau, Jul 21 '11 at 15:15

score 3 · Accepted Answer · answered Nov 08 '10 at 11:12

3

I would simply do return qHash(QString("%1,%2,%3,%4").arg(r.x()).arg(r.y()).arg(r.width()).arg(r.height())))

Also I've found this solution: http://thesmithfam.org/blog/2008/01/17/using-qrect-with-qhash/ (read comment)

answered Nov 08 '10 at 11:12

Kamil Klimek

12,884
2
43
58

1

Thanks. Hashing the printed string should work. But I'm afraid it may be a bit slower than it needs to be. The comment in the link you provided seems to be reasonably fast and reliable. I've tried it and it seems to work pretty well. – Stephen Chu Nov 08 '10 at 16:17
2

I would not suggest this as a general purpose solution, as the calculation overhead is just too big. Hash tables shall be fast - so hash functions need to be, too. – leemes Jul 21 '11 at 14:33

score 1 · Answer 2 · answered Nov 08 '10 at 01:48

1

Well, how about:

inline uint qHash(const QRect & r)
{
    return qHash(r.left()) + qHash(r.top()) + qHash(r.width()) + qHash(r.bottom());
}

answered Nov 08 '10 at 01:48

Jeremy Friesner

70,199
15
131
234

1

Sorry, but i don't think its reliable. qHash(int key) makes just uint(key), there are to many datasets that will hit same record. For rect (x:1, y:2, w:3, h:4) it will expand to 1 + 2 + 3 + (bottom: 1 + 4) = 11. There is high risk that another dataset will hit same qHash value – Kamil Klimek Nov 08 '10 at 10:57
Kamil is right. I thought of doing that at the beginning and find that basically any rectangle with the same combination of x, y, w, h will produce the same hash. – Stephen Chu Nov 08 '10 at 13:08
1

Two different rectangles returning the same hash isn't an error. That said, if it bothers you, you can multiply certain inputs to differentiate them in the results. – Jeremy Friesner Nov 08 '10 at 16:17
@Jemery: It may not be an error but it will ruin my result since it will plot the same pixmap at the wrong locations. :) Thanks for the input, though. Multiplying the inputs is what I ended up doing. Much appreciated. – Stephen Chu Nov 08 '10 at 16:21
2

No, it would not (or at least, should not, unless QCache is buggy -- which is unlikely) cause your pixmap to be plotted in the wrong location. It's allowed and expected that two different QRects can have the same hash code. Because of the pigeon-hole principle, QCache can't rely on hash codes alone. Once QCache has found a matching hash code, it still has to check with QRect::operator==() as well before returning a result. – Jeremy Friesner Nov 09 '10 at 02:18

leemes · Answer 3 · 2012-07-08T10:35:00.897

What about simply XORing each integer? As far as I know, qHash(QPair<..>) does this (with the already calculated qHashes for both items).

inline uint qHash(const QRect & r)
{
    return qHash(r.left() ^ r.top() ^ r.right() ^ r.bottom());
    // or
    return qHash(r.left()) ^ qHash(r.top()) ^
           qHash(r.right()) ^ qHash(r.bottom());
}

The same for QRectF:

inline uint qHash(const QRectF & r)
{
    return qHash(r.left()) ^ qHash(r.top()) ^
           qHash(r.right()) ^ qHash(r.bottom());
}

(Note that even rounding down to integers does NOT mean that your cache will work improperly - just the hash table "cheats" a bit.)

score 0 · Answer 4 · answered Jul 27 '16 at 17:42

I think this is most optimal solution for >=Qt5.4:

uint qHash(const QRect& r)
{
    int data[4];
    data[0] = r.left();
    data[1] = r.top();
    data[2] = r.width();
    data[3] = r.height();
    return qHashBits(data, 4 * sizeof(int));
}

For versions of Qt below 5.4 we have to write less optimal in such manner:

uint qHash(const QRect& r)
{
    QByteArray data(sizeof(int) * 4, 0);
    int* d = reinterpret_cast<int*>(data.data());
    d[0] = r.left();
    d[1] = r.top();
    d[2] = r.width();
    d[3] = r.height();
    return qHash(data);
}

qHash function for QRect

4 Answers4

Linked