QHash behaving different in different qt version

Question

I am compiling below code in QT version 4.8 as well as in 5.12.9 .

QHash<QString, int> m_userDataHash;
m_userDataHash.insert("white", 1);
m_userDataHash.insert("yellow", 3);
m_userDataHash.insert("lightblue", 5);
m_userDataHash.insert("darkblue", 7);
m_userDataHash.insert("pink", 9);
m_userDataHash.insert("red", 11);
m_userDataHash.insert("green", 13);
m_userDataHash.insert("black", 15);
m_userDataHash.insert("grey", 17);

QHashIterator<QString, int> i(m_userDataHash);
while (i.hasNext())
{
    i.next();
    ui->ColorCombo->addItem(i.key());
}

This code is behaving differently as the order of insertion is different in different qt version.

In Qt 5.12.9

In Qt 4.8

How can I solve this problem? Why is this happening?

I checked the QHash documentation but could not figure out anything. https://doc.qt.io/qt-5/qhash.html#insert

Answer 1

QT documentation states that:

When iterating over a QMap, the items are always sorted by key. With QHash, the items are arbitrarily ordered.

That is an expected behavior for a hash function. They do not store items in any order, but instead you can get any item fast enough O(1). Maps store the keys the tree, you can iterate them in order, but the lookup is log(N).

The implementation of the hash function might have changed and you get different order. That is what happening here.

If there are few items in the map it may be faster than the hash. Probably you can just replace QHash with QMap.

If you've got lots of items and need a very fast lookup (so QHash is your best option), then you can separately store the ordered keys in the vector and use it for iterating.

Answer 2

One possible culprit is the addition of randomized hashing in 2012. source:

All hash tables are vulnerable to a particular class of denial of service attacks, in which the attacker carefully pre-computes a set of different keys that are going to be hashed in the same bucket of a hash table (or even have the very same hash value). The attack aims at getting the worst-case algorithmic behavior (O(n) instead of amortized O(1), see Algorithmic Complexity for the details) when the data is fed into the table.

In order to avoid this worst-case behavior, the calculation of the hash value done by qHash() can be salted by a random seed, that nullifies the attack's extent. This seed is automatically generated by QHash once per process, and then passed by QHash as the second argument of the two-arguments overload of the qHash() function.

This randomization of QHash is enabled by default. Even though programs should never depend on a particular QHash ordering, there may be situations where you temporarily need deterministic behavior, for example for debugging or regression testing. To disable the randomization, define the environment variable QT_HASH_SEED to have the value 0. Alternatively, you can call the qSetGlobalQHashSeed() function with the value 0.

As the documentation says, you should not rely on the order of entries in a hash table. For debugging or testing you can try setting the QT_HASH_SEED to 0 to see if it reproduces the old behavior.