Класс QHash

Класс QHash — это шаблонный класс, предоставляющий словарь на основе хеш-таблицы. Подробнее...

• Список всех членов, включая унаследованные

Примечание: Все функции в этом классе являются реентерабельными.

Общедоступные типы

Общедоступные функции

Связанные нечлены

Подробное описание

Класс QHash — это шаблонный класс, который предоставляет словарь на основе хэш-таблицы.

QHash<Key, T> — один из общих классов контейнеров Qt. Он хранит пары (ключ, значение) и обеспечивает очень быстрый поиск значения, связанного с ключом.

QHash предоставляет функциональность, очень похожую на QMap. Различия заключаются в следующем:

• QHash обеспечивает более быстрый поиск, чем QMap. (См. Алгоритмическая сложность для получения подробной информации.)
• При итерации по QMap элементы всегда сортируются по ключу. В QHash элементы упорядочены произвольно.
• Тип ключа QMap должен предоставлять оператор<(). Тип ключа QHash должен предоставлять оператор==() и глобальную функцию хеширования, называемую qHash() (см. qHash).

Вот пример QHash со строками QString в качестве ключей и int значениями:

QHash<QString, int> hash;

Чтобы вставить пару (ключ, значение) в хэш-таблицу, можно использовать оператор[]():

hash["one"] = 1;
hash["three"] = 3;
hash["seven"] = 7;

Это вставляет следующие три пары (ключ, значение) в QHash: ("one", 1), ("three", 3) и ("seven", 7). Другой способ вставки элементов в хэш-таблицу — использование insert():

hash.insert("twelve", 12);

Чтобы выполнить поиск значения, используйте оператор[]() или value():

int num1 = hash["thirteen"];
int num2 = hash.value("thirteen");

Если в хэше нет элемента с указанным ключом, эти функции возвращают значение по умолчанию.

Если нужно проверить, содержит ли хэш определённый ключ, используйте contains():

int timeout = 30;
if (hash.contains("TIMEOUT"))
    timeout = hash.value("TIMEOUT");

Также существует перегрузка value(), которая использует второй аргумент в качестве значения по умолчанию, если в хэше нет элемента с указанным ключом:

int timeout = hash.value("TIMEOUT", 30);

В общем случае рекомендуется использовать contains() и value() вместо оператора[]() для поиска ключа в хэше. Причина заключается в том, что оператор[]() в случае отсутствия элемента с заданным ключом незаметно вставляет в хэш новый элемент (если хэш не является константным). Например, следующий фрагмент кода создаст 1000 элементов в памяти:

// WRONG
QHash<int, QWidget *> hash;
...
for (int i = 0; i < 1000; ++i) {
    if (hash[i] == okButton)
        cout << "Found button at index " << i << endl;
}

Чтобы избежать этой проблемы, замените hash[i] на hash.value(i) в приведенном выше коде.

Внутренне QHash использует хэш-таблицу для поиска. В отличие от класса QDict Qt 3, который должен был быть инициализирован простым числом, хэш-таблица QHash автоматически увеличивается и уменьшается, обеспечивая быстрый поиск без чрезмерного расхода памяти. Вы по-прежнему можете контролировать размер хэш-таблицы, вызвав reserve(), если вы уже примерно знаете, сколько элементов будет содержать QHash, но это необязательно для получения хорошей производительности. Вы также можете вызвать capacity(), чтобы получить размер хэш-таблицы.

Если нужно просмотреть все пары (ключ, значение), хранящиеся в QHash, можно использовать итератор. QHash предоставляет как итераторы в стиле Java (QHashIterator и QMutableHashIterator), так и итераторы в стиле STL (QHash::const_iterator и QHash::iterator). Вот как перебрать QHash<QString, int> с помощью итератора в стиле Java:

QHashIterator<QString, int> i(hash);
while (i.hasNext()) {
    i.next();
    cout << i.key() << ": " << i.value() << endl;
}

Вот тот же код, но с использованием итератора в стиле STL:

