Russian Qt Forum

с праздниками всех!

Допустим, что есть хеш QHash<int, int>. В процессе работы с этим хешем заметил, что он размещает свои элементы не в произвольном порядке, как написано в Ассистанте, а в порядке возростания ключей.

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

Чистая случайность. Ключи располагаются не в собстенном порядке (ибо оператора < может даже не быть), а в порядке возрастания qHash( ключ ) % QHash::capacity().

не совсем случайность :) для типов данных размером <= sizeof(uint) функция qHash возвращает значение аргумента :)

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

Друзья!
Мне надо следующее: вытягивать из хеша ключи в порядке возрастания. Для этого я хочу создать дополнительный контейнер QList (вытянуть туда все ключи и отсортировать), а потом, пробегаясь по элементам этого контейнера, доставать их из хеша.
Может есть менее затратный вариант, чем создавать дополнительный контейнер?
Ключей в хеше много (в пределах милиона).

QMap. хранит элементы в порядке возрастания значения ключа.
или я что не так понял?

элементов очень много (около миллиона). На определенном этапе работы программы хеш часто используется для поиска ключей, вставки новых, а в документации написано:
>> QHash provides faster lookups than QMap.
Вот и был выбран QHash.

А результирующая задача то какая? Что с этим сортированым списком потом делать?

Чуть подробнее:
1) есть хеш:
QHash((1, 5)(2, 3)(4, 2)(4, 1)(7, 2)(5, 1))
2) мне надо вытягивать ключи в порядке возрастания и делать некоторые преобразования с другими контейнерами на основе вытянутого ключа и значения.
(на данном этапе это и есть результирующая задача)

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

Офигенно развёрнутое обьяснение задачи. То что вытягивать ключи в опрядке возрастания нужно для того чтобы потом что-то с ними делать и так ясно. Иначе вы бы этим не занимались. Под "задачей" понимается нечто большее. Попробуйте обьяснить копнув на один уровень вглубь. Что именно это за индексы, что физически из себя представляет сортированый список, насколько часто это нужно делать.

разворачиваю постановку задачи :-)

есть следующая основная структура данных:
QHash<int, QHash<int, class T1> > someHash;
надо извлекать значения (value - хеши второго уровня) из каждого ключа первого уровня.

Порядок извлечения value должен основываться на количестве значений (хешей второго уровня). Хеши должны извлекаться в порядке возрастания их количеств для данного ключа :-)

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

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

извините :-)

У меня подозрение что вам здесь нужен не QHash, а специализированный контейнер для таких операций. Или база данных.

если быть более точным, то основная структура выглядит так:
QHash<int, QHash<int, QHash<int, int> > > myHash;

над значениями последнего уровня QHash очень часто производятся преобразования, при этом постоянно надо обращаться к хешам верхних уровней (в зависимости от их количества :-) ).

Значения первых уровней структуры данных периодически удаляются и добавляются, не знаю (не имею опыта работы с базами), будет ли обращение к базе и преобразования в ней настолько быстрыми, как к структуре данных, основанной на хеше?

Dendy, уточните, пожалуйста про специализированный контейнер, как примерно может выглядеть этот класс?

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

Не буду вводить в заблуждение, сам работал достаточно посредственно с чёрно-красными деревьями, погуглите, возможно их алгоритмы именно то что вам нужно. Хотя если у вас миллионы элементов, то это уже задача для базы данных. QHash спроектирован не для этого. Он работает медленно путём прямого перебора или есть память, выделяемую под букеты. Для нескольких элементов (возможно, тысяч) это терпимо. Собственно он предназначен для избавления программиста от геммороя в простых случаях.

про красно-черные деревья почитал в Wikipedia - Red-black tree (http://en.wikipedia.org/wiki/Red-black_tree) интересная идея, но, просветите меня, пожалуйста по такому поводу:

на этой же странице (про красно-черные деревья) нашёл:
>> In the C++ Standard Template Library, the containers std::set<Value> and std::map<Key,Value> are often based on red-black trees
вывод - поиск происходит достаточно быстро (используется же метод красно-черных деревьев!)

В Ассистанте про QMap написано, что поиск ключа медленнее, чем в QHash (для QMap - Average O(log n), к слову, для QHash время поиска - Average O(1) )

выходит, что std::map и QMap имеют разную реализацию, если в случае map (STL) мы получаем быстрый поиск, а в случае QMap - медленный?

---------------------------

про базы подумаю, почитаю еще.

Общее (суммарное) количество элементов в моём случае в пределах одного миллиона. Это означает, что количество всех хешей в основной структуре около миллиона, а я писал только про верхний уровень - извините ошибся. В каждом хеше-значении на первом уровне основной структуры данных (QHash<int, QHash<int, QHash<int, int> > >) как раз будет в пределах 100000 элементов.

Про память особо не заморачиваюсь, пусть ест :-)
почитал в Интернете (http://www.linux.org.ru/jump-message.jsp?msgid=2824630&cid=2828120), народ пишет, что STL-ий контейнер еще хорошо справляется с сотней тысяч объектов, но не больше. Что скажете, будет ли QHash справляться с сотней тысяч объектов так же как и STL контейнер?

Я все это веду к тому, что может, все-таки можно использовать предложенную мною структуру хешей? :-)

