Qt4 QHash hash collision?

Question

I am using QT 4.8 and I notice that it has a QHash class which can be used as follows:

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

If there is a hash collision, will it be handled correctly?

Answer 1

Yes, collisions will be handled. QHash is a standard implementation of the classic hash-table based container and wouldn't be very reliable if it didn't handle collisions correctly. Typically a hash-table based container will map keys not to a single entry in the list but to a "bucket" which may contain more than one entry where different keys map to the same hash value.

When fetching values, the hash value for the key leads to the correct bucket then the container will iterate through the entries in the bucket until it finds a match for the particular key you are looking for.

Although I could not find a specific reference in the documentation to the "correctness" of Qt's implementation, this quote eludes to it. I can't imagine it being otherwise.

QHash's internal hash table grows by powers of two, and each time it grows, the items are relocated in a new bucket, computed as qHash(key) % QHash::capacity() (the number of buckets).

A simple test will increase our confidence:

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;
}

The BadHashObject class stores an int and its hash function will always return 1 so all objects added to a QHash using this type as a key will result in a collision. The output from our test program shows that the collision is handled properly.

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