一种改进的分段哈希算法

胥 攀,刘胜利,兰景宏,肖 达

(数学工程与先进计算国家重点实验室,郑州450002)

·开发研究与工程应用·

一种改进的分段哈希算法

胥 攀,刘胜利,兰景宏,肖 达

(数学工程与先进计算国家重点实验室,郑州450002)

为更有效地降低分段哈希算法的碰撞率,提出一种改进的分段哈希算法。在各哈希子表中采用开放地址法,降低各哈希子表中元素的碰撞率,进而降低整个分段哈希算法的碰撞率。对碰撞率、时间效率、空间效率进行分析。使用11 119 905个不同IP数据包的五元组信息,对该算法的碰撞率和时间效率进行测试。实验结果表明,改进的分段哈希算法在不增加内存使用的情况下,可有效降低分段哈希算法的碰撞率,并且随着分段哈希子表数量的增加,该算法的各项性能优势会更加明显。

哈希;开放地址法;碰撞;分段哈希子表;五元组;分类

1 概述

哈希算法广泛应用于计算机科学的各个方面,可以用于负载均衡[1]、TCP/IP状态管理[2]、IP地址查询[3-4]、数据包分类[5-8]等方面,它能够提供O(1)复杂度的查询、插入、删除操作。随着哈希表中元素的增多,哈希算法会出现碰撞问题。哈希算法的碰撞问题会在很大程度上降低哈希算法的性能。解决哈希算法的碰撞问题通常会损耗计算机大量的时间或者空间性能,因此,研究如何在降低计算机性能损耗的情况下,降低哈希算法的碰撞问题非常有意义。

文献[9]提出了分段哈希算法,通过将一个哈希表分成多个子表,各子表使用不同的哈希函数降低碰撞,具有空间利用率较低的缺点。后来又提出孔雀哈希算法[10],虽然大大降低了内存空间的使用,但是在查询、删除等操作时,具有一些时间性能上的不确定性。

文献[11]根据碰撞哈希元素被查询的概率对碰撞的哈希元素进行排序,提高了哈希算法的时间效率,但是没能降低碰撞率,并且该方法不具备广泛适用性。

本文通过对常用哈希碰撞解决方法的分析,提出一种改进的分段哈希算法。通过对11 119 905条不同的五元组信息进行测试,在分段哈希子表数为2的情况下,将碰撞元素的个数从187 668减少到26 184。

2 哈希算法

2.1 常用的哈希算法冲突解决方法

解决哈希算法碰撞问题的方法很多[12-13],使用最广泛的有2种[9,11]:开放地址法和拉链法。

开放地址法将碰撞的元素在哈希表中进行特定的运算,再进行一次查找,直到找到正确的元素为止。该方法具有节省内存空间的优点,但是当哈希表中元素较多时,会产生连锁碰撞,极大降低哈希算法的时间性能。

拉链法在哈希表中碰撞元素位置处建立一个链表存储碰撞的元素,具有冲突处理简单、平均查询时间短的特点,但是在进行元素删除操作时,有很多额外的时间开销。

2.2 分段哈希算法

分段哈希算法也是降低哈希函数碰撞的一种方法。分段哈希算法将哈希表分成多个子表,各子表使用不同的哈希算法进行哈希运算,当元素在上一子表产生碰撞后,被移入下一子表再次进行哈希运算。分段哈希算法通过多次哈希运算降低冲突率,但是每次进行不同哈希运算需要一个分段哈希子表存储碰撞的元素,对内存空间的使用过高。

3 改进的分段哈希算法

本文在分段哈希表结构基础上,结合解决哈希碰撞问题中常用的开放地址法,设计一种复合的冲突处理算法。该算法在不增加内存空间的基础上,通过将分段哈希函数的各个表中产生碰撞的元素的哈希值根据开放地址法,再次进行一次简单的运算,形成新的哈希值,然后再次查看该元素在本表中是否依然冲突,如果依然冲突则移入下一子表进行哈希运算。

本文的哈希表结构主体依然是分段哈希的表结构,由多个子表Ti(i=1,2,…)构成,子表之间按顺序进行哈希运算,各子表使用不同的哈希算法hi(),根据开放地址法对各个子表的碰撞元素使用的函数为f()。

3.1 算法描述

本文从插入操作的角度对改进后的哈希算法进行描述,删除操作、查询操作的流程类似。插入操作的伪代码如下:

