《STL源码剖析》之hashtable
hashtable即散列表，也叫哈希表，它对元素的插入、删除和访问操作具有常数时间复杂度的表现，这种表现不依赖于输入元素的随机性。
1 哈希函数的作用概述
假如使用哈希存储数据，且该所有的数据是16-bits且不带正负号，范围是0~65535，那么使用一个array就可以满足上述期望。具体操作：
- 首先配置一个array，大小为65536，并把所有元素的值初始化为0；每个元素的值为元素出现的次数。
- 如果插入元素i，那么就执行++A[i]；
- 如果删除元素i，那么就执行--A[i]；
- 如果访问元素i，那么就执行A[i]。
上述操作时间复杂度均为常数时间，这种解法的额外负担是array的空间和初始化时间。且这个解法存在两种问题：
- 如果元素是32-bits，那么array的大小为2的32次方，即4GB，占用空间实在是太大了；
- 如果元素的类型是字符串（或其他）而非整数，将不能作为array的索引。
第一个问题是实实在在存在的问题，难以解决；第二个问题可通过把字符串转换为ASII来解决，但是仍可能会产生巨大的数字，比如"jjhou"的索引是：
这太不切实际了，更长的字符串会导致更大的数字，这就回归到第一个问题：array的大小可能会巨大。
为解决上述array空间巨大的问题，我们使用散列函数把大数映射成小数，把某一元素映射成大小可接受的索引。但是会带来新的问题：冲突！
比如：X为任意整数，tableSize为array的大小，则X%tableSize会得到一个整数，范围在0~tableSize-1，恰可作为array的索引。例如：5%10 == 15%10 == 5，此时，两个数被映射到相同的位置，引发了冲突，也即元素出现了碰撞。
2 如何解决冲突
解决冲突的方法有多种，常见的有线性探测、二次探测（也叫平方探测）及开链法（也叫分离链接法）等。不同做法导致的效率各不相同——与array的填满程度有关。
2-1 线性探测法
我们仍使用hash function计算出某个元素的插入位置，可能出现以下两种情况：
- 该位置空间可用，那么插入即可，over；
- 该位置空间不可用.........疯狂寻找可用位置吧！
针对第二种情况，我们只需循环往下一一寻找，如果到达尾端，那么就绕到头部继续寻找，直到找到一个可用空间为止。只要array足够大，那么总能找到一个安身立命之处，但是寻找的时间复杂度就很难说了，元素的搜寻操作和插入操作道理相同。
下面是一个例子：
使用线性探测法，需要以下假设：
- 表格足够大；
- 元素相互独立，即经hash function计算出来的位置不能相同，否则将引起冲突而进行疯狂搜寻可用位置。
在此假设下，
最坏情况是线性遍历整个array，平均情况是遍历一半array——这和哈希表的常数时间天差地远了，且第二种假设真的太天真...............
此外，线性探测还会导致另外一个问题：
主集团！在上图中，除非新元素经过hash function的计算之后直接落在位置#4~#7，否则#4~#7永远不可能被运用，因为位置#3永远是第一考虑，换句话说，新元素不论是8,9,0,1,2,3中的哪一个，都会落在位置#3上，新元素如果是4或5，或6，或7，才会各自落在位置#4，或#5，或#6，或#7上。这里很清楚的突显一个问题：平均插入成本的成长幅度，远高于
负载系数（元素的个数除以表格的大小，介于0~1）的成长程度，这样的现象在hasing过程中成为主集团。
2-2 二次探测法
二次探测带来的疑问：
- Q1：线性探测每次探测都必然是不同的位置，二次探测能否保证如此？二次探测是否能保证如果表格之中没有X，那么插入X一定能成功?
- Q2：线性探测的元算过程及其简单，二次探测显然复杂的多，这是否会在执行效率上带来太多的负面影响？
- Q3：不论线性探测或二次探测，当负载系数过高时，表格是否能够动态成长？
对于
Q1，
通过把表格的大小设为质数，而且永远保持负载系数在0.5以下（也就是说超过0.5就重新配置并重新整理表格），就可以确定每次插入一个元素所需探测的次数不超过两次。对于
Q2，二次探测通过
数学运算消除耗时的乘法和除法，如下：
因此，如果我们能够以前一个H值，来计算下一个H值，就不需要执行二次方所需的乘法了。肃然还有一个乘法，但那是乘以2，,可通过位移位快速完成；至于mod运算，也可证明并非真有需要（本处略）。对于
Q3，欲扩充表格，首先必须找出下一个新的而且够大（大约两倍）的质数，然后必须考虑重建表格的成本——是的，
不可能原封不动地拷贝而已，我们必须检验旧表格中的每一个元素，计算其在新表格中的位置，然后再插入到新的表格中。
二次探测消除了主集团问题，却带来了
次集团问题！两个元素经hash function计算出来的位置若相同，则插入时所探测的位置也相同，形成某种浪费。次集团可由复散列解决，总体来说二次探测仍然值得投资。
2-3 开链法
能和二次探测分庭抗礼的是开链法，SGI STL的hast table便是采用开链法。这种做法是 在表格（vector）中的每个元素中维护一个list，在链表身上执行元素的插入、搜寻及删除等操作是线性操作，但是如果list足够短，速度还是够快。3 hashtable实现分析
3-1 hashtable桶子与节点
hashtable使用vector作为底层表格，以便于动态扩充，vector中的元素成为桶子，桶子维护linked list，注意该list并不是STL的list或slist，而是自行定义的，如下所示：
template<class Value>
struct __hashtable_node
{
__hashtable_node* next;
Value val;
};
SGI STL以开链法完成的hash table入下图所示：
3-2 hashtable的迭代器
3-3 hashtable的数据结构
3-4 hashtable的构造和内存管理
3-4-1 插入操作（insert）与表格重整（resize）
3-4-2 判断元素的落脚处（btk_num）
3-4-3 复制（copy_from）和整体删除（clear）
——参考《STL源码剖析》
注意！
本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。