Simple answer: Use tree if you need range access or to get elements ordered by key, and use hash otherwise. More nuance: - hashmap may be resized if it's over

Simple answer: Use tree if you need range access or to get elements ordered by key, and use hash otherwise. More nuance: - hashmap may be resized if it's over capacity, the resize may cause a latency spike. - hashmap is essentially a single random memory access, tree is a couple of accesses but they are not random - tree is a bit like a sorted array with fast inserts/deletes. Some trees, like leveldb, are in fact sorted arrays (plus some tricks, of course) - if you use b-tree, you are more memory-efficient (but less cpu efficient), and access to nearby elements is almost free. That's why b-trees are used to store data in a permanent memory - there are many other tree variants, each of them with different trade-off