图1所示为只有2个子表情况下改进后的哈希算法的插入操作流程,并且各表的碰撞元素再运算的函数为f()=hi()+1。

图1 哈希算法插入操作示意图

算法具体步骤如下:

(1)元素k1通过h1()哈希函数得到结果h1(k1),T1表中该位置为空,故元素k1进入位置h1(k1);

(2)元素k2通过h1()哈希函数得到结果h1(k2),且h1(k2)=h1(k1),但是k2≠k1,所以元素k2和k1在表T1中碰撞,根据本文算法,则进行一次运算,h1(k2)=h1(k2)+1,新的h1(k2)位置元素为空,故元素k2进入位置h1(k2),即位置h1(k1)+1;

(3)元素k3通过h1()哈希函数得到结果h1(k3),T1表中该位置为空,故元素k3进入位置h1(k3);

(4)元素k4通过h1()哈希函数得到结果h1(k4),且h1(k4)=h1(k1),但是k4≠k1,所以元素k4和k1在表T1中碰撞,然后令h1(k4)=h1(k4)+1,新的h1(k4)位置处元素k4和k2碰撞。然后元素k4进入表T2,用h2()哈希函数进行计算得到结果h2(k4),T2表中该位置为空,故元素k4进入位置h2(k4)。

3.2 算法性能分析

为说明改进的哈希算法的有效性,本文从哈希算法的碰撞率、时间效率、空间效率3个角度进行分析。

3.2.1 碰撞率分析

分段哈希算法在表Ti(i=1,2,…)中哈希函数hi()产生碰撞后,在Ti+1表中使用新的哈希函数hi+1()进行哈希,寻找对应的位置进行插入,而改进后的哈希算法在表Ti中哈希函数hi()产生碰撞后,先查找表Ti中哈希值的下一个位置是否合适,如果依然碰撞,再在表Ti+1中使用新的哈希函数hi+1()进行哈希,并在Ti+1中使用类似的过程寻找合适的空间。

令分段哈希表子表个数为n(n＞0),令Pc(i)表示分段哈希表Ti的哈希函数hi()产生碰撞的概率,Pl(i)表示改进后分段哈希表Ti的哈希函数hi()产生碰撞后,进行一次加1操作,再次查表产生碰撞的概率(i=1,2,…,n)。

普通的分段哈希函数的碰撞率为:

改进后的分段哈希函数的碰撞率为:

由于Pc(i)和Pl(i)都小于1,很显然P2＜P1,因此改进后的哈希函数的碰撞率大大降低。

3.2.2 时间性能分析

令Thi表示分段哈希算法在表Ti中的哈希函数hi()的计算时间加上哈希计算后元素匹配的时间。T0表示改进后分段哈希算法在表Ti中的哈希函数hi()碰撞后进行加1操作及与相应位置内容匹配的时间。

普通的分段哈希函数在表Ti中哈希需要的时间为:

改进后的分段哈希函数在表Ti中哈希需要的时间为:

因此,对一个元素进行一次哈希操作需要的时间分别为:

由式(3)～式(6)可知,分段哈希函数的运行时间与哈希表的个数、各子表哈希函数的计算时间、碰撞率、元素匹配时间等因素都有关联,因此2种哈希算法的计算时间很难进行精确的对比,但是可以通过对某些变量进行稍微的调整,可以得出一个大概的性能对比。

本文仅从调整分段哈希子表个数的角度对2种分段哈希算法的性能进行分析对比。当分段哈希子表数为n(n＞0)时,原始分段哈希算法处理一个元素需要的时间为Sn,改进后的分段哈希算法处理一个元素需要的时间为S′n。

当n=1时,有:

很容易可以得出S1＜S′1,即改进后的哈希算法处理一个元素的计算时间长,时间性能较差。

当n=2时,有:

由式(9)～式(11)可以看出,S1和S′1的大小由(1-Pl(1))Th(2)和(1+Pl(1)Pc(2))T0确定。在一般情况下,Th(2)＞T0,Pl(1)和Pl(1)Pc(2)都是比较小的正数,故(1-Pl(1))Th(2)和(1+Pl(1)Pc(2))T0的大小关系很难确定。因此,比较S2和S′2的大小很困难。根据不同的Pl(i)和Pc(i)以及Th(2),T0的值,各种情况都是可能出现的。但是可以看出,随着分段哈希表数量的增大,改进后的分段哈希函数的时间优势会慢慢体现出来,并且由于改进后的哈希函数具有更低的碰撞率,导致哈希表的数目会比原来的少,因此随着分段哈希子表数量的增加,改进后的分段哈希算法计算速度比原始分段哈希函数更快也是非常可能的。

