QHash 在不同的 qt 版本中表现不同

Question

我正在 QT 版本 4.8 和 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());
}

此代码的行为不同，因为插入顺序在不同的 qt 版本中是不同的。

在 Qt 5.12.9 中

在 Qt 4.8 中

我该如何解决这个问题？为什么会这样？

我查看了 QHash 文档，但没有找到任何答案。 https://doc.qt.io/qt-5/qhash.html#insert

Answer 1

一个可能的罪魁祸首是 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.

如文档所述，您不应依赖散列中条目的顺序 table。对于调试或测试，您可以尝试将 QT_HASH_SEED 设置为 0 以查看它是否重现旧行为。

Answer 2

QT 文档指出：

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

这是哈希函数的预期行为。他们不以任何顺序存储项目，但是您可以足够快地获得任何项目 O(1)。地图将键存储在树中，您可以按顺序迭代它们，但查找是 log(N)。

哈希函数的实现可能已经改变，您得到不同的顺序。这就是这里发生的事情。

如果地图中的项目很少，它可能比散列更快。也许你可以用 QMap 替换 QHash。

如果您有很多项目并且需要非常快速的查找（因此 QHash 是您的最佳选择），那么您可以将有序键单独存储在向量中并使用它进行迭代。

QHash 在不同的 qt 版本中表现不同

QHash behaving different in different qt version

c++

qt

insert

qhash