容器hashtable(哈希表）：另外一种底层机制

其基本原理是：使用一个下标范围比较大的数组来存储元素。把关键字Key通过一个固定的算法函数即所谓的哈希函数（散列函数）转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的list空间里。也可以简单的理解为，按照关键字key为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方，称为桶。

了避免哈希表太大，需要用到某种映射函数，将大数映射为小数，这种函数称为散列函数hash function。但hash function会带来碰撞问题，即不同的元素被映射到相同位置。

为了解决碰撞问题有三种方法：线性探测、二次探测、开链。

hashtable就是用的开链法。

 

hashtable存取过程

hash_map，首先分配一大片内存，形成许多桶。是利用hash函数，对key进行映射到不同区域（桶）进行保存。其插入过程是：

1.得到key
2.通过hash函数得到hash值
3.得到桶号(一般都为hash值对桶数求模)
4.存放key和value在桶内。
其取值过程是:
1.得到key
2.通过hash函数得到hash值
3.得到桶号(一般都为hash值对桶数求模)
4.比较桶的内部元素是否与key相等，若都不相等，则没有找到。
5.取出相等的记录的value。

原理：

H=hashcode%桶子个数(例子中为0=53%53，2=55%53,2=2%53,2=108%53）

hashcode由函数HashFcn通过key计算

rehashing：当桶内的元素总个数大于桶子个数时，就会使桶子个数增长到其两倍附近的质数，所以桶子数一定比元素个数多。例子中为97，然后所有元素再执行H=hashcode%桶子数。

hashtable的数据结构

Value:结点的实值型别

Key:结点的键值型别

HashFcn：hash function的函数型别，利用key,计算每个元素的编号hashcode 。

H=hashcode%桶子数

 

 

 

解析：

• ExtractKey:从节点中取出键值的方法（函数或仿函数）
• EqualKey:判断键值相同与否的方法（函数或仿函数）
• Alloc:空间配置器，缺省使用std::alloc
• 桶子实际是以vector完成的，以利于动态扩充。
• hashtabe的迭代器：维系着整个“buckets vector”的关系，并记录目前所指的结点
• node*cur;//迭代器目前所指结点
• hashtable*ht;//保持对容器的连接关系（因为可能需要从一个桶子跳到临近的桶子）
• 其前进操作是首先尝试从目前所指的结点出发，前进一个结点，由于结点被安置在list中，所以利用结点的next指针即可轻易达成前进操作。如果目前处于list的尾端，就通过ht指针跳到下一个桶子上，同时cur指向下一个桶子的头部结点。
• hashtable的迭代器没有后退操作，也没有逆向迭代器。
• 桶子维护的linked list(可单向可双向）,并不是标准库中的list,而是自行维护hash table node

例子：