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(key) % QHash::acity() (количество ведер).

Простой тест увеличит нашу уверенность:

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