文档介绍：倒插入分段哈希算法
摘要:
受到孔雀哈希与分段哈希算法的启发,提出了一种新的倒插入分段哈希表。该算法从改变表的操作顺序及修改孔雀哈希数据结构着手,保证了片外访问的平均次数接近于1。分析与实验表明,该算法具有较高的效率,降低了内存开销。
?ス丶?词:
孔雀哈希;分段哈希;位图数组;布鲁姆过滤器;内存
?ブ型挤掷嗪牛? ;
文献标志码:A
英文标题
??
Inverse insert algorithm based on segment hash
?び⑽淖髡呙?
TANG Ming??1,SHI Chang??qiong1,2,ZHOU Kai??qing??1, ZHANG Da??fang??2
?び⑽牡刂?(
puter munication Engineering, Changsha University of Science and Technology, Changsha Hunan 410114, China??;??
puter munication, 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 off??chip 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 哈希表??
哈希表能够对键值进行散列、快速查找、删除以及插入等操作。下面分别介绍分段哈希表及孔雀哈希表。??
分段哈希表??
分段哈希[3] 采用将哈希表分成多级子表和一个主表,并使用多个哈希函数进行散列的策略来解决冲突。相对于链式哈希及其他哈希的冲突策略,分段哈希表的提出虽然能够减少片外访问的次数,就本身数据结构而言,无法很好地解决冲突,导致键值的查找时间较长。??
孔雀哈希算法??
孔雀哈希表在分段哈希表的基础上对数据结构进行了修改,在每一个表前都添加了Bloom Filter。虽然在访问外存次数上大大降低,却带来了内存开销问题。另外,孔雀哈希表采取了一种负载平衡的策略,使各表间的散列位子形成了一种链式关系,但在删除过程中,为了保存这种关系,对于表的优先权而言,表的优先权低的键值需要向优先权高的表中一一移动,在删除操作时也会在时间上带来一定的开销且复杂。
??
2 倒插入分段哈希算法??
在分段哈希和孔雀哈希思想的基础上,本文提出倒插入分段哈希表。通过与桶深度为1的孔雀哈希进行对比,改进后的哈希表兼容了内存开销小、片外访问次数低的特点。??
算法思想??
本算法的改进主要体现在将主表的Bloom Filter去掉而改成一个位图数组,大大减少了内存的开销,在每个子表前都添加一个位图数组。在搜索键值的策略上,先探测位图数组中的相应位置已经存放了关键值,再在Bloom Filter中进行查找,但由于Bloom Fi