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是經典的基於散列表容器的標準實現，如果它不能正確處理衝突，它將不會非常可靠。通常，基於散列表的容器將把鍵不映射到列表中的單個條目，而映射到可能包含多個條目的「桶」，其中不同的鍵映射到相同的散列值。

當獲取值時，密鑰的哈希值會導致正確的桶，然後容器將遍歷桶中的條目，直到找到您正在查找的特定鍵的匹配。

儘管我無法在文檔中找到Qt實現的「正確性」的具體參考，但是這個引用沒有涉及到。我無法想象它在其他方面。

QHash的內部哈希表的增長由兩個大國，並且每次 長的時間，項目將在一個新的水桶搬遷，計算qHash（鍵） ％QHash ::容量（）（數量桶）。

一個簡單的測試將增加我們的信心：

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