Maybe it's beacause std::map tree nodes don't get reallocated while unordered_map hash buckets do ?
Maybe it's beacause std::map tree nodes don't get reallocated while unordered_map hash buckets do ?
Suppose you have two threads doing writes at a rate of r per second. Suppose that it takes time t to do an operation. Suppose that concurrent operations have a probability p of crashing. What rate do crashes happen at?
Well, the one thread spends time t * r per second in the operation. The other spends the same. So you spend time (r * t)^2 per second with concurrent accesses, and crashes happen at a rate p * (r * t)^2.
Now let's look at the normal case for a hash insert. t is small and constant in the size of the collection. p is proportional to 1/n. And therefore collisions happen at a rate of O((r * t)^2 / n).
Now let's think about the red-black tree. Exact numbers are calculated. While the writing part is at most O(log(n)). But on average you spend time O(log(n)) finding where to write, and only write O(1) nodes. Think half the time you only write once, 1/4 of the time you write once, rebalance once. 1/8 of the time you write once and rebalance twice. The result is complicated to analyze, but it works out as worse than the regular hash operation by a constant factor. So crashes happen at a rate O((r * t)^2 / n) with worse constants.
Now let's look at the resize operation. This works very differently. The first thread encounters resize every n operations, for a rate r/n. A resize takes time O(t * n). If any write comes in during that resize, the other thread will also do a resize, and they will crash. So the odds that we crash is the time of the operation, times the rate at which writes come, which is O(r * t * n). Multiplying this by the rate we get a probability of O(r/n * r * t * n) = O(r^2 * t).
The previous equation was smaller by a factor of t/n. But remember, t is a very small time (operations are fast) and n tends to be reasonably large (the size of the collection). The result is that race conditions happen dramatically more often for resizes of hashes than any other operation.