Qt4 QHash哈希冲突？
Qt4 QHash哈希冲突？
提问于 2012-11-12 11:10:56
我使用的是Qt4.8，我注意到它有一个QHash类，可以按如下方式使用：
QHash<QString, int> hash;
hash["one"] = 1;
hash["three"] = 3;
hash["seven"] = 7;
hash.insert("twelve", 12);如果有哈希冲突，会被正确处理吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2012-11-12 11:53:58
是的，冲突将被处理。QHash是经典的基于哈希表的容器的标准实现，如果它不能正确处理冲突，它将不是很可靠。通常，基于散列表的容器不会将关键字映射到列表中的单个条目，而是映射到可能包含多个条目的“桶”，其中不同的关键字映射到相同的散列值。
当获取值时，键的哈希值指向正确的存储桶，然后容器将遍历存储桶中的条目，直到找到您正在查找的特定键的匹配项。
虽然我在文档中找不到关于Qt实现的“正确性”的具体引用，但这句话对它来说是难以理解的。我不能想象会有什么不同。
QHash的内部哈希表以2的幂增长，每次增长时，项都会被重新定位到新的存储桶中，计算方法为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_Hmain.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页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/13337896
复制相关文章
相似问题
腾讯云开发者