QHash<QString, int>::const_iterator i = hash.constBegin();
while (i != hash.constEnd()) {
    cout << i.key() << ": " << i.value() << endl;
    ++i;
}

QHash не упорядочен, поэтому последовательность итератора непредсказуема. Если требуется упорядочение по ключу, используйте QMap.

Обычно QHash позволяет только одно значение на ключ. Если вы вызываете insert() с ключом, который уже существует в QHash, предыдущее значение удаляется. Например:

hash.insert("plenty", 100);
hash.insert("plenty", 2000);
// hash.value("plenty") == 2000

Однако, вы можете хранить несколько значений на один ключ, используя insertMulti() вместо insert() (или используя удобный подкласс QMultiHash). Если вы хотите получить все значения для одного ключа, вы можете использовать values(const Key &key), которая возвращает QList<T>:

QList<int> values = hash.values("plenty");
for (int i = 0; i < values.size(); ++i)
    cout << values.at(i) << endl;

Элементы с одинаковым ключом доступны от последнего к первому вставленному. Более эффективный подход — вызвать find() для получения итератора первого элемента с ключом и итерировать оттуда:

QHash<QString, int>::iterator i = hash.find("plenty");
while (i != hash.end() && i.key() == "plenty") {
    cout << i.value() << endl;
    ++i;
}

Если вам нужно только извлечь значения из хэша (не ключи), вы также можете использовать foreach:

QHash<QString, int> hash;
...
foreach (int value, hash)
    cout << value << endl;

Элементы могут быть удалены из хэша несколькими способами. Один из них — вызвать remove(); это удалит любой элемент с заданным ключом. Другой способ — использовать QMutableHashIterator::remove(). Кроме того, вы можете очистить весь хэш, используя clear().

QHash's типы данных ключа и значения должны быть присваиваемыми типами данных. Например, вы не можете хранить QWidget как значение; вместо этого храните QWidget *.

Функция хэширования qHash()

Тип ключа QHash имеет дополнительные требования помимо того, что он является присваиваемым типом данных: он должен предоставлять operator==(), и в пространстве имен типа также должна быть функция qHash(), которая возвращает значение хэша для аргумента типа ключа.

Функция qHash() вычисляет числовое значение на основе ключа. Она может использовать любой алгоритм, как долго, как она всегда возвращает то же значение, если задан тот же аргумент. Другими словами, если e1 == e2, то qHash(e1) == qHash(e2) должно также выполняться. Однако, для получения хорошей производительности, функция qHash() должна пытаться возвращать разные значения хэша для разных ключей в максимальной степени.

Для типа ключа K функция qHash должна иметь одну из этих сигнатур:

uint qHash(K key);
uint qHash(const K &key);

uint qHash(K key, uint seed);
uint qHash(const K &key, uint seed);

Перегрузки с двумя аргументами принимают целое беззнаковое число, которое должно быть использовано для инициализации вычисления функции хэширования. Эта инициализация предоставляется QHash для предотвращения атак на алгоритмическую сложность. Если определены перегрузки как с одним, так и с двумя аргументами для типа ключа, последняя используется QHash (обратите внимание, что вы можете просто определить версию с двумя аргументами и использовать значение по умолчанию для параметра инициализации).

Вот частичный список типов C++ и Qt, которые могут служить ключами в QHash: любой целочисленный тип (char, unsigned long и т. д.), любой указатель, QChar, QString и QByteArray. Для всех этих типов заголовок <QHash> определяет функцию qHash(), которая вычисляет подходящее значение хэша. Многие другие классы Qt также объявляют перегрузку qHash для своего типа; обратитесь к документации каждого класса.

Если вы хотите использовать другие типы в качестве ключа, убедитесь, что вы предоставили оператор ==() и реализацию qHash().

Пример:

#ifndef EMPLOYEE_H
#define EMPLOYEE_H

class Employee
{
public:
    Employee() {}
    Employee(const QString &name, const QDate &dateOfBirth);
    ...

private:
    QString myName;
    QDate myDateOfBirth;
};

