Contention is much worse on balanced tree than on hash table because at a minimum hand-over-hand locking is required, and many threads will have to traverse the same nodes to find a certain node in the tree.

Well put, @tonycai. It seems like hash tables basically always perform better than balanced tress. Definitely outside the scope of this course, but when is it ever better to use a balanced tree set/map instead of a hash set/map? Every CS course seems to treat both but I've never heard a good argument for using the tree approach.

@rthomp I think the tree set / map has to do with the red black tree implementations of ordered set - map.

@rthomp, just a guess but perhaps the cost of accessing a tree map is lower when (complexity of key1 < key2) * (depth of tree) is less than (complexity of hash function) ... I think a tree map doesn't need a hash function.