Est. 2011

QMap vs. QHash: A small benchmark

While working on my Qt developer days 2012 presentation (QtCore in depth), I made a benchmark comparing QMap and QHash. I thought it would be nice to share the results in this short blog entry.

Under The Hood

The Qt 4 containers are well explained by this old Qt Quarterly article.

QHash is implemented using a Hash Table and QMap was implemented using a Skip list in Qt4.

In Qt 5, the implementation of the containers have changed a bit, but the concepts are still the same. Here are the main differences:

  • QVector, QString and QByteArray now share the same implementation ( QArrayData ). The main difference is that there is now an offset which might allow in the future to reference external data.
  • QMap implementation has totally changed. It is no longer a skip list, but a red-black tree.

The Benchmark

The benchmark is simple and is doing lots of look-ups in a loop during one second and count the number of iterations.
It is not really scientific. The goal is only to show the shape of the curves.

The source: benchmark.cc

The Result

Run on my computer, gcc 4.7. Higher is better. The number of element is on a logarithmic scale. For QHash, one should expect it not to change with the number of elements, and for QMap it should be O(log N): a straight line on a logarithmic scale.

Qt 4.8

QMap performs slightly slower than std::map. QMap lookup is faster than in a QHash for less than about 10 elements.

Qt 5

It was a good idea to change from a skip list to a red-black tree. The performance of the Qt containers compared to the STL are about the same. QMap is faster than QHash if there is less than about 20 elements.

If you compare the number between Qt5 and Qt4 you see that Qt5 performs better. That might be related by the changes in QString.

Conclusion

The typical rule is: Use QMap only if you need the items to be sorted or if you know that you always have a very small amount of items in your map.

Woboq is a software company that specializes in development and consulting around Qt and C++. Hire us!

If you like this blog and want to read similar articles, consider subscribing via our RSS feed (Via Google Feedburner, Privacy Policy), by e-mail (Via Google Feedburner, Privacy Policy) or follow us on twitter or add us on G+.

Submit on reddit Submit on reddit Tweet about it Share on Facebook Post on Google+

Article posted by Olivier Goffart on 19 February 2013

Load Comments...
Loading comments embeds an external widget from disqus.com.
Check disqus privacy policy for more information.
Get notified when we post a new interesting article!

Click to subscribe via RSS or e-mail on Google Feedburner. (external service).

Click for the privacy policy of Google Feedburner.
© 2011-2023 Woboq GmbH
Google Analytics Tracking Opt-Out