Qt4 QHash哈希冲突

Question

我正在使用QT 4.8，我注意到它有一个QHash类，可以如下使用：

QHash<QString, int> hash;
hash["one"] = 1;
hash["three"] = 3;
hash["seven"] = 7;
hash.insert("twelve", 12);

如果发生哈希冲突，会正确处理吗？

Answer 1

是的，将处理冲突。QHash是经典的基于哈希表的容器的标准实现，如果不能正确处理冲突，它就不会非常可靠。通常，基于哈希表的容器不会将关键字映射到列表中的单个条目，而是映射到一个"bucket"，该"bucket"可能包含多个条目，其中不同的关键字映射到相同的哈希值。

当获取值时，密钥的哈希值会导致正确的bucket，然后容器将遍历bucket中的条目，直到找到与您要查找的特定密钥匹配的项。

尽管我在文档中找不到关于Qt实现的"正确性"的具体参考，但这句话并没有被引用。我无法想象会有其他情况。

QHash的内部哈希表以2的幂增长，每次增长，项目被重新定位到一个新的bucket中，计算为qHash(key)%QHash:：capacity()(铲斗的数量)。

一个简单的测试将增加我们的信心：

BadHashOjbect.h

#ifndef BADHASHOBJECT_H
#define BADHASHOBJECT_H
class BadHashObject
{
public:
BadHashObject(const int value): value(value){}
int getValue() const
{
return value;
}
private:
int value;
};
bool operator==(const BadHashObject &b1, const BadHashObject &b2)
{
return b1.getValue() == b2.getValue();
}
uint qHash(const BadHashObject &/*key*/)
{
return 1;
}
#endif // BADHASHOBJECT_H

main.cpp

#include <iostream>
#include <QHash>
#include "BadHashObject.h"
using namespace std;
int main(int , char **)
{
cout << "Hash of BadHashObject(10) is: " << qHash(BadHashObject(10)) << endl;
cout << "Hash of BadHashObject(100) is: " << qHash(BadHashObject(100)) << endl;
cout << "Adding BadHashObject(10), value10 and BadHashObject(100), value100" << endl;
QHash<BadHashObject, QString> hashMap;
hashMap.insert(BadHashObject(10), QString("value10"));
hashMap.insert(BadHashObject(100), QString("value100"));
cout << "Size of hashMap: " << hashMap.size() << endl;
cout << "Value stored with key 10: " << hashMap.value(BadHashObject(10)).toStdString() << endl;
cout << "Value stored with key 100: " << hashMap.value(BadHashObject(100)).toStdString() << endl;
}

BadHashObject类存储int，其哈希函数将始终返回1，因此使用此类型作为键添加到QHash的所有对象都将导致冲突。我们的测试程序的输出表明碰撞得到了正确的处理。

Hash of BadHashObject(10) is: 1
Hash of BadHashObject(100) is: 1
Adding BadHashObject(10), value10 and BadHashObject(100), value100
Size of hashMap: 2
Value stored with key 10: value10
Value stored with key 100: value100