STL关联式容器之散列表——hashtable

以散列表为基础的关联式容器深受人们的喜欢，虽然它们目前还不是STL的标准，但是SGI的STL已经包含了这些内容。

前面学习的关联式容器都是基于红黑树这样一种二叉搜索树，也正因为这样，如果要求搜索时间具有对数平均时间，那么需要数据有足够的随机性。而哈希表这种数据结构，在插入、删除、搜索等操作也具有“常数平均时间”的表现，而这种表现是以统计为基础的，不需要依赖数据输入的随机性。

相信大家对散列函数是比较熟悉的，它的作用是将使用某种函数将大数映射到小数空间。常见的散列函数是取模法。

使用散列函数，可能会将不同的元素 映射到相同的位置上，因此就引发了所谓的碰撞问题。解决碰撞问题的经典方法有：线性探测、二次探测、开链等。现在我们一一来了解一下这些方法

1、线性探测

负载系数：元素个数除以表格大小，除非采用开链，否则负载系数永远在0-1之间。

线性探测的插入：如计算出的这个位置上有元素，那么循序往下找，知道一个空位置，如果表格到底了，那么就绕到头部继续查找。

线性探测的搜索：和插入操作一样，当遇到空位置还未找到的话，则查找失败。

删除：删除稍微复杂一点，采用惰性删除，即只标记删除符号，实际删除操作则等待表格重新整理（rehashing）再进行——原因就是因为每个元素不仅表述他自己，他也关系到其他元素的排列。

线性探测最坏情况下是线性巡防整个表格，平均情况下为半个表格。

线性探测中的主集团（primary cluster）问题：平均插入成本的成长幅度，远高于负载系数的成长幅度。即此时表格有大团用过的位置，插入操作有可能在主集团形成的泥泞中爬行，直至最后找到空位置，但同时用助长了主集团的泥泞面积。

2、二次探测

二次弹出的提出主要是为了解决主集团问题。具体操作是这样的：

如果此时用散列函数计算出的位置为H，那么以后尝试的位置分别为H+1^2, H+2^2, H+3^2。。。取代线性探测的

H+1，H+2，。。。

那么我们可能会产生一些疑问。

（1）线性探测每次探测的都必然是一个不同的位置，二次探测法是否能保证如此？二次探测法是否能保证如果表格中没有X，那么我们插入X一定能够成功。

（2）执行效率是否很低？

（3）表格是否能动态生长？

幸运的是，我们我们保证表格大小为质数，并且负载系数用于在0.5之下，也就是如果大于0.5就重新配置表格，那么就可以确定没插入一个元素所需要的弹出次数不多于2。具体证明希望和广大博友共同探讨，因为我现在也没有证明出来。

二次探测可以消除主集团问题，却可能造成次集团：即两个元素经散列函数计算出来的位置若相同，则插入时所探测的位置也相同，形成某种浪费。

3、开链法

SGI的STL中的哈希表采用的就是开链法。

具体代码实现强烈推荐看完源码之后用自己熟悉的语言写一个简单的但完整的哈希表。