This depends a lot on data size &amp; shape.  There&#x27;ve been some applications where I benchmarked a std::map (a tree, in practice) against Google&#x27;s highly-tuned hashmap for a small (~25-50 item) container and the tree came out ahead.  For such a small data structure, everything fit in L1 cache, and comparisons to follow pointers could usually be resolved by looking at the first word of the key.<p>One thing often forgotten with hashmaps is that they aren&#x27;t actually O(1); they&#x27;re O(k), where k is the length of the key, and often need to examine the entire key to derive a hashcode.  This oftentimes makes them significantly slower than a binary search tree when the size of the key is large compared to the size of the container.<p>As always, measure before optimizing.  YMMV.