0

我正在 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 中

5.12.9

在 Qt 4.8 中

4.8

我怎么解决这个问题？为什么会这样？

我检查了 QHash 文档，但什么也想不通。 https://doc.qt.io/qt-5/qhash.html#insert

4

2 回答 2

4

一个可能的罪魁祸首是在 2012 年添加了随机散列。来源：

所有哈希表都容易受到特定类别的拒绝服务攻击，其中攻击者会仔细预先计算一组不同的密钥，这些密钥将在哈希表的同一个桶中进行哈希处理（甚至具有相同的哈希值）价值）。当数据被输入表时，攻击旨在获得最坏情况下的算法行为（O(n) 而不是摊销的 O(1)，详见算法复杂性）。

为了避免这种最坏情况的行为，由 qHash() 完成的哈希值的计算可以用随机种子加盐，从而使攻击范围无效。该种子由 QHash 每个进程自动生成一次，然后由 QHash 作为 qHash() 函数的双参数重载的第二个参数传递。

默认情况下启用 QHash 的这种随机化。尽管程序永远不应该依赖于特定的 QHash 排序，但在某些情况下您可能暂时需要确定性行为，例如调试或回归测试。要禁用随机化，请将环境变量 QT_HASH_SEED 定义为值为 0。或者，您可以调用值为 0 的 qSetGlobalQHashSeed() 函数。

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

于 2020-08-11T07:59:39.670 回答
1

QT 文档指出：

遍历 QMap 时，项目总是按键排序。使用 QHash，项目是任意排序的。

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

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

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

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

于 2020-08-11T08:03:51.740 回答