胥 攀,劉勝利,蘭景宏,肖 達(dá)

(數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室,鄭州450002)

·開發(fā)研究與工程應(yīng)用·

一種改進(jìn)的分段哈希算法

胥 攀,劉勝利,蘭景宏,肖 達(dá)

(數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室,鄭州450002)

為更有效地降低分段哈希算法的碰撞率,提出一種改進(jìn)的分段哈希算法。在各哈希子表中采用開放地址法,降低各哈希子表中元素的碰撞率,進(jìn)而降低整個(gè)分段哈希算法的碰撞率。對(duì)碰撞率、時(shí)間效率、空間效率進(jìn)行分析。使用11 119 905個(gè)不同IP數(shù)據(jù)包的五元組信息,對(duì)該算法的碰撞率和時(shí)間效率進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果表明,改進(jìn)的分段哈希算法在不增加內(nèi)存使用的情況下,可有效降低分段哈希算法的碰撞率,并且隨著分段哈希子表數(shù)量的增加,該算法的各項(xiàng)性能優(yōu)勢(shì)會(huì)更加明顯。

哈希;開放地址法;碰撞;分段哈希子表;五元組;分類

1 概述

哈希算法廣泛應(yīng)用于計(jì)算機(jī)科學(xué)的各個(gè)方面,可以用于負(fù)載均衡[1]、TCP/IP狀態(tài)管理[2]、IP地址查詢[3-4]、數(shù)據(jù)包分類[5-8]等方面,它能夠提供O(1)復(fù)雜度的查詢、插入、刪除操作。隨著哈希表中元素的增多,哈希算法會(huì)出現(xiàn)碰撞問題。哈希算法的碰撞問題會(huì)在很大程度上降低哈希算法的性能。解決哈希算法的碰撞問題通常會(huì)損耗計(jì)算機(jī)大量的時(shí)間或者空間性能,因此,研究如何在降低計(jì)算機(jī)性能損耗的情況下,降低哈希算法的碰撞問題非常有意義。

文獻(xiàn)[9]提出了分段哈希算法,通過將一個(gè)哈希表分成多個(gè)子表,各子表使用不同的哈希函數(shù)降低碰撞,具有空間利用率較低的缺點(diǎn)。后來又提出孔雀哈希算法[10],雖然大大降低了內(nèi)存空間的使用,但是在查詢、刪除等操作時(shí),具有一些時(shí)間性能上的不確定性。

文獻(xiàn)[11]根據(jù)碰撞哈希元素被查詢的概率對(duì)碰撞的哈希元素進(jìn)行排序,提高了哈希算法的時(shí)間效率,但是沒能降低碰撞率,并且該方法不具備廣泛適用性。

本文通過對(duì)常用哈希碰撞解決方法的分析,提出一種改進(jìn)的分段哈希算法。通過對(duì)11 119 905條不同的五元組信息進(jìn)行測(cè)試,在分段哈希子表數(shù)為2的情況下,將碰撞元素的個(gè)數(shù)從187 668減少到26 184。

2 哈希算法

2.1 常用的哈希算法沖突解決方法

解決哈希算法碰撞問題的方法很多[12-13],使用最廣泛的有2種[9,11]:開放地址法和拉鏈法。

開放地址法將碰撞的元素在哈希表中進(jìn)行特定的運(yùn)算,再進(jìn)行一次查找,直到找到正確的元素為止。該方法具有節(jié)省內(nèi)存空間的優(yōu)點(diǎn),但是當(dāng)哈希表中元素較多時(shí),會(huì)產(chǎn)生連鎖碰撞,極大降低哈希算法的時(shí)間性能。

拉鏈法在哈希表中碰撞元素位置處建立一個(gè)鏈表存儲(chǔ)碰撞的元素,具有沖突處理簡(jiǎn)單、平均查詢時(shí)間短的特點(diǎn),但是在進(jìn)行元素刪除操作時(shí),有很多額外的時(shí)間開銷。

2.2 分段哈希算法