Хеш-таблица внутри хеш-таблицы внутри хеш-таблицы уже нездравое решение. Понимаете в чём фишка... Мой опыт программирования показывает, что балансируя на грани "делать как знаю" или "делать по уму" и предпочтя первое - в итоге вы обрастёте свою программу спагетти сомнительного кода. А через время закончится всё это переписыванием "по уму" с тратой драгоценного времени. Если вас не жмёт время - сядьте, осильте SQLite и запихните все своё добро в таблицы.

Dendy, большое спасибо за наводку. Изучаю SQLite.
Пока не почитал про базы, у меня были сомнения относительно скорости доступа к данным в базах.

Есть еще такая штука: http://www.garret.ru/fastdb.html.

cпасибо, почитаю обязательно.

И что, никого не смутило что QHash действительно сортирует значения по ключу?
Хотя в асистанте написано, что сортировки нету!
Я хотел этим воспрользоваться и словил облом. Вот же блин.


Наглая ложь!

хотели воспользоваться отсутствием сортировки в QHash? :)

2 kirill, тогда тролям писать надо!

QHash<QString, int> hash;
for(int i = 0; i < 50; ++i)
	hash.insert(QString::number(i), i);
qDebug() << hash;

Простой пример

В Output будет
s1
s2

Хотя мною задумывалось что будет
s2
s1

2 kirill

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

Вот код:

C++ (Qt)
#include <QHash>
#include <QDebug>
#include <math.h>
 
 
int main( int argc, char ** argv )
{
	QHash<QString,QString> hash;
 
	qDebug() << "Generating...";
	for ( int i = 0; i < 10; ++i )
	{
		int r = rand();
 
		QString key = QString( "Key: %1" ).arg( r );
		QString value = QString( "Value: %1" ).arg( r );
 
		hash[ key ] = value;
 
		qDebug() << "key:" << key << "  value:" << value;
	}
 
 	qDebug() << "Iterating...";
	for ( QHashIterator<QString,QString> it( hash ); it.hasNext(); )
	{
		it.next();
		QString key = it.key();
		QString value = it.value();
 
		qDebug() << "key:" << key << "  value:" << value;
	}
 
	return 0;
}
 

Вот вывод:

Естественно последовательность случайная. Почему - читайте тему с начала.

Понял, спасибо за разъяснения.
А нет ли какого нибудь контейнера, который бы хранил значения в том порядке, в котором заносишь?

Внезапно! QList

Хотелось бы ассоциативный массив типа QMap, QHash, чтобы удобно было хранить пары ключ/значение.
Задача простая - есть список свойств, на QMap это было бы как QMap<QString, QString> или QVariantMap. Но эти свойства грузятся из xml файла. и отображать их надо в том порядке, как они записаны в файле. Но QMap взялся сортировать значения по ключу, QHash располагает их в произвольном порядке.
хм.. думаю может быть QList<QPair>.

такого контейнера нет и, судя по всему, не будет. сам не раз сталкивался с потребностью в подобном контейнере, сохраняющем последовательность ключей, как QList и в тоже время удобный, как QHash. несколько раз пинал Троллей по этому поводу - ответили, что в ближайшем будущем подобного контейнера не планируется ибо не хотят плодить классы на все случаи жизни; предлагают QList<QPair<..., ...>>

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

Вообще-то сам алгоритм работы hash-а таков, что данные в нём как можно менее упорядочены. :)
Для map (оно упорядоченное дерево) порядок жестко зафиксирован - по возрастанию
Т.е. для сохранения какого-то дополнительного порядка нужно это делать явно.

Ежели не хочется городить свои велосипеды - есть boost.multiindex. :)

Я бя сказал так:
QHash полезен тогда - когда операция сравнения ключей довольно накладная операция а также когда накладно хранение самих ключей.
Простейший случай такого ключа - QString. Т.е. если ключи представляют из себя довольно длинные строки, то накладно и их сравнение и их хранение в контейнере.
В текущей реализации QHash преобразует любой реальный ключ перед использованием во внутренний 32-х разрядный ключик, и именно его он потом и использует. При этом данные хранятся в отсортированном (так или иначе) по внутреннему ключу  виде.
Некоторые целочисленные типы ключа (типа int) транслируются во внутренний ключ без преобразований, поэтому ктото и наблюдает отсортированный список ключей.
Поэтому я не вижу особых преимуществ у QHash<int, XXX> перед QHash<int, XXX>.

terlan
Твой QHash<int, QHash<int, QHash<int, int> > > возможно полезно заменить на QHash<QByteArray, int> и засовывать твои три ключа в этот QByteArray.
Ну или не QByteArray а struct { int x, int y, int z } и соответственно operator==() и global qHash(Key) function для этой структуры.

чего? (с) Мак Сим

Поразительно, я тоже.

Да, кстати, QHash хранит не только огрызки от ключей, а и сами ключи. Но, в случае и Implicitly Shared классами (вроде QString) сами ключи занимают места ровно на один указатель, поэтому некритично.

товарищи, всего-навсего опечатка :)
по-моему имелось в виду
Alex03, спасибо за ликбез. Однако для своей задачи уже выбрал базы данных.

а мне кажется. имелось в виду
:)

Угу.

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

Меня например поразила строчка:
в

Поизучал немного исходники.... (ибо не понял зачем там operator==() для ключа)
Поразился тем что оригинальные ключи тоже хранятся в QHash.... (сэкономить памяти не получатся)
С другой стороны теперь уверен в QHash-e, даже при одних и тех же результатах qHash() для разных ключей всё будет ОК.