Класс 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 типы данных ключа и значения должны быть типaми данных, допускающими присваивание. Например, вы не можете хранить QWidget как значение; вместо этого храните QWidget *.

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

Тип ключа QHash имеет дополнительные требования помимо того, что он является типом данных, допускающим присваивание: он должен предоставлять оператор==(), и в пространстве имен типа также должна быть функция 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

Возвращает постоянный итератор в стиле 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

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

QPair<iterator, iterator> QHash::equal_range(const Key &key)

Возвращает пару итераторов, ограничивающих диапазон значений [first, second), хранящихся под ключом key. Если диапазон пуст, оба итератора будут равны end().

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

QPair<const_iterator, const_iterator> QHash::equal_range(const Key &key) const

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

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

iterator QHash::erase(const_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;
    }
}

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

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

iterator QHash::erase(iterator pos)

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

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

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

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

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

key_iterator QHash::keyEnd() 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)

Удаляет элемент с ключом 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.

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

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

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

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

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

QList<T> QHash::values() const

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

Порядок гарантированно будет таким же, как и у keys().

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

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

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

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

См. также 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)

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

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

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

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

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

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

qHash(qMakePair(key.first, key.second), seed);

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