分段哈希算法也是降低哈希函數(shù)碰撞的一種方法。分段哈希算法將哈希表分成多個(gè)子表,各子表使用不同的哈希算法進(jìn)行哈希運(yùn)算,當(dāng)元素在上一子表產(chǎn)生碰撞后,被移入下一子表再次進(jìn)行哈希運(yùn)算。分段哈希算法通過多次哈希運(yùn)算降低沖突率,但是每次進(jìn)行不同哈希運(yùn)算需要一個(gè)分段哈希子表存儲(chǔ)碰撞的元素,對(duì)內(nèi)存空間的使用過高。

3 改進(jìn)的分段哈希算法

本文在分段哈希表結(jié)構(gòu)基礎(chǔ)上,結(jié)合解決哈希碰撞問題中常用的開放地址法,設(shè)計(jì)一種復(fù)合的沖突處理算法。該算法在不增加內(nèi)存空間的基礎(chǔ)上,通過將分段哈希函數(shù)的各個(gè)表中產(chǎn)生碰撞的元素的哈希值根據(jù)開放地址法,再次進(jìn)行一次簡(jiǎn)單的運(yùn)算,形成新的哈希值,然后再次查看該元素在本表中是否依然沖突,如果依然沖突則移入下一子表進(jìn)行哈希運(yùn)算。

本文的哈希表結(jié)構(gòu)主體依然是分段哈希的表結(jié)構(gòu),由多個(gè)子表Ti(i=1,2,…)構(gòu)成,子表之間按順序進(jìn)行哈希運(yùn)算,各子表使用不同的哈希算法hi(),根據(jù)開放地址法對(duì)各個(gè)子表的碰撞元素使用的函數(shù)為f()。

3.1 算法描述

本文從插入操作的角度對(duì)改進(jìn)后的哈希算法進(jìn)行描述,刪除操作、查詢操作的流程類似。插入操作的偽代碼如下:

圖1所示為只有2個(gè)子表情況下改進(jìn)后的哈希算法的插入操作流程,并且各表的碰撞元素再運(yùn)算的函數(shù)為f()=hi()+1。

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

算法具體步驟如下:

(1)元素k1通過h1()哈希函數(shù)得到結(jié)果h1(k1),T1表中該位置為空,故元素k1進(jìn)入位置h1(k1);

(2)元素k2通過h1()哈希函數(shù)得到結(jié)果h1(k2),且h1(k2)=h1(k1),但是k2≠k1,所以元素k2和k1在表T1中碰撞,根據(jù)本文算法,則進(jìn)行一次運(yùn)算,h1(k2)=h1(k2)+1,新的h1(k2)位置元素為空,故元素k2進(jìn)入位置h1(k2),即位置h1(k1)+1;

(3)元素k3通過h1()哈希函數(shù)得到結(jié)果h1(k3),T1表中該位置為空,故元素k3進(jìn)入位置h1(k3);

(4)元素k4通過h1()哈希函數(shù)得到結(jié)果h1(k4),且h1(k4)=h1(k1),但是k4≠k1,所以元素k4和k1在表T1中碰撞,然后令h1(k4)=h1(k4)+1,新的h1(k4)位置處元素k4和k2碰撞。然后元素k4進(jìn)入表T2,用h2()哈希函數(shù)進(jìn)行計(jì)算得到結(jié)果h2(k4),T2表中該位置為空,故元素k4進(jìn)入位置h2(k4)。

3.2 算法性能分析

為說明改進(jìn)的哈希算法的有效性,本文從哈希算法的碰撞率、時(shí)間效率、空間效率3個(gè)角度進(jìn)行分析。

3.2.1 碰撞率分析

分段哈希算法在表Ti(i=1,2,…)中哈希函數(shù)hi()產(chǎn)生碰撞后,在Ti+1表中使用新的哈希函數(shù)hi+1()進(jìn)行哈希,尋找對(duì)應(yīng)的位置進(jìn)行插入,而改進(jìn)后的哈希算法在表Ti中哈希函數(shù)hi()產(chǎn)生碰撞后,先查找表Ti中哈希值的下一個(gè)位置是否合適,如果依然碰撞,再在表Ti+1中使用新的哈希函數(shù)hi+1()進(jìn)行哈希,并在Ti+1中使用類似的過程尋找合適的空間。

