1）为什么需要hash_map
/* 例如： 我要记录一个人名和相应的存储，而且随时增加，要快速查找和修改： 岳不群－华山派掌门人，人称君子剑 张三丰－武当掌门人，太极拳创始人 东方不败－第一高手，葵花宝典 【注】如果你使用STL 的map容器，你可以非常方便的实现这个功能，而不用关心其细节。 */ #include <map> #include <string> using namespace std; ... map<string, string> namemap; //增加 namemap["岳不群"]="华山派掌门人，人称君子剑"; namemap["张三丰"]="武当掌门人，太极拳创始人"; namemap["东方不败"]="第一高手，葵花宝典"; ... //查找 if(namemap.find("岳不群") != namemap.end()){ ... }上述程序用map去保存数据时特别效率，但是存在下面的问题： 一旦我门需要在大的数据库中频繁进行搜索时，时间复杂度大导致效率低下，因此引出hash_map！ 【先介绍下为什么引出hash_map】 hash_map基于hash table（哈希表）。 哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。
1、hash_map和map的区别在哪里？ （1）构造函数:hash_map需要hash函数，等于函数；map只需要比较函数(小于函数). （2）存储结构（底层数据结构不同）:hash_map采用hash表存储，map一般采用红黑树(RB Tree)实现。 （3）map的优点：可以自动按照Key值进行排序；hash_map优点在于它各项操作的平均时间复杂度接近常数，即O(1). （4）map属于STL标准的一部分，而hash_map则不是。 2、什么时候需要用hash_map，什么时候需要用map? （1）总体来说，hash_map 查找速度会比map快，而且查找速度基本和数据量大小，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小，hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。 （2）但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash_map可能会让你陷入尴尬，特别是当你的hash_map对象特别多时，你就更无法控制了，而且hash_map的构造速度较慢。 【总结】现在知道如何选择了吗？权衡三个因素: 查找速度, 数据量, 内存使用。 3、 如何用hash_map替换程序中已有的map容器？ 这个很容易，但需要你有良好的编程风格。建议你尽量使用typedef来定义你的类型： typedef map
