Qt扫盲-QHash理论总结
QHash理论总结
- 一、概述
- 二、使用
- 1. 添加 元素
- 2. 获取元素
- 3. 遍历元素
- 4. 删除元素
- 5. qHash()的散列函数
- 6.算法复杂性
一、概述
QHash是Qt的通用容器类之一。它和QMap一样是用来存储(键，值)对的工具，并提供快速查找与键相关联的值的功能。
QHash提供了与QMap非常相似的功能。区别在于:
- QHash提供了比QMap更快的查找。
- 在遍历QMap时，元素总是按键排序。在QHash时，元素在QHash内部的顺序是无序的。QMap内部是有序的
- QMap的键类型必须含有< ()运算符。QHash的键类型必须能提供==()运算符和一个名为QHash()的全局散列函数(参见QHash)。其实就是构造函数要重载这些运算符，一般我们用的都是QString做键，所以不要慌。
二、使用
1. 添加 元素
下面是一个QHash的例子，键为QString，值为int:
QHash<QString, int> hash;
hash["one"] = 1;
hash["three"] = 3;
hash["seven"] = 7;
这会将以下3个(键，值)对插入到QHash中:(“one”，1)， (“three”，3)，和(“seven”，7)。
另一种向散列中插入元素的方法是使用insert():
hash.insert("twelve", 12);
int num1 = hash["thirteen"];
int num2 = hash.value("thirteen");
如果散列中没有指定键的项，这些函数返回一个默认构造的值。int、double类返回 0，QString 返回空字符串。
2. 获取元素
如果你想检查散列值是否包含特定的键，可以使用contains():
int timeout = 30;
if (hash.contains("TIMEOUT"))
timeout = hash.value("TIMEOUT");
还有一个value()重载方法，如果指定的键不存在，则使用第二个参数作为默认值:
int timeout = hash.value("TIMEOUT", 30);
一般来说，我们推荐使用contains()和value()而不是 [ ] 在散列中查找键。
原因在于，如果没有键相同的元素存在，[ ]运算符会静默地将元素插入到散列中(除非散列值是const)。
例如，下面的代码片段将在内存中创建1000个元素:
// WRONG
QHash<int, QWidget *> hash;
...
for (int i = 0; i < 1000; ++i) {
if (hash[i] == okButton)
cout << "Found button at index " << i << Qt::endl;
}
为了避免这个问题，请将上面代码中的hash[i]替换为hash.value(i)。
在内部，QHash使用散列表来执行查找。这个散列表会自动增长和缩小，以提供快速查找，而不会浪费太多内存。如果你已经知道QHash大约包含多少个元素，那么仍然可以通过调用reserve()来控制散列表的大小，但这对获得良好的性能来说不是必要的。你也可以调用capacity()来取得散列表的大小。
3. 遍历元素
如果想遍历存储在QHash中的所有键值对，可以使用迭代器。QHash提供了java风格的迭代器(QHashIterator和QMutableHashIterator)和stl风格的迭代器(QHash::const_iterator和QHash::iterator)。下面是如何使用java风格的迭代器迭代QHash<QString, int>:
QHashIterator<QString, int> i(hash);
while (i.hasNext()) {
i.next();
cout << i.key() << ": " << i.value() << Qt::endl;
}
下面是相同的代码，但使用了stl风格的迭代器:
QHash<QString, int>::const_iterator i = hash.constBegin();
while (i != hash.constEnd()) {
cout << i.key() << ": " << i.value() << Qt::endl;
++i;
}
QHash是无序的，因此不能假定迭代器的序列是可预测的。如果需要按键排序，则使用QMap。
通常，QHash每个键只允许一个值。如果使用QHash中已经存在的键调用insert()，前一个值将被删除。例如:
hash.insert("plenty", 100);
hash.insert("plenty", 2000);
// hash.value("plenty") == 2000
然而，你可以使用insertMulti()而不是insert()来为每个键存储多个值(或者使用便捷的子类QMultiHash)。
如果想取得一个键对应的所有值，可以使用values(const key &key)，它会返回一个QList:
QList<int> values = hash.values("plenty");
for (int i = 0; i < values.size(); ++i)
cout << values.at(i) << Qt::endl;
共享相同键的项获取的方法是调用find()来获取第一个键对应的元素的迭代器，然后从那里开始迭代:
QHash<QString, int>::iterator i = hash.find("plenty");
while (i != hash.end() && i.key() == "plenty") {
cout << i.value() << Qt::endl;
++i;
}
如果你只需要从散列中提取值(而不是键)，也可以使用foreach:
QHash<QString, int> hash;
...
foreach (int value, hash)
cout << value << Qt::endl;
4. 删除元素
有几种方法可以从散列中删除元素。一种方法是调用remove()方法;这将删除具有给定键的任何项。另一种方法是使用QMutableHashIterator::remove()。此外，还可以使用clear()清除整个QHash表。
QHash的键和值数据类型必须是可分配的数据类型。例如，您不能将QWidget存储为值;相反，存储一个QWidget *。
qHash()散列函数
5. qHash()的散列函数
QHash内部使用哈希表来索引值的。这个是部分原理
除了是可赋值的数据类型外，QHash的键类型还有其他要求:它必须提供 == 运算符，并且在该类型的命名空间中还必须有一个qHash()函数，该函数返回键类型参数的散列值。
函数qHash()根据键计算数值。它可以使用任何可以想象到的算法，只要给定相同的参数时总是返回相同的值。换句话说，如果e1 == e2，那么qHash(e1) == qHash(e2)也必须成立。然而，为了获得良好的性能，qHash()函数应该尽可能地为不同的键返回不同的散列值。
对于密钥类型K, qHash函数必须具有以下签名之一:
uint qHash(K key);
uint qHash(const K &key);
uint qHash(K key, uint seed);
uint qHash(const K &key, uint seed);
两个重载参数接受一个无符号整数，该整数将用于散列函数的计算。该种子由QHash提供，用于防止一系列算法复杂性攻击。如果key类型同时定义了单参数和双参数重载，QHash将使用后者(注意，你可以简单地定义一个双参数版本，并为seed参数使用默认值)。
以下是可以作为QHash键的c++和Qt类型的部分列表:任何整数类型(char、unsigned long等)、任何指针类型、QChar、QString和QByteArray。对于所有这些，头文件定义了一个QHash()函数，用于计算适当的散列值。许多其他Qt类也为它们的类型声明了一个qHash重载。请参阅每个类的文档。
如果想使用其他类型作为键，请确保提供==()运算符和qHash()实现。这个就是把 Employee 作为键的例子
例子:
#ifndef EMPLOYEE_H
#define EMPLOYEE_H
class Employee
{
public:
Employee() {}
Employee(const QString &name, QDate dateOfBirth);
...
private:
QString myName;
QDate myDateOfBirth;
};
inline bool operator==(const Employee &e1, const Employee &e2)
{
return e1.name() == e2.name()
&& e1.dateOfBirth() == e2.dateOfBirth();
}
inline uint qHash(const Employee &key, uint seed)
{
return qHash(key.name(), seed) ^ key.dateOfBirth().day();
}
#endif // EMPLOYEE_H
在上面的例子中，我们依赖Qt的全局qHash(const QString &， uint)来为我们提供员工名字的哈希值，并将其与他们出生的日期异或，以帮助生成具有相同名字的人的唯一哈希值。
请注意，Qt提供的qHash()重载的实现可能随时改变。你不能指望qHash()在不同的Qt版本中(对于相同的输入)会得到相同的结果。
6.算法复杂性
所有的散列表都容易受到一类特定的拒绝服务攻击，攻击者会仔细地预先计算一组不同的键，这些键将被散列到散列表的同一个桶中(甚至具有相同的散列值)。攻击的目的是在数据被输入到表中时获得最坏情况下的算法行为(O(n)，而不是平摊O(1)，详情请参阅算法复杂性。这个就是哈希算法函数本身的问题。也就是那个散列函数把多个值计算到同一个位置了。
为了避免这种最坏情况下的行为，可以在qHash()计算哈希值时添加随机种子，从而消除攻击的范围。该种子由QHash在每个进程中自动生成一次，然后作为QHash()函数的两个参数重载的第二个参数传递给QHash。
QHash的这种随机化在默认情况下是启用的。尽管程序永远不应该依赖于特定的QHash排序，但在某些情况下，您可能需要临时确定的行为，例如调试或回归测试。要禁用随机化，可以定义环境变量QT_HASH_SEED的值为0。或者，你可以调用qSetGlobalQHashSeed()函数，参数值为0。