令分段哈希表子表個(gè)數(shù)為n(n＞0),令Pc(i)表示分段哈希表Ti的哈希函數(shù)hi()產(chǎn)生碰撞的概率,Pl(i)表示改進(jìn)后分段哈希表Ti的哈希函數(shù)hi()產(chǎn)生碰撞后,進(jìn)行一次加1操作,再次查表產(chǎn)生碰撞的概率(i=1,2,…,n)。

普通的分段哈希函數(shù)的碰撞率為:

改進(jìn)后的分段哈希函數(shù)的碰撞率為:

由于Pc(i)和Pl(i)都小于1,很顯然P2＜P1,因此改進(jìn)后的哈希函數(shù)的碰撞率大大降低。

3.2.2 時(shí)間性能分析

令Thi表示分段哈希算法在表Ti中的哈希函數(shù)hi()的計(jì)算時(shí)間加上哈希計(jì)算后元素匹配的時(shí)間。T0表示改進(jìn)后分段哈希算法在表Ti中的哈希函數(shù)hi()碰撞后進(jìn)行加1操作及與相應(yīng)位置內(nèi)容匹配的時(shí)間。

普通的分段哈希函數(shù)在表Ti中哈希需要的時(shí)間為:

改進(jìn)后的分段哈希函數(shù)在表Ti中哈希需要的時(shí)間為:

因此,對(duì)一個(gè)元素進(jìn)行一次哈希操作需要的時(shí)間分別為:

由式(3)～式(6)可知,分段哈希函數(shù)的運(yùn)行時(shí)間與哈希表的個(gè)數(shù)、各子表哈希函數(shù)的計(jì)算時(shí)間、碰撞率、元素匹配時(shí)間等因素都有關(guān)聯(lián),因此2種哈希算法的計(jì)算時(shí)間很難進(jìn)行精確的對(duì)比,但是可以通過對(duì)某些變量進(jìn)行稍微的調(diào)整,可以得出一個(gè)大概的性能對(duì)比。

本文僅從調(diào)整分段哈希子表個(gè)數(shù)的角度對(duì)2種分段哈希算法的性能進(jìn)行分析對(duì)比。當(dāng)分段哈希子表數(shù)為n(n＞0)時(shí),原始分段哈希算法處理一個(gè)元素需要的時(shí)間為Sn,改進(jìn)后的分段哈希算法處理一個(gè)元素需要的時(shí)間為S′n。

當(dāng)n=1時(shí),有:

很容易可以得出S1＜S′1,即改進(jìn)后的哈希算法處理一個(gè)元素的計(jì)算時(shí)間長(zhǎng),時(shí)間性能較差。

當(dāng)n=2時(shí),有:

由式(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)都是比較小的正數(shù),故(1-Pl(1))Th(2)和(1+Pl(1)Pc(2))T0的大小關(guān)系很難確定。因此,比較S2和S′2的大小很困難。根據(jù)不同的Pl(i)和Pc(i)以及Th(2),T0的值,各種情況都是可能出現(xiàn)的。但是可以看出,隨著分段哈希表數(shù)量的增大,改進(jìn)后的分段哈希函數(shù)的時(shí)間優(yōu)勢(shì)會(huì)慢慢體現(xiàn)出來,并且由于改進(jìn)后的哈希函數(shù)具有更低的碰撞率,導(dǎo)致哈希表的數(shù)目會(huì)比原來的少,因此隨著分段哈希子表數(shù)量的增加,改進(jìn)后的分段哈希算法計(jì)算速度比原始分段哈希函數(shù)更快也是非?？赡艿摹?/p>

3.2.3 空間性能分析

改進(jìn)后的哈希算法使用和原分段哈希算法相同的表結(jié)構(gòu),對(duì)內(nèi)存空間的使用一定不會(huì)比原始分段哈希算法內(nèi)存空間大。但是改進(jìn)后的分段哈希算法由于其較低的碰撞率,在哈希表數(shù)量上可能會(huì)降低,因此會(huì)降低內(nèi)存空間的使用。