3.2.3 空间性能分析

改进后的哈希算法使用和原分段哈希算法相同的表结构,对内存空间的使用一定不会比原始分段哈希算法内存空间大。但是改进后的分段哈希算法由于其较低的碰撞率,在哈希表数量上可能会降低,因此会降低内存空间的使用。

综上所述,改进后的哈希算法极大降低了分段哈希算法的碰撞率,同时改进后的哈希算法的计算速度和原始算法相比,并不会降低多少,随着分段哈希子表数量的增多,改进后的哈希算法的计算速度会更快。并且在内存空间使用上,改进后的分段哈希表不会大于原始分段哈希表,随着碰撞率的降低,反而会降低内存空间的使用。

4 实验结果与分析

本文对改进后的哈希算法进行性能测试,并与原来分段哈希算法的性能进行对比,主要从2种哈希算法的碰撞率和时间性能方面进行测试。

实验机器的配置CPU为Pentium(R)Dual-CoreE5500,主频2.8 GHz,内存4 GB,Windows7 64位操作系统。

实验测试的数据是从1 Gb带宽的校园关口处采集而来,共1千多万个不同的网络数据包五元组信息,分为10组进行测试。

4.1 分段哈希算法碰撞率测试及结果

通过分配相同大小的哈希表空间,保证2种算法的哈希子表的数量、大小。对应子表使用的哈希函数也相同的情况下,检测最后碰撞元素的个数,来测试2种哈希算法的碰撞率。碰撞元素个数少的算法的碰撞率低。

本文为简化实验流程,设定分段哈希子表数量为2,各子表的大小为221–1,分段哈希子表T1使用IPSX哈希函数[8],分段哈希子表T2使用CRC32哈希函数[8],各表的碰撞元素再运算函数f()=hi()+1。2种算法碰撞性能的测试结果如表1所示。

表1 2种哈希算法的碰撞情况测试结果

从表1中可以明显得出,在每个分组中,改进后的哈希算法的碰撞率都远低于原始分段哈希算法。

4.2 分段哈希算法时间性能测试及结果

对2种分段哈希算法的时间性能测试较难,各分段哈希子表对应的哈希函数的变化、分段哈希子表数量的变化、元素匹配操作的变化都会影响2种哈希算法的时间性能,见式(9)～式(11)。但是可以通过控制变量法对哈希算法的性能进行一个大概的比较。本文从分段哈希子表数量变化的角度对哈希算法的性能进行测试,其他的变化情况未考虑。

对4.1节中各个哈希子表的大小进行压缩,将各哈希子表的大小调整为219-1,增大各子表元素的碰撞概率,然后增加不同数量的哈希子表装载碰撞元素。对比2种分段哈希算法在不同的哈希子表数目下,运算消耗的时间。

由于本文关注2种不同的分段哈希算法的时间性能,对于各子表中使用的哈希函数性能不作要求,但是为了避免2个连续的子表采用相同的哈希函数导致元素的碰撞传递概率增大,本文令各分段哈希子表交替使用CRC32和IPSX哈希函数进行哈希运算。

本文分别测试了2种分段哈希算法在哈希子表数为2～8各种情况下的时间性能,测试的五元组数据为4.1节中第9组和第10组两组数据,结果如表2、表3所示。

表2 2种哈希算法第9组数据时间测试结果 ms

表3 2种哈希算法第10组数据时间测试结果 ms

从表2和表3可以看出,在分段哈希子表数量较少的情况下,2种分段哈希算法的时间性能相当,当哈希子表数为2时,改进前和改进后的分段哈希算法数据处理时间差距不大。随着分段哈希子表数量增加,改进后的分段哈希函数的时间性能优势越来越明显,哈希子表数从3开始,2种哈希算法的时间消耗差距开始增大。由此可以得出,当分段哈希子表数增多时,改进后的哈希算法的时间性能会渐渐超过原始分段哈希算法。

4.3 实验分析

