jjh42

If you want different threads to see the same data structure then I think you would also need a mechanism to prevent multiple threads modifying the same node and clobbering each other's changes.

Fortunately, the internet is large and adds a huge number of new domains daily such that whitelisting is so disruptive to everyday browsing it's rather difficult (e.g. Amazon cloud front CDN makes new domains with one click and you couldn't block the base domain with breaking several major websites)

For insertions and lookup it is probably hard to find a situation (for large n hashes are asymptotically superior).

Trees provide some other nice properties such as maintaining an ordering (so it's fast to get the smallest argument or interate of the elements in numerical order) and always perform at the asymptotic time cost (a dynamic hash table occasionally takes O(n) when the table is resized so it might not be a good fit in a realtime situation)

Fixed. I'd like to say it was a subtle implication that it contains wisdom from the future ... but actually it was just me being boneheaded.

I only benchmarked and considered the single-threaded case. Multithreading is a whole new can of worms.

(top article author). I wasn't aware of that, it looks like they come to similar conclusions "B-trees are widely known as data structures for secondary storage, because they keep disk seeks to a minimum. For an in-memory data structure, the same property yields a performance boost by keeping cache-line misses to a minimum. C++ B-tree containers make better use of the cache by performing multiple key-comparisons per node when searching the tree. Although B-tree algorithms are more complex, compared with the Red-Black tree algorithms, the improvement in cache behavior may account for a significant speedup in accessing large containers."