inline bool operator==(const Employee &e1, const Employee &e2)
{
    return e1.name() == e2.name()
           && e1.dateOfBirth() == e2.dateOfBirth();
}

inline uint qHash(const Employee &key, uint seed)
{
    return qHash(key.name(), seed) ^ key.dateOfBirth().day();
}

#endif // EMPLOYEE_H

В приведенном выше примере мы полагались на глобальную функцию Qt qHash(const QString &, uint) для получения значения хэша для имени сотрудника и выполнили побитовое XOR с днем рождения, чтобы получить уникальные хэши для людей с одинаковыми именами.

Обратите внимание, что реализация перегрузок qHash(), предлагаемых Qt, может меняться в любое время. Вы **не должны** полагаться на то, что qHash() будет давать одинаковые результаты (для одинаковых входных данных) в разных версиях Qt.

Атаки на алгоритмическую сложность

Все хэш-таблицы уязвимы для определенного класса атак типа отказа в обслуживании, в которых злоумышленник тщательно предопределяет набор различных ключей, которые будут хэшироваться в одном ведре хэш-таблицы (или даже иметь одно и то же значение хэша). Цель атаки — получить худшее алгоритмическое поведение (O(n) вместо усредненного O(1), см. Алгоритмическая сложность для получения подробностей) при подаче данных в таблицу.

Для предотвращения такого худшего случая вычисление значения хэша, выполняемое функцией qHash(), может быть замаскировано случайным начальным значением, которое снижает масштаб атаки. Это начальное значение автоматически генерируется QHash один раз на процесс и затем передается QHash в качестве второго аргумента перегрузки функции qHash() с двумя аргументами.

Эта случайная генерация в QHash включена по умолчанию. Несмотря на то, что программы никогда не должны зависеть от конкретного порядка QHash, могут быть ситуации, когда вам временно необходимо детерминированное поведение, например, для отладки или регрессионного тестирования. Чтобы отключить случайную генерацию, определите переменную среды QT_HASH_SEED. Содержимое этой переменной, интерпретируемое как десятичное значение, будет использоваться в качестве начального значения для qHash(). В качестве альтернативы, вы можете вызвать функцию qSetGlobalQHashSeed().

См. также QHashIterator, QMutableHashIterator, QMap и QSet.

Документация по типу члена

typedef QHash::ConstIterator

Синоним Qt-стиля для QHash::const_iterator.

typedef QHash::Iterator

Синоним Qt-стиля для QHash::iterator.

typedef QHash::difference_type

Тип-псевдоним для ptrdiff_t. Предоставлен для совместимости со STL.

typedef QHash::key_type

Тип-псевдоним для Key. Предоставлен для совместимости со STL.

typedef QHash::mapped_type

Тип-псевдоним для T. Предоставлен для совместимости со STL.

typedef QHash::size_type

Тип-псевдоним для int. Предоставлен для совместимости со STL.

Документация по функциям-членам

QHash::QHash()

Создаёт пустой хэш.

См. также clear().

QHash::QHash(std::initializer_list<std::pair<Key, T> > list)

Создаёт хэш с копией каждого элемента в списке инициализации list.

Эта функция доступна только если программа компилируется в режиме C++11.

Эта функция была добавлена в Qt 5.1.

QHash::QHash(const QHash &other)

Создаёт копию other.

Эта операция выполняется за постоянное время, так как QHash использует неявное совместное использование. Это делает возврат QHash из функции очень быстрым. Если модифицируется общий экземпляр, он будет скопирован (copy-on-write), и это занимает линейное время.

См. также operator=().

QHash::QHash(QHash &&other)

Перемещающее создание экземпляра QHash, делая его указывающим на тот же объект, на который указывал other.

Эта функция была добавлена в Qt 5.2.

QHash::~QHash()

Уничтожает хэш. Ссылки на значения в хэше и все итераторы этого хэша становятся недействительными.

iterator QHash::begin()

Возвращает итератор STL, указывающий на первый элемент в хэше.

См. также constBegin() и end().

