According to Herb Sutter the name `hash_map` (or `hashmap`) had already been taken by some C++ standard library implementation that shipped a class with this name in the std namespace: http://www.gotw.ca/publications/mill20.htm
if only the language had a way of putting names in some different area where they wont conflict with each other...
they could have done something like create a new namespace: std::maps, and then have std::maps::tree_map, std::maps::hash_map, or something to that effect, and use std::maps::tree_map as the implementation for std::map for backwards compatibility.
instead they chose to name something by what it isn't.