最根本的区别为底层的实现机制不同，map底层实现为红黑时，hash_map为hash表，所以就有一些其他方面的不同：
1）map存储的时候为排好序的，所以输出时候也是排序的。而hash_map不是的。
2）map具有稳定性，底层存储为树，这种算法差不多相当与list线性容器的折半查找的效率一样，都是O (log2N)。而hash_map使用hash表来排列配对，hash表是使用关键字来计算表位置。当这个表的大小合适，并且计算算法合适的情况下，hash表的算法复杂度为O(1)的，但是这是理想的情况下的，如果hash表的关键字计算与表位置存在冲突，那么最坏的复杂度为O(n)。 map在一次查找中，你可以断定它最坏的情况下其复杂度不会超过O(log2N)。而hash表就不一样，是O(1)，还是O(N)，或者在其之间，你并不能把握。

我觉得如果数量级很小，不到w，那么使用map和hash_map的区别不大，速度，稳定性都相差不大。但是如果数量级很大，就要考虑是要平均效率高，还是稳定性好了，如果用hash_map那么可以自己来根据经验来设定hash函数优化速度。而如果算法对稳定性要求高的话，首选map。

不过gnu hash_map和c++ stl的api不兼容，c++ tr1(C++ Technical Report1)作为标准的扩展，实现了hash map,提供了和stl兼容一致的api,称为unorder_map.在头文件 <tr1/unordered_map>中。另外c++ tr1还提供了正则表达式、智能指针、hash table、 随机数生成器的功能。
Linux 下的hash_map

#include <iostream>
#include <string>
#include <tr1/unordered_map>
using namespace std;

int main(){
 typedef std::tr1::unordered_map<int,string> hash_map;
 hash_map hm;
 hm.insert(std::pair<int,std::string>(0,"Hello"));
 hm[1] = "World";
 for(hash_map::const_iterator it = hm.begin(); it != hm.end(); ++it){
  cout << it->first << "-> " << it->second << endl;
 }
 return 0;
}

参考：
http://blog.csdn.net/skyremember/article/details/2941076
http://fuliang.iteye.com/blog/725055