const_iterator QHash::begin() const

Это перегруженная функция.

int QHash::capacity() const

Возвращает количество ведер во внутренней хэш-таблице QHash.

Единственная цель этой функции — предоставить средство для тонкой настройки использования памяти QHash. В целом, вам редко понадобится вызывать эту функцию. Если вы хотите узнать, сколько элементов в хэше, вызовите size().

См. также reserve() и squeeze().

const_iterator QHash::cbegin() const

Возвращает константный итератор STL, указывающий на первый элемент в хэше.

Эта функция была добавлена в Qt 5.0.

См. также begin() и cend().

const_iterator QHash::cend() const

Возвращает константный итератор STL, указывающий на воображаемый элемент после последнего элемента в хэше.

Эта функция была добавлена в Qt 5.0.

См. также cbegin() и end().

void QHash::clear()

Удаляет все элементы из хэша.

См. также remove().

const_iterator QHash::constBegin() const

Возвращает константный итератор STL, указывающий на первый элемент в хэше.

См. также begin() и constEnd().

const_iterator QHash::constEnd() const

Возвращает const STL-подобный итератор, указывающий на воображаемый элемент после последнего элемента в хэше.

См. также constBegin() и end().

const_iterator QHash::constFind(const Key &key) const

Возвращает итератор, указывающий на элемент с key в хэше.

Если в хэше нет элемента с key, функция возвращает constEnd().

Эта функция была добавлена в Qt 4.1.

См. также find() и QMultiHash::constFind().

bool QHash::contains(const Key &key) const

Возвращает true, если в хэше есть элемент с key; в противном случае возвращает false.

См. также count() и QMultiHash::contains().

int QHash::count(const Key &key) const

Возвращает количество элементов, связанных с key.

См. также contains() и insertMulti().

int QHash::count() const

Это перегруженная функция.

То же самое, что и size().

bool QHash::empty() const

Эта функция предоставлена для совместимости со STL. Она эквивалентна isEmpty(), возвращая true, если хэш пустой; в противном случае возвращает false.

iterator QHash::end()

Возвращает STL-подобный итератор, указывающий на воображаемый элемент после последнего элемента в хэше.

См. также begin() и constEnd().

const_iterator QHash::end() const

Это перегруженная функция.

iterator QHash::erase(iterator pos)

Удаляет пару (ключ, значение), связанную с итератором pos из хэша и возвращает итератор на следующий элемент в хэше.

В отличие от remove() и take(), эта функция никогда не вызывает перерасчет внутренней структуры данных QHash. Это означает, что ее можно безопасно вызывать во время итерирования, и она не повлияет на порядок элементов в хэше. Например:

QHash<QObject *, int> objectHash;
...
QHash<QObject *, int>::iterator i = objectHash.find(obj);
while (i != objectHash.end() && i.key() == obj) {
    if (i.value() == 0) {
        i = objectHash.erase(i);
    } else {
        ++i;
    }
}

См. также remove(), take() и find().

iterator QHash::find(const Key &key)

Возвращает итератор, указывающий на элемент с key в хэше.

Если в хэше нет элемента с key, функция возвращает end().

Если в хэше несколько элементов с key, эта функция возвращает итератор, указывающий на значение, которое было вставлено последним. Другие значения доступны, увеличивая итератор. Например, вот код, который итерируется по всем элементам с тем же ключом:

QHash<QString, int> hash;
...
QHash<QString, int>::const_iterator i = hash.find("HDR");
while (i != hash.end() && i.key() == "HDR") {
    cout << i.value() << endl;
    ++i;
}

См. также value(), values() и QMultiHash::find().

const_iterator QHash::find(const Key &key) const

Это перегруженная функция.

iterator QHash::insert(const Key &key, const T &value)

Вставляет новый элемент с key и значением value.

Если элемент с key уже существует, значение этого элемента заменяется на value.

Если существует несколько элементов с key, значение последнего вставленного элемента заменяется на value.

См. также insertMulti().

iterator QHash::insertMulti(const Key &key, const T &value)

