QMap vs. QHash: A small benchmark

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.