qt - Qt4 QHash ハッシュ衝突?

Question

QHashQT 4.8 を使用していますが、次のように使用できるクラスがあることに気付きました。

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

ハッシュ衝突が発生した場合、それは正しく処理されますか?

Answer 1

はい、衝突は処理されます。QHash は、従来のハッシュ テーブル ベースのコンテナーの標準実装であり、衝突を正しく処理しないと信頼性が低くなります。通常、ハッシュ テーブル ベースのコンテナは、キーをリスト内の 1 つのエントリにマップするのではなく、異なるキーが同じハッシュ値にマップされる複数のエントリを含む「バケット」にマップします。

値をフェッチすると、キーのハッシュ値が正しいバケットにつながります。コンテナは、探している特定のキーに一致するものが見つかるまで、バケット内のエントリを反復処理します。

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_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