Вставляет новый элемент с key и значением value.

Если в хэше уже существует элемент с тем же ключом, эта функция просто создаст новый. (Это поведение отличается от insert(), которая перезаписывает значение существующего элемента.)

См. также insert() и values().

bool QHash::isEmpty() const

Возвращает true, если хэш не содержит элементов; в противном случае возвращает false.

См. также size().

const Key QHash::key(const T &value) const

Возвращает первый ключ, сопоставленный со значением value.

Если в хэше нет элемента со значением value, функция возвращает значение ключа по умолчанию.

Эта функция может быть медленной (линейное время), так как внутренняя структура данных QHash оптимизирована для быстрого поиска по ключу, а не по значению.

См. также value() и keys().

const Key QHash::key(const T &value, const Key &defaultKey) const

Это перегруженная функция.

Возвращает первый ключ, сопоставленный со значением value, или defaultKey, если в хэше нет элемента, сопоставленного со значением value.

Эта функция может быть медленной (линейное время), так как внутренняя структура данных QHash оптимизирована для быстрого поиска по ключу, а не по значению.

Эта функция была добавлена в Qt 4.3.

key_iterator QHash::keyBegin() const

Возвращает const STL-подобный итератор, указывающий на первый ключ в хэше.

Эта функция была добавлена в Qt 5.6.

См. также keyEnd().

key_iterator QHash::keyEnd() const

Возвращает const STL-подобный итератор, указывающий на воображаемый элемент после последнего ключа в хэше.

Эта функция была добавлена в Qt 5.6.

См. также keyBegin().

QList<Key> QHash::keys() const

Возвращает список, содержащий все ключи в хэше в произвольном порядке. Ключи, которые встречаются несколько раз в хэше (потому что элементы были вставлены с помощью insertMulti() или использовалось unite()), также встречаются несколько раз в списке.

Чтобы получить список уникальных ключей, где каждый ключ из карты встречается только один раз, используйте uniqueKeys().

Порядок гарантированно будет таким же, как и при использовании values().

См. также uniqueKeys(), values() и key().

QList<Key> QHash::keys(const T &value) const

Это перегруженная функция.

Возвращает список, содержащий все ключи, связанные со значением value, в произвольном порядке.

Эта функция может быть медленной (линейное время), так как внутренняя структура данных QHash оптимизирована для быстрого поиска по ключу, а не по значению.

int QHash::remove(const Key &key)

Удаляет все элементы, имеющие key из хэша. Возвращает количество удаленных элементов, которое обычно равно 1, но будет равно 0, если ключа нет в хэше, или больше 1, если использовалась insertMulti() с key.

См. также clear(), take() и QMultiHash::remove().

void QHash::reserve(int size)

Обеспечивает, что внутренняя хэш-таблица QHash состоит как минимум из size бакетов.

Эта функция полезна для кода, которому нужно построить огромный хэш и который хочет избежать повторного выделения памяти. Например:

QHash<QString, int> hash;
hash.reserve(20000);
for (int i = 0; i < 20000; ++i)
    hash.insert(keys[i], values[i]);

В идеале, size должен быть немного больше максимального ожидаемого количества элементов в хэше. size не обязательно должен быть простым числом, потому что QHash в любом случае будет использовать простое число внутри. Если size является недооценкой, худшее, что может произойти, это то, что QHash будет немного медленнее.

Как правило, вам редко понадобится вызывать эту функцию. Внутренняя хэш-таблица QHash автоматически уменьшается или увеличивается, чтобы обеспечить хорошую производительность, не тратя слишком много памяти.

См. также squeeze() и capacity().

int QHash::size() const

Возвращает количество элементов в хэше.

См. также isEmpty() и count().

void QHash::squeeze()

Уменьшает размер внутренней хэш-таблицы QHash для экономии памяти.

Единственная цель этой функции — предоставить способ тонкой настройки использования памяти QHash. Как правило, вам вряд ли понадобится вызывать эту функцию.

См. также reserve() и capacity().

void QHash::swap(QHash &other)

