首先申明一下，我是菜鸟，真正的菜鸟，不是谦虚。所以很多地方有错误，需要大家指出。我只是为了记录，顺便加深自己的理解，不是为了炫耀什么。

这两天学习使用hash_map，在网上搜索了一下，没搜到详细介绍hash_map工作原理的内容（可能是我的搜索方式有问题），然后就自己复制别人的代码，进行修改后使用。就因为是copy别人的代码，就多了后面这些教训了。。

做实验用的源代码如下：

include "stdafx.h" #include #include #include

using std::vector; using stdext::hash_map;

class hash_wchar_t { public: // 以下两个变量我也不是很明白究竟是干嘛的 static const size_t bucket_size = 4; // 猜测这个变量是初始化hash_map的大小 static const size_t min_buckets = 8; // 猜测这个变量是每次扩充容量的大小 // 以上猜测是根据vector得来的，其实我基本上没使用过STL，只是在C++Primer上看到过，很粗略的看。

size_t operator()(const wchar_t& GBword) const { return GBword%100; // 下面的那个哈希函数算法是我在网上搜索的说是适合汉字使用的。 // 具体适不适合我也不知道，这里测试的时候可以用简单的 // return ((unsigned char)GBword-176)*94 + (unsigned char)(GBword>>8) - 161; }

bool operator()(const wchar_t& s1,const wchar_t& s2) const { // copy别人代码的时候，由于Key类型是char类型字符串，所以是这么写的 // return 0 == strcmp(s1,s2); // 我针对自己使用的Key类型，在修改了参数的形式之后，很天真的就这么使用，这是问题的关键！！ // 写成这种形式，在下面 测试能否找到的时候，始终出问题， // 原因是p指针指向的是一个未初始化的内存区域，所以无法取数据 // 具体原理在代码后面解释 return s1 == s2;

// 最后的正确用法 // return s1 < s2; // 或者 return s2 > s1; } };

int main() { hash_map*,hash_wchar_t> loNameMap; vector* lpoVecUint = NULL; lpoVecUint = new vector; lpoVecUint->push_back(2);

loNameMap[L'C'] = lpoVecUint; loNameMap[L'A'] = lpoVecUint; loNameMap[L'B'] = lpoVecUint;

vector* p = loNameMap[L'A']; // 测试能否找到 std::cout<size()<*> loNameMap; vector\* lpoVecUint = NULL; lpoVecUint = new vector\; lpoVecUint->push_back(2);

loNameMap[L'C'] = lpoVecUint; loNameMap[L'A'] = lpoVecUint; loNameMap[L'B'] = lpoVecUint;

vector* p = loNameMap[L'A']; // 测试能否找到 std::cout<size()<<std::endl; return 1; }

代码部分有很多注释都是为了增加说明，尽量表现出我调试的过程而加上的（这里说一下，其实是在一位大哥的帮助下，我才理解的）。不理解的可以看完下面我对自定义的哈希函数和比较函数的理解之后再看代码部分：（这里说明一下，其实对于上面的hash_map,可以不用自定义哈希函数和比较函数）

首先说自定义的哈希函数，通常都是以Key作为参数，通过哈希函数对key值的一系列计算得出一个哈希值，然后hash_map内部会根据这个哈希值将对应的Key_Value对存放在对应的桶中，也就是说，可以看作哈希值就是这个桶的索引。这就是哈希函数为什么能够使得搜索效率为常数级（注意，是常数级，但是不一定就是1，只是说已经很接近1了）。

然后说关键的地方，就是自定义的那个比较函数（就是上面重载（）时传进去两个参数的那个函数），这里的比较函数，并不是说每次插入，或者使用[]运算符时，都会去调用这个函数和已经存在的元素进行比较（因为如果是的话，凡是牵涉到寻找和插入的操作，都会去调用这个函数了，我之前是以为这个函数是用来判断两个Key_Value对是否相等时调用的函数），而是说，当进行寻找和插入操作时，如果新的Key_Value（后面写成NewValue) 和一个已经存在的Key_Value(后面写成OldValue）的哈希值相同（这就是哈希冲突），根据上面哈希函数的解释，这两个元素就会放置在同一个桶内。也就是说，当NewValue和OldValue的哈希值是一样，hash_map内部就需要去判断，应该把这个NewValue舍去、或者是在这个桶的内部，按照Key从小到达排序或者从大到小排序。这个判断过程，就需要用到这个比较函数了。

这里另起一段说明调用这个比较函数的过程，hash_map每次进入到一个已经存在的桶（因为哈希值已经存在了），就会去这样调用compare_function(OldValue.Key,NewValue.Key),如果这个函数返回true，它就认为OldValue.Key<NewValue.Key,也就是说，这个比较函数，对于hash_map内部来说，是用来判断OldValue.Key和NewValue.Key的大小关系的，当返回true的时候，它就认为OldValue.Key<NewValue.Key，当返回false的时候，为了进一步判断这两个值的关系，再一次这么调用这个函数compare_function(NewValue.Key，OldValue.Key)。如果还是返回false,说明NewValue.Key不小于OldValue.Key，那么就能确定他们的关系肯定是NewValue.Key==OldValue.Key了。这样就不会向这个桶中插入这个NewValue了，如果最后确定的关系是NewValue.Key!=OldValue.Key，那么hash_map内部就会根据调用你的这个比较函数得出来 的结果向这个桶子的合适位置插入这个新的元素。

到这里位置，已经讲述完了hash_map调用这个比较函数的作用了。为了便于理解写成伪代码的形式就是这样的：

if(!compare_function(OldValue.Key,NewValue.Key))

{ 说明 OldValue.Key !< NewValue.Key;继续判断

if(! compare_function(NewValue.Key，OldValue.Key)

{

NewValue.Key !< OldValue.Key,可以确定NewValue.Key ==OldValue.Key；这里就直接返回对OldValue.Value的引用就可以了

}

else

{

确定NewValue.Key < OldValue.Key，接着去和桶内其他的元素去比，最后将这个元素按照桶内从小到大的顺序插入

｝

｝

else

{

确定 OldValue.Key < NewValue.Key; 接着去和桶内其他的元素去比，最后将这个元素按照桶内从小到大的顺序插入

}

上面当OldValue.Key ！= NewValue.Key时，接下来就会再次通过比较函数去寻找一个合适的位置插入，这里的合适的位置，就会因为比较函数的实现逻辑而不同过了，最简单的方式就是与hash_map内部认为这个函数的功能一致，写成return s1s2; 因为你的判断逻辑和哈希函数内部默认的判断逻辑相反了，最后的结果就是哈希函数把桶内的元素从"小“到”大”排列（而事实上是从大到小）. 最后，如果你写成return s1 == s2，那么当只有当s1确实是等于s2的时候才会返回true，也就是说，只有NewValue确实已经存在的时候，hash_map会在第一次调用比较函数的时候就得到s1<s2的结果，最后实际上是将NewValue插入到OldValue中了，并且，如果NewValue != OldValue的时候，是不会插入新的元素的。

如果比较函数中再写一些其他的逻辑的话，根据这个思路去判断，就很容易知道桶内的元素是什么个情况了。

写在最后：从没写过这么详细的文章（我说的是相对自己以前写的），感觉好累啊，不过收获也很多，确实是比写之前更加清楚hash_map的工作机制了。好佩服那些技术大牛们写的技术讲解文章，以后再有机会，我还得继续努力。。

最后的最后，还是希望有错误的地方有人指正出来~~~~~谢谢了

原文链接: https://www.cnblogs.com/monotone/archive/2011/09/24/2770602.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