Re:Finding unique items: hash vs. sort
by kyllo on Wednesday January 08, 2020 @01:04AM
(#21988772)
It'd be interesting to see how std::map (implemented with a red-black tree) would do on these same benchmarks. A high ratio of inserts to lookups could favor the tree-based map.
[ Parent
| on HN ]
Re:Finding unique items: hash vs. sort
by jonstewart on Wednesday January 08, 2020 @07:48AM
(#21990891)
It’s hard to get slower than std::map and std::set. They combine logarithmic algorithms with nonlocal memory access.
A tree map is O(n*log n) on inserts, though.
For a hash map to be faster, you'd need to trade memory for speed, i.e have significantly more buckets than the expected size. This may however collide with good caching performance which I suspect is what the author observes.