[Development] QHash for Qt 6

[Lars Knoll]

Hi,

I’ve been playing around with QHash during our recent Hackathon at The Qt Company. I started with measuring and comparing our implementation with various others that are out there using the benchmark that’s described here: https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html. 

The result was that QHash has clear weaknesses compared to other implementations. It uses too much memory and certainly isn’t the fastest implementation. But std::unordered_map is just as bad, so there’s no point in using that to implement QHash.

After looking into it and some of the ideas behind googles and tessils spare map implementations, I got an idea how to possibly improve on those and implement a hash table that’s both very fast and greedy on memory. 

The result can be found at https://git.qt.io/laknoll/qt6hash. For now it only implements QHash and not QMultiHash and it’s still lacking some APIs such as emplace(), but it does implement the data structure.

Performance is pretty much on par with the best hash tables I could find out there, memory usage is a few percent higher than the tsl_sparse_map (which is using least memory of them all). You can find some benchmark results in my repository in the results folder.

I’m pretty happy with the results, and would like to move ahead and finish the implementation, so that we get a state of the art hash table implementation for QHash in Qt 6.

Let me know what you think :)

Cheers,
Lars