綜上所述,改進(jìn)后的哈希算法極大降低了分段哈希算法的碰撞率,同時(shí)改進(jìn)后的哈希算法的計(jì)算速度和原始算法相比,并不會(huì)降低多少,隨著分段哈希子表數(shù)量的增多,改進(jìn)后的哈希算法的計(jì)算速度會(huì)更快。并且在內(nèi)存空間使用上,改進(jìn)后的分段哈希表不會(huì)大于原始分段哈希表,隨著碰撞率的降低,反而會(huì)降低內(nèi)存空間的使用。

4 實(shí)驗(yàn)結(jié)果與分析

本文對(duì)改進(jìn)后的哈希算法進(jìn)行性能測(cè)試,并與原來分段哈希算法的性能進(jìn)行對(duì)比,主要從2種哈希算法的碰撞率和時(shí)間性能方面進(jìn)行測(cè)試。

實(shí)驗(yàn)機(jī)器的配置CPU為Pentium(R)Dual-CoreE5500,主頻2.8 GHz,內(nèi)存4 GB,Windows7 64位操作系統(tǒng)。

實(shí)驗(yàn)測(cè)試的數(shù)據(jù)是從1 Gb帶寬的校園關(guān)口處采集而來,共1千多萬(wàn)個(gè)不同的網(wǎng)絡(luò)數(shù)據(jù)包五元組信息,分為10組進(jìn)行測(cè)試。

4.1 分段哈希算法碰撞率測(cè)試及結(jié)果

通過分配相同大小的哈希表空間,保證2種算法的哈希子表的數(shù)量、大小。對(duì)應(yīng)子表使用的哈希函數(shù)也相同的情況下,檢測(cè)最后碰撞元素的個(gè)數(shù),來測(cè)試2種哈希算法的碰撞率。碰撞元素個(gè)數(shù)少的算法的碰撞率低。

本文為簡(jiǎn)化實(shí)驗(yàn)流程,設(shè)定分段哈希子表數(shù)量為2,各子表的大小為221–1,分段哈希子表T1使用IPSX哈希函數(shù)[8],分段哈希子表T2使用CRC32哈希函數(shù)[8],各表的碰撞元素再運(yùn)算函數(shù)f()=hi()+1。2種算法碰撞性能的測(cè)試結(jié)果如表1所示。

表1 2種哈希算法的碰撞情況測(cè)試結(jié)果

從表1中可以明顯得出,在每個(gè)分組中,改進(jìn)后的哈希算法的碰撞率都遠(yuǎn)低于原始分段哈希算法。

4.2 分段哈希算法時(shí)間性能測(cè)試及結(jié)果

對(duì)2種分段哈希算法的時(shí)間性能測(cè)試較難,各分段哈希子表對(duì)應(yīng)的哈希函數(shù)的變化、分段哈希子表數(shù)量的變化、元素匹配操作的變化都會(huì)影響2種哈希算法的時(shí)間性能,見式(9)～式(11)。但是可以通過控制變量法對(duì)哈希算法的性能進(jìn)行一個(gè)大概的比較。本文從分段哈希子表數(shù)量變化的角度對(duì)哈希算法的性能進(jìn)行測(cè)試,其他的變化情況未考慮。

對(duì)4.1節(jié)中各個(gè)哈希子表的大小進(jìn)行壓縮,將各哈希子表的大小調(diào)整為219-1,增大各子表元素的碰撞概率,然后增加不同數(shù)量的哈希子表裝載碰撞元素。對(duì)比2種分段哈希算法在不同的哈希子表數(shù)目下,運(yùn)算消耗的時(shí)間。

由于本文關(guān)注2種不同的分段哈希算法的時(shí)間性能,對(duì)于各子表中使用的哈希函數(shù)性能不作要求,但是為了避免2個(gè)連續(xù)的子表采用相同的哈希函數(shù)導(dǎo)致元素的碰撞傳遞概率增大,本文令各分段哈希子表交替使用CRC32和IPSX哈希函數(shù)進(jìn)行哈希運(yùn)算。

