倒插入分段哈希算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇倒插入分段哈希算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：
受到孔雀哈希与分段哈希算法的启发，提出了一种新的倒插入分段哈希表。该算法从改变表的操作顺序及修改孔雀哈希数据结构着手，保证了片外访问的平均次数接近于1。分析与实验表明，该算法具有较高的效率，降低了内存开销。
ス丶词：
孔雀哈希;分段哈希;位图数组;布鲁姆过滤器;内存
ブ型挤掷嗪牛 TP309.7; TP311.12
文献标志码：A
英文标题
Inverse insert algorithm based on segment hash
び⑽淖髡呙
TANG Ming1，SHI Changqiong1，2，ZHOU Kaiqing1， ZHANG Dafang2
び⑽牡刂(
1.College of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha Hunan 410114, China;
2.School of Computer and Communication, Hunan University, Changsha Hunan 410082,China
英文摘要
)
Abstract:
A segment hash with inversed insertion based on peacock hash and segment hash was proposed. This algorithm ensured the average times of offchip access close to 1 through changing the operating sequence and data structure of peacock hash. The analysis and experimental results show that the algorithm has high efficiency and can reduce the memory overhead.
英文关键词
Key words:
peacock hash; segment hash; bitmap array; Bloom Filter (BF); memory
0 引言
通常情况下，通过改进哈希表来实现更高的查找性能会要求有更大的片内存储。因此，如何在高速操作的哈希表中提出减少片内存储的方法具有重要的理论意义和应用价值。文献［1］提出了孔雀哈希算法，减少了冲突及片外访问次数，引入的布鲁姆过滤器(Bloom Filter, BF)能判断关键字存在，但具有一定的假阳性并内存开销大；文献［2］采用位图数组来标识哈希表中当前位置是否被占用，该方法简单且占用内存小，但对于关键值是否存在无法辨别。本文通过分析Bloom Filter与位图数组各自的优缺点，提出了一种新的倒插入分段哈希表，使其能够提供更加简捷和快速的运算。
1 哈希表
哈希表能够对键值进行散列、快速查找、删除以及插入等操作。下面分别介绍分段哈希表及孔雀哈希表。
1.1 分段哈希表
分段哈希［3］ 采用将哈希表分成多级子表和一个主表，并使用多个哈希函数进行散列的策略来解决冲突。相对于链式哈希及其他哈希的冲突策略，分段哈希表的提出虽然能够减少片外访问的次数，就本身数据结构而言，无法很好地解决冲突，导致键值的查找时间较长。
1.2 孔雀哈希算法
孔雀哈希表在分段哈希表的基础上对数据结构进行了修改，在每一个表前都添加了Bloom Filter。虽然在访问外存次数上大大降低，却带来了内存开销问题。另外，孔雀哈希表采取了一种负载平衡的策略，使各表间的散列位子形成了一种链式关系，但在删除过程中，为了保存这种关系，对于表的优先权而言，表的优先权低的键值需要向优先权高的表中一一移动，在删除操作时也会在时间上带来一定的开销且复杂。
2 倒插入分段哈希算法
在分段哈希和孔雀哈希思想的基础上，本文提出倒插入分段哈希表。通过与桶深度为1的孔雀哈希进行对比，改进后的哈希表兼容了内存开销小、片外访问次数低的特点。
2.1 算法思想
本算法的改进主要体现在将主表的Bloom Filter去掉而改成一个位图数组,大大减少了内存的开销，在每个子表前都添加一个位图数组。在搜索键值的策略上，先探测位图数组中的相应位置已经存放了关键值，再在Bloom Filter中进行查找，但由于Bloom Filter本身存在假阳性，所以在经过Bloom Filter查找之后，再访问片外进行键值查找。在Bloom Filter与位图数组的共同作用下，根据上述搜索键值策略能够保证访问外存次数为1。
插入键值时，采取的方式是从子表往主表的顺序进行插入，当碰见冲突时，则往优先权更高的子表进行插入，直到主表也发生冲突，则放入溢出表。查找、删除键值的策略也进行从后往前的查找、删除策略。
2.2 改进哈希表的数据结构
程序前
class HashTable
{
private:
deque * subtable_set;//子表集合
}
class SubTable
{
public:
unsigned int table_index;//表的序列
int *BitArray;//位图数组
Bloomfilter Cbf;//布鲁姆过滤器
deque * bucket_set;//桶队列
}
程序后
┆扑慊应用 ┑31卷
2.3 算法描述
下面从插入、查找、删除3个操作来进行算法描述。
2.3.1 插入操作
1)选择哈希子表，在子表中进行哈希散列，当位图中的位子没有被占用，则进入2)；否则重复1)直到所有的子表都被从后到前地探测过，再进入3)。
2)插入目标桶，插入Bloom Filter中，设置位图数组标志，然后返回。
3)在主表中进行哈希散列,找出相应的桶,如果位图数组的位置没有被占有，则插入桶中，设置表前位图数组的相应位子，然后返回；否则进入4)。
4)进行桶中匹配，如果没有匹配成功，则冲突放入溢出表；如果位图数组的位置没有被占有则插入桶中，设置位图数组的相应位置后返回；否则将键值插入到溢出表中。
2.3.2 查找操作
1)从子表开始按照优先级从后往前查找，如果子表前的Bloom Filter中不存在当前键值，重复1)直到所有子表都进行查找完毕，进入2);否则在当前子表中进行散列，判断位图数组的位置没有被占有，则返回1)，否则进行桶的访问。
2)在主表中进行哈希散列,如果位图数组的位置没有被占有则返回；否则,找出相应的桶并进行查找，如果不匹配时，进入3)。
3)在溢出表中进行查找。
2.3.3 删除操作
1)进行查找操作，如果查找到键值存在于桶中，则进入操作2)，反之不进行操作。
2)首先删除Bloom Filter中的键值，然后删除位图数组中的占用状态，将1改为0。进入操作3)。
3)将存在桶中的键值删除，退出删除操作。
2.4 改进哈希表的性能分析
为了说明改进哈希表的有效性，本文从时间性能和空间性能两个方面来进行分析。
2.4.1 时间性能分析
由于主表中存放了大部分键值，使得孔雀哈希算法的片外访问平均次数≤2［1］。
传统的操作都是按照从主表到子表的顺序进行，使得主表必定被访问，产生的冲突数增加，还需要在子表中继续进行查找。而改进的哈希算法将传统的操作顺序改变，仅当键值存在于子表的Bloom Filter中，才会去访问外存进行精确匹配，使不存在于子表中的键值直接在主表中查找，通过这样的查找策略可以保证片外访问的平均次数接近于1。
具体的片外访问平均次数可以通过式（1）来估算。
W梦蚀问=1+P1×2+…+Pi×(i+1)В1）
其中Pi表示了i+1次访问的键值在总键值中所占的比例。И
由于Bloom Filter存在假阳性，所以PiУ募扑闳缡剑2）。
Pi=(1－Pi－1)×(1－P┆false)В2）
其中:P┆false是Bloom Filter的假阳性概率［4］，其值小于0.1%。
Bloom Filter的假阳性保证了以下现象的必然性：在子表Bloom Filter中存在的键值极少可能在其他优先权高的表中存在，即片外访问平均次数大于2的键值比例维持低的水平，假如此比例为10%，则由式（1）可知，W梦蚀问约为1.2。オ
综合上述公式可以估算出片外访问平均次数会远远小于2。
2.4.2 空间性能分析
空间复杂度主要指片上存储空间，为了方便运算，本文设定空间大小单位为字节。tП硎竟希表总长度，优先权高的表长为低的2次幂。
分段哈希的片上存储空间大小为：
M侄=t×lb n8(3)
孔雀哈希在存储桶前添加了一个Bloom Filter使得额外开销增加，Bloom Filter在空间上需要哈希表空间的1/4［5］,则片上存储空间大小为：
M兹=M兹+M兹4=5M侄4(4)
改进后的哈希在主表的存储桶前将Bloom Filter换成了位图数组，在子表数据结构保持与孔雀哈希不变，Bloom Filter带来的总内存开销（由于主表与子表的关系为幂次关系）为M兹/2,存储空间大小为：
M慕=M兹2+t8=5M侄8+t8(5)
由式(3)~(5)可知，在t相同的情况下，在空间需求方面改进哈希仍优于孔雀哈希表。
综上所述，改进的哈希算法确实能够在节省空间的前提下来优化外存访问。
3 实验仿真及结果分析
3.1 时间性能仿真
实验中总共随机产生50组数据，每组数据有242个关键字。总共有4级哈希表，其中最大的哈希表容量为128个关键字并各级哈希表的容量呈2的幂次递减，故最小一级的哈希表容量为16个关键字。此外，还存在一个溢出表。
实验采用VC++ 6.0平台进行仿真，具体仿真步骤如下：
1)将孔雀哈希算法及改进算法转化为程序；
2)将50组随机产生的数据分别输入程序；
3)在算法的程序中设置计数器，用来记录产生冲突数及片外访问次数。
此外，在查找键值的过程中，当程序处于访问位图数组和Bloom Filter时，并不认为产生冲突及访问了片外，只有通过改进算法中位图数组和Bloom Filter的共同筛选后，访问了哈希表的存储桶时发现位置没有被占用，则认为没有产生冲突，仅仅访问了一次片外;反之认为发生了冲突，并进行了片外的访问。实验结果如图1所示。
通过图1可以发现改进哈希算法片外访问次数低于原始孔雀哈希算法，改进哈希算法的冲突次数也低于原始孔雀哈希算法。改进哈希算法的片外访问平均次数为264, 冲突平均次数为83,较原始孔雀哈希算法减少约34%；，冲突次数减少约47%。由于数据量为242，可得知每一个键值的片外访问次数约为1.09，接近于1次，哈希表的查找速度大大提高。
为了进一步体现出改进算法的优越性，本文从片外访问次数与冲突数的关系方面进一步讨论，如图2~3所示。
图片
图1 片外访问次数与冲突数对比
由图2可知，随着冲突次数的增加，片外访问次数也急剧增加, 访问次数为370~430，即每一个键值的片外访问次数的波动范围约为（1.53,1.77）。
图片
图2 原始孔雀哈希算法关系
由图3可知，随着冲突次数的增加，片外访问次数增加并不急剧，而是出现了波动，这种波动仍处于访问次数250~280，即每一个键值的片外访问次数的波动范围为（1.03,1.15）。通过两图对比，说明了改进哈希算法较原始孔雀哈希算法稳定性更强。
图片
图3 改进哈希算法关系
3.2 空间性能仿真结果
由于实验中关键字大小固定，故未将其加入内存开销的计算。实际上，哈希表的内存开销主要是其他数据结构在表中应用带来的额外开销，如表1所示。
表格(有表名)
表1 不同表长的内存开销对比
最大表长表的个数原始算法内存开销/B改进算法内存开销/B
5124 450304
1B0244900730
2B04841B8001B328
4B09643B6002B640
从表1可知，原始孔雀哈希算法的内存开销在各种表长情况下，都会比改进哈希算法的内存开销要大一些，改进后的内存开销平均节省了约27.7%。
3.3 实验分析
通过时间性能仿真可以得出改进后的哈希表在片外访问次数和冲突次数方面都有很大的优化。在空间性能方面，实验也证明改进哈希算法的内存开销确实小于原始孔雀哈希算法的开销。
4 结语
改进哈希表的目标在于能够有好的决策进行高速查找及改善最坏情况。在孔雀哈希的基础上，通过引入位图数组，提出了一种新的倒插入分段哈希表。改进后的哈希表较原始孔雀哈希算法对片外的访问次数减少了约34%，内存开销降低了约27.7%，降低了能耗。
げ慰嘉南:
［1］
KUMAR S, TURNER J, CROWLEY P. Peacock hashing: Deterministic and updatable hashing for high performance networking［C］// The 27th Conference on Computer Communications. Washington, DC: IEEE Computer Society, 2008: 101-105.
［2］
AHMADI M, WONG S. A memoryoptimized bloom filter using an additional hashing function［C］// IEEE Global Telecommunications Conference. Washington, DC: IEEE Computer Society, 2008: 1-5.
［3］
KUMAR S, CROWLEY P. Segmented hash: An efficient hash table implementation for high performance networking subsystems ［C］ // Proceedings of the 2005 ACM Symposium on Architecture for Networking and Communications Systems. New York: Springer, 2005: 91-103.
［4］
DHARMAPURIKAR S, KRISHNAMURTHY P. Deep packet inspection using parallel bloom filters［J］ . IEEE Micro, 2004, 24(1): 52-61.
［5］
潘登,张大方,谢鲲,等.一种基于折半层次搜索的包分类算法［J］.计算机应用, 2009, 29(2): 500-506.