正在赶一个关于证劵交易的项目，其中用到了很多数据的查找等操作，开始用了map，同事看到后建议我用hash_map，查了查hash_map的内部实现，这里顺带也就写了下来。
hash_map基于hash table（哈希表）。 哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。
其基本原理是：使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash值）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方，称为桶。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。 总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。hash_map，首先分配一大片内存，形成许多桶。是利用hash函数，对key进行映射到不同区域（桶）进行保
比较桶的内部元素是否与key相等，若都不相等，则没有找到。
hash_map中直接地址用hash函数生成，解决冲突，用比较函数解决。这里可以看出，如果每个桶内部只有一个元素，那么查找的时候只有一次比较。当许多桶内没有值时，许多查询就会更快了(指查不到的时候).
由此可见，要实现哈希表, 和用户相关的是：hash函数和比较函数。这两个参数刚好是我们在使用hash_map时需要指定的参数。
- #if defined(__GNUC__)
- #if __GNUC__ < 3 && __GNUC__ >= 2 && __GNUC_MINOR__ >= 95
- #include <hash_map>
- #elif __GNUC__ >= 3
- #include <ext/hash_map>
- using namespace __gnu_cxx;
- #else
- #include <hash_map.h>
- #endif
- #elif defined(__MSVC_VER__)
- #if __MSVC_VER__ >= 7
- #include <hash_map>
- #else
- #error "std::hash_map is not available with this compiler"
- #endif
- #elif defined(__sgi__)
- #include <hash_map>
- #else
- #error "std::hash_map is not available with this compiler"
- #endif
- #include <string>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- struct str_hash{
- size_t operator()(const string& str) const
- {
- return __stl_hash_string(str.c_str());
- }
- };
- struct str_equal{
- bool operator()(const string& s1,const string& s2) const {
- return s1==s2;
- }
- };
-
- int main(int argc, char *argv[])
- {
- hash_map<string,string,str_hash,str_equal> mymap;
- mymap.insert(pair<string,string>("hcq","20"));
- mymap["sgx"]="24";
- mymap["sb"]="23";
- cout<<mymap["sb"]<<endl;
- if(mymap.find("hcq")!=mymap.end())
- cout<<mymap["hcq"]<<endl;
- return 0;
- }
1、构造函数。hash_map需要hash函数，等于函数；map只需要比较函数(小于函数).
2、存储结构。hash_map采用hash表存储，map一般采用红黑树(RB Tree)实现。因此其memory数据结构是不一样的。
总体来说，hash_map 查找速度会比map快，而且查找速度基本和数据数据量大小，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小，hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash_map可能会让你陷入尴尬，特别是当你的hash_map对象特别多时，你就更无法控制了，而且hash_map的构造速度较慢。现在知道如何选择了吗？权衡三个因素: 查找速度, 数据量, 内存使用。
哈哈，不说了，要不让BOSS看到我不干活那就麻烦了……继续工作！！！
本文转自 驿落黄昏 51CTO博客，原文链接：http://blog.51cto.com/yiluohuanghun/1086355，如需转载请自行联系原作者