本文分別測(cè)試了2種分段哈希算法在哈希子表數(shù)為2～8各種情況下的時(shí)間性能,測(cè)試的五元組數(shù)據(jù)為4.1節(jié)中第9組和第10組兩組數(shù)據(jù),結(jié)果如表2、表3所示。

表2 2種哈希算法第9組數(shù)據(jù)時(shí)間測(cè)試結(jié)果 ms

表3 2種哈希算法第10組數(shù)據(jù)時(shí)間測(cè)試結(jié)果 ms

從表2和表3可以看出,在分段哈希子表數(shù)量較少的情況下,2種分段哈希算法的時(shí)間性能相當(dāng),當(dāng)哈希子表數(shù)為2時(shí),改進(jìn)前和改進(jìn)后的分段哈希算法數(shù)據(jù)處理時(shí)間差距不大。隨著分段哈希子表數(shù)量增加,改進(jìn)后的分段哈希函數(shù)的時(shí)間性能優(yōu)勢(shì)越來越明顯,哈希子表數(shù)從3開始,2種哈希算法的時(shí)間消耗差距開始增大。由此可以得出,當(dāng)分段哈希子表數(shù)增多時(shí),改進(jìn)后的哈希算法的時(shí)間性能會(huì)漸漸超過原始分段哈希算法。

4.3 實(shí)驗(yàn)分析

通過從碰撞率和時(shí)間效率2個(gè)方面進(jìn)行測(cè)試,改進(jìn)后的分段哈希算法在不改變內(nèi)存使用的情況下,大大降低了原始分段哈希算法的碰撞率,并且在時(shí)間性能上和原始分段哈希算法相當(dāng),并且隨著分段哈希子表數(shù)的增加,改進(jìn)后的分段哈希函數(shù)的性能優(yōu)勢(shì)會(huì)更加明顯。

5 結(jié)束語(yǔ)

本文提出改進(jìn)的分段哈希算法,測(cè)試結(jié)果表明,該算法可以有效降低原來分段哈希算法的碰撞率。在分段哈希子表較少的情況下,改進(jìn)后分段哈希算法的時(shí)間效率提高不明顯,但是隨著分段哈希子表數(shù)的增多,改進(jìn)后的分段哈希算法效率會(huì)越來越高。

[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] 劉艙強(qiáng),鄧昌勝,余 諒.基于哈希表的最長(zhǎng)前綴匹配算法改進(jìn)[J].微計(jì)算機(jī)信息,2009,(30):143-144.

[4] 崔尚森,張白一.一種基于哈希表和Trie樹的快速IP路由查找算法[J].計(jì)算機(jī)工程與應(yīng)用,2005,41(9): 156-158.

[5] 趙國(guó)鋒,陳群麗.基于Hash和AQT的類決策樹包分類算法研究[J].通信技術(shù),2010,43(2):210-212.

[6] 李英毅,賈 雨.用Hash表技術(shù)實(shí)現(xiàn)快速流分類[J].成都理工大學(xué)學(xué)報(bào):自然科學(xué)版,2008,35(1):108-112.

[7] 強(qiáng)士卿,程 光.基于流的哈希函數(shù)比較分析研究[J].南京師范大學(xué)學(xué)報(bào):工程技術(shù)版,2008,8(4):25-28.

[8] 程 光,龔 儉,丁 偉,等.面向IP流測(cè)量的哈希算法研究[J].軟件學(xué)報(bào),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].計(jì)算機(jī)應(yīng)用,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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61309007);鄭州市科技創(chuàng)新團(tuán)隊(duì)基金資助項(xiàng)目(10CXTD150)。

胥 攀(1988-),男,碩士研究生,主研方向:信息安全;劉勝利,副教授、博士;蘭景宏,碩士研究生;肖 達(dá),講師、博士研究生。

2014-02-19

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

中文引用格式:胥 攀,劉勝利,蘭景宏,等.一種改進(jìn)的分段哈希算法[J].計(jì)算機(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.