算法导论（四）——哈希表&平摊分析
算法导论（四）——哈希表&平摊分析
1. 背景: symbol-table problem(tableS holding n records)，执行操作插入，删除，搜素。
要使在列表中查找元素的效率达到Θ(1)【给定一个关键字Key（整数）,通过一个定义好的散列函数，可以计算出数据存放的索引位置，这样免去遍历】
若直接映射，则占用的存储空间太大。
2. 哈希表:压缩存储空间。
重点问题：collision (link records in same slot into list)
3. ①选择哈希（散列）函数：（产生的键值要尽可能的均匀，函数本身不能太复杂）
i．除法散列：h(k)=k mod m。通常m是与2的整数幂不太接近的质数。（不能被小于20的数整除的质数）
ii．乘法散列：h(k) = m(kA mod 1)关键字k乘上常数A（0<A<1），并抽取小数部分。再用m乘以这个值，再取结果的底。
iii．全域散列：随机地选择散列函数，使之独立与要存储的关键字
选择一个足够大的质数p，使得每一个可能的关键字都落在0到p-1的范围内。设Zp表示集合{0, 1, …, p-1}，Zp*表示集合{1, 2, …, p-1}。对于任何a∈Zp*和任何b∈Zp，定义散列函数ha,b= ((ak+b) mod p) mod m；其中a,b是满足自己集合的随机数；
iv．完全散列（在查找时，最坏情况内存访问次数为O(1)）
当关键字集合是静态（一旦各关键字存入表中后，该集合就不再变化）时，这种最坏情况的性能是可以达到的。
实现：两级散列，其中每级上采用的都是全域散列。每一个（有元素的）槽里都维护着一张散列表，该表的大小为槽中元素数的平方.
每个槽都使用不同的散列函数: h(k) = ((ak+b) mod p) mod m中选择不同的a值和b值，但所有槽共用一个p值如101。每个槽中的（二级）散列函数可以保证不发生碰撞情况。当第一级散列表的槽的数量和元素数量相同时(m=n)，所有的二级散列表的大小的总量的期望值会小于2n，即Ө(n)。
分类:
简单均匀哈希【每个键等可能的映射到槽中；键之间相互独立】
全域哈希【随机选择哈希函数，与键值相独立，使两个哈希函数值相等的概率不超过1/m (m个槽中随机选择一个的概率)——全域法】
完全哈希【给出n个关键字，构造一个静态哈希表（m），在最坏的情况下搜索元素的耗时为O(1)】
②解决碰撞问题
i链表法：每一次碰撞都添加一个链表（会增加哈希表的大小）。在最坏的情况下，那就是所有的h（k）都指向了同一个槽，那么哈希表实际上就是一个链表，在链表中查询一个值的时间复杂度是θ（n），在最好的情况下，没有发生碰撞那么时间为θ（1）。定义α=n/m为哈希表的装载因子，一次成功的搜索平均用时θ（1+α/2）1表示计算H的时间，α/2表示在链表中所用的平均时间，所以如果n=O（m）那么α就是常数，在这个哈希表中搜索的时间就为θ（1），同时，考虑平均情况下的最坏情况的搜索，时间为θ（1+α）
从平均上看，使用链表时检查的节点数比使用线性和随机探查时要少。
改进：增加尾节点（无穷大，用<limit.h>中的INT_MAX），省去对空指针的检验操作。
ii开放寻址法：在产生冲突的情况下，在hashtable中寻找其他空闲的槽位插入
开放寻址的效率：对于一个开放寻址的哈希表，α=n/m<1，那么一次不成功搜索的预期探寻次数为1/(1-α)。由此可见，如果α=50%那么预期探寻次数为2，如果α=90%，预期探寻次数将会显著升高到10，因此在这种策略下，α的大小至关重要，在工程上某些采用此策略的哈希表会强制α小于75%，如果超过这个值会自动扩充哈希表。
——>线性探查 h(k,i)=(h'(k)+i) mod m, i = 0,1,...,m-1
【存在着一次群集问题。当一个空槽前有i个满的槽时，该空槽下一个将被占用的概率是(i+1)/m。连续被占用的槽就会变得越来越长，平均查询时间也会越来越大】；
——>非线性（二次探查） h(k,i)=(h'(k)+c₁i+c₂i²) mod m , i = 0,1,...,m-1
【为了能够充分利用散列表，c₁，c₂和m的值要受到限制。此外，如果两个关键字的初始探查位置相同，那么它们的探查序列也是相同的。这一性质可导致一种轻度的群集，称为二次群集。】
——>双重哈希；h(k,i)=(h₁(k)+ih₂(k)) mod m, i = 0,1,...,m-1
【用于开放寻址法的最好方法之一，因为它所产生的排列具有随机选择队列的许多特性。后续的探查位置是前一个位置加上偏移量h₂(k)模m。探查序列以两种不同方式依赖于关键字k，因为初始探查位置、偏移量或者两则都可能发生变化】
——>伪随机序列探寻
h(k,i)=(h₁(k)+Random(i))mod m,Random(i)是随机整数，大小属于集合{0，1,2，...，m-1}
不用随机探查的原因：1.计算随机数代价大 2.随机探查使用随机访视搜索散列表，高速缓存使运行时间增大，尽管查看的桶数（冲撞次数）比现行探查少，但实际运行时间大，除非装载因子接近1.
4 再散列问题
散列表快满时，创建另外一个散列表，使得新的散列表的长度是当前散列表的2倍多一些，重新计算各个元素的hash值，插入到新的散列表中。
（1）当散列表将快要满了，给定一个范围，例如散列被中已经被用到了80%，这个时候进行再散列。
（2）当插入一个新元素失败时候（相同关键字失败除外），进行再散列。
（3）当插入一个新元素产生冲突次数过多时，进行再散列。
（4）对于链表法，根据装载因子（已存放n个元素的、具有m个槽位的散列表T，装载因子α=n/m）进行判断，当装载因子达到一定的阈值时候，进行再散列。
参考：http://www.guokr.com/blog/483397/
http://www.cnblogs.com/zhoutaotao/p/4067749.html
平摊分析：
VS 平均情况分析: 平均分析是平均所有的输入，比如，INSERTION SORT算法对于所有可能的输入在平均情况下表现性能不错就算它在某些输入下表现性能是非常差的。而平摊分析是平均操作，比如，TABLEINSERTION算法在所有的操作上平均表现性能很好尽管一些操作非常耗时，概率是没有被包含进来的，并且保证在最坏情况下每一个操作的平均性能。因此n个元素插入的平摊代价（单次插入）为O(1)
【参考：http://blog.csdn.net/ying_xu/article/details/51433497】
对算法复杂度的另一种分析。尽管一个或几个操作比较耗时，但是它们的代价被匀摊，使得平均代价仍较小。本质上，平摊分析就是在最坏的场景下，对于一连串操作给出一个更加严格约束的一种策略。它不涉及概率，并且保证在最坏情况下每一个操作的平均性能。有三类比较常见的平摊分析：
①聚集分析：证明对所有的n，由n个操作所构成的序列的总时间在最坏情况下为T(n)，每一个操作的平均成本或者均摊成本是T(n)/n；比如栈的操作，对于一个空栈的入栈和出栈的操作。【一般不采用】
（以下两种方法则是对特定的操作分配特定的平摊代价。平摊代价是实际代价的上界）
②记账方法：当一个操作的平摊代价超过了它的实际代价时，两者的差值就被当作存款，并赋予数据结构中的一些特定对象，可以用来补偿那些平摊代价低于其实际代价的操作。注意：总存款不能是负的。比如，二进制计数器:通过二进制触发器计算一系列数字
③势能方法：将存款总体上表示成一种“势能”或“势”，它在需要时可以释放出来，以支付后面的操作。势是与整个数据结构而不是其中的个别对象发生联系的。比如，动态表，可以动态改变大小的连续存储数组。
例子:分析哈希表需要多大时(insert, doubling)
表的扩增: 使用动态表，思想为vector扩展容量的方式，空间满时重新分配两倍当前大小的空间，并移动元素，释放旧的空间。
表的搜索: 收缩则是当删除一个后，元素个数小于表大小的1/4，而不是1/2时才收缩表。因为如果以1/2，则如果再立即插入，则会由扩增，从而增大开销。
平摊分析对于有实时需求的场合不太适合。(实时操作系统必须及时响应所要求的任务，在限定时间内完成任务。非实时的操作系统，多时间不是很敏感，对所要求的任务只是会保证完成，但在什么时候完成，或用多长的时间完成就不一定了。)