Qt4 Q 해쉬 해시 충돌?

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 클래스 저장한다을 :

간단한 테스트는 우리의 자신감을 증가및 해당 해시 함수는 항상 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