Меняет местами хеш other с этим хешем. Эта операция очень быстрая и никогда не терпит неудачу.

Эта функция была добавлена в Qt 4.8.

T QHash::take(const Key &key)

Удаляет элемент с ключом из хеша и возвращает ассоциированное с ним значение.

Если элемент не существует в хеше, функция просто возвращает значение, созданное по умолчанию. Если в хеше существует несколько элементов с ключом, удаляется только последний добавленный.

Если вам не нужно использовать возвращаемое значение, то remove() более эффективен.

См. также remove().

QList<Key> QHash::uniqueKeys() const

Возвращает список, содержащий все ключи в карте. Ключи, которые встречаются несколько раз в карте (потому что элементы были вставлены с помощью insertMulti(), или использовалась функция unite()), встречаются только один раз в возвращаемом списке.

Эта функция была добавлена в Qt 4.2.

См. также keys() и values().

QHash &QHash::unite(const QHash &other)

Вставляет все элементы из хеша other в этот хеш. Если ключ присутствует в обоих хешах, полученный хеш будет содержать этот ключ несколько раз.

См. также insertMulti().

const T QHash::value(const Key &key) const

Возвращает значение, связанное с ключом.

Если хеш не содержит элемента с ключом, функция возвращает значение, созданное по умолчанию. Если в хеше существует несколько элементов с ключом, возвращается значение последнего вставленного элемента.

См. также key(), values(), contains(), и operator[]().

const T QHash::value(const Key &key, const T &defaultValue) const

Это перегруженная функция.

Если в хеше нет элемента с заданным ключом, функция возвращает defaultValue.

QList<T> QHash::values() const

Возвращает список, содержащий все значения в хеше в произвольном порядке. Если ключ связан с несколькими значениями, все они будут в списке, а не только последне вставленный.

Порядок гарантированно совпадает с порядком, используемым функцией keys().

См. также keys() и value().

QList<T> QHash::values(const Key &key) const

Это перегруженная функция.

Возвращает список всех значений, связанных с ключом, от последнего вставленного до первого.

См. также count() и insertMulti().

bool QHash::operator!=(const QHash &other) const

Возвращает true, если other не равно этому хешу; в противном случае возвращает false.

Два хеша считаются равными, если они содержат одинаковые пары (ключ, значение).

Для этой функции тип значения должен реализовывать operator==().

См. также operator==().

QHash &QHash::operator=(const QHash &other)

Присваивает other этому хешу и возвращает ссылку на этот хеш.

QHash &QHash::operator=(QHash &&other)

Перемещает присваивание other этому экземпляру QHash.

Эта функция была добавлена в Qt 5.2.

bool QHash::operator==(const QHash &other) const

Возвращает true, если other равен этому хешу; в противном случае возвращает false.

Два хеша считаются равными, если они содержат одинаковые пары (ключ, значение).

Для этой функции тип значения должен реализовывать operator==().

См. также operator!=().

T &QHash::operator[](const Key &key)

Возвращает значение, связанное с ключом, как ссылку для изменения.

Если в хеше нет элемента с ключом, функция вставляет в хеш значение, созданное по умолчанию, с этим ключом и возвращает ссылку на него. Если в хеше есть несколько элементов с ключом, эта функция возвращает ссылку на последнее вставленное значение.

См. также insert() и value().

const T QHash::operator[](const Key &key) const

Это перегруженная функция.

То же, что и value().

inline uint qHash(const std::vector<int> &key, uint seed = 0)
{
    if (key.empty())
        return seed;
    else
        return qHashBits(&key.front(), key.size() * sizeof(int), seed);
}

{0, 1, 2}

{1, 2, 0}

inline uint qHash(const std::vector<int> &key, uint seed = 0)
{
    return qHashRange(key.begin(), key.end(), seed);
}

{0, 1, 2}

{1, 2, 0}

inline uint qHash(const std::unordered_set<int> &key, uint seed = 0)
{
    return qHashRangeCommutative(key.begin(), key.end(), seed);
}