通过从碰撞率和时间效率2个方面进行测试,改进后的分段哈希算法在不改变内存使用的情况下,大大降低了原始分段哈希算法的碰撞率,并且在时间性能上和原始分段哈希算法相当,并且随着分段哈希子表数的增加,改进后的分段哈希函数的性能优势会更加明显。

5 结束语

本文提出改进的分段哈希算法,测试结果表明,该算法可以有效降低原来分段哈希算法的碰撞率。在分段哈希子表较少的情况下,改进后分段哈希算法的时间效率提高不明显,但是随着分段哈希子表数的增多,改进后的分段哈希算法效率会越来越高。

[1] Vócking B.How Asymmetry Helps Load Balancing[J]. Journal of the ACM on Computer,2003,50(4):568-589.

[2] Fall K R,Stevens W R.TCP/IP Illustrated[M].[S.l.]: Addison-Wesley Professional,2011.

[3] 刘舱强,邓昌胜,余 谅.基于哈希表的最长前缀匹配算法改进[J].微计算机信息,2009,(30):143-144.

[4] 崔尚森,张白一.一种基于哈希表和Trie树的快速IP路由查找算法[J].计算机工程与应用,2005,41(9): 156-158.

[5] 赵国锋,陈群丽.基于Hash和AQT的类决策树包分类算法研究[J].通信技术,2010,43(2):210-212.

[6] 李英毅,贾 雨.用Hash表技术实现快速流分类[J].成都理工大学学报:自然科学版,2008,35(1):108-112.

[7] 强士卿,程 光.基于流的哈希函数比较分析研究[J].南京师范大学学报:工程技术版,2008,8(4):25-28.

[8] 程 光,龚 俭,丁 伟,等.面向IP流测量的哈希算法研究[J].软件学报,2005,16(5):652-658.

[9] Kumar S,Crowley P.Segmented Hash:An Efficient Hash Table Implementation for High Performance Networking Subsystems[C]//Proceedings of ACM Symposium on Architecture for Networking and Communications Systems. [S.l.]:ACM Press,2005:91-103.

[10] Kumar S,TurnerJ,CrowleyP.Peacock Hashing: Deterministic and Updatable Hashing for High Performance Networking[C]//Proceedings of the 27th Conference on Computer Communications.[S.l.]: IEEE Press,2008:101-105.

[11] 张朝霞,刘耀军.有效的哈希冲突解决办法[J].计算机应用,2010,30(11):2965-2966.

[12] MacKenzie P D,Plaxton C G,Rajaraman R.On Contention Resolution Protocols and Associated Probabilistic Phenomena[C]//Proceedings of the 26th Annual ACM Symposium on Theory of Computing.[S.l.]:ACM Press,1994: 153-162.

[13] Cormen T H,Leiserson C E,Rivest R L,et al.Introduction to Algorithms[M].Cambridge,USA:MIT Press,2001.

编辑 顾逸斐

An Improved Segment Hash Algorithm

XU Pan,LIU Shengli,LAN Jinghong,XIAO Da
(State Key Laboratory of Mathematical Engineering and Advanced Computing,Zhengzhou 450002,China)

Collision rate is important to evaluate the hash algorithm.To reduce the collision rate of segment hash algorithm,an improved algorithm is proposed by combining the open address method and the segment hash algorithm,and the performance of the algorithm including collision rate,time efficiency,space efficiency is analyzed.The algorithm is tested by 11 119 905 different IP packets.Experimental results show that the algorithm can reduce the collision rate without increasing memory usage,which can effectively reduce the collision rate of piecewise hashing algorithm.And with the number of sub-table hash increasing,the algorithm is more efficient.

hash;open address method;collision;segment hash table;five-tuple;classification

1000-3428(2015)01-0266-04

A

TP309.7

10.3969/j.issn.1000-3428.2015.01.050

国家自然科学基金资助项目(61309007);郑州市科技创新团队基金资助项目(10CXTD150)。

胥 攀(1988-),男,硕士研究生,主研方向:信息安全;刘胜利,副教授、博士;兰景宏,硕士研究生;肖 达,讲师、博士研究生。

2014-02-19

2014-03-21 E-mail:xupan07@163.com

中文引用格式:胥 攀,刘胜利,兰景宏,等.一种改进的分段哈希算法[J].计算机工程,2015,41(1):266-269.

英文引用格式:Xu Pan,Liu Shengli,Lan Jinghong,et al.An Improved Segment Hash Algorithm[J].Computer Engineering,2015,41(1):266-269.