Question about QMultiHash:

Volker D

Hallo,

referring to https://doc.qt.io/qt-6/qmultihash.html

Quote: "Unlike QMultiMap, QMultiHash does not provide and ordering of
the inserted items. The only guarantee is that items that share the
same key will appear consecutively, from the most recently to the
least recently inserted value."

and Quote: "A more efficient approach is to call find() to get the
STL-style iterator for the first item with a key and iterate from
there:

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

"

So if the items are "consecutively", isn't it much faster this way: (or
are there still items with other keys between?)

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

If i am not missing items by that, the documention should be updated.

Best Regards
Volker

Christian Ehrlicher

Can you please format your code - currently it's unreadable.
From a first sight I don't see a difference between the first and second code piece.

Volker D

Ohh.. Sorry. Fixed.
Maybe it doesn't work like this, since there might be keys with the same hash and there are in between?
In that case the "consecutive" word is a bit confusing in the documentation and in that case i ask myself if there isn't a way to get fast a better end. Something like:

QMultiHash<QString, int>::iterator iend = hash.findNextWithOtherHashAfter("plenty");

Christian Ehrlicher

I still see no difference between the first and the second code piece - it does exactly the same.

You can't get fast to the end since there is a 'bucket' (container) for every key / the calculated hash with all the elements. So the lookup for the items with the same key is O(n) which is why you should a) avoid key collisions / use a good hash functions and b) don't add too much items with the same key when you need fast lookup of a single value.

Volker D

hmmm... If it will give the same results, then my variant will be faster, since it doesn't run to the end.

But i fear my variant is wrong, since the items are not consecutive if 2 >different< keys produce the same hash. In that case the word "consecutive" in the documentation is wrong.

Christian Ehrlicher

@Volker-D said in Question about QMultiHash::

then my variant will be faster, since it doesn't run to the end.

Again: the two code pieces are exactly the same

Volker D

Ahh... Sorry. I got it now. I was wrong. Thank you very much.