[Development] QHash for Qt 6

[Philippe]

+10

It's excellent because it behaves very well in multiple scenarios, which
is uncommon for a hash map.
And according to your design, it should perform equally well with very small maps.
And all that under 1000 lines of code, this is brillant (BTW, you need to #include <array> in qthash.h)

Given the fact that maps are used in so many places, this would be a major
addtion to Qt6

Though this is not the same thing, your optimized memory layout design recalls me
the recent ordered map implementation of abseil
https://abseil.io/blog/20190812-btree

Philippe

On Fri, 20 Dec 2019 08:23:34 +0000
Lars Knoll <lars.knoll at qt.io> wrote:

> 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
> 
> _______________________________________________
> Development mailing list
> Development at qt-project.org
> https://lists.qt-project.org/listinfo/development