[nostrademons]

This depends a lot on data size & shape. There've been some applications where I benchmarked a std::map (a tree, in practice) against Google'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.

One thing often forgotten with hashmaps is that they aren't actually O(1); they'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.

As always, measure before optimizing. YMMV.