一種改進的分段哈希算法

胥 攀,劉勝利,蘭景宏,肖 達

(數(shù)學工程與先進計算國家重點實驗室,鄭州450002)

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

一種改進的分段哈希算法

胥 攀,劉勝利,蘭景宏,肖 達

(數(shù)學工程與先進計算國家重點實驗室,鄭州450002)

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

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

1 概述

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

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

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

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

2 哈希算法

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

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

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

拉鏈法在哈希表中碰撞元素位置處建立一個鏈表存儲碰撞的元素,具有沖突處理簡單、平均查詢時間短的特點,但是在進行元素刪除操作時,有很多額外的時間開銷。

2.2 分段哈希算法

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

3 改進的分段哈希算法

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

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

3.1 算法描述

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

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

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

算法具體步驟如下:

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

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

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

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

3.2 算法性能分析

為說明改進的哈希算法的有效性,本文從哈希算法的碰撞率、時間效率、空間效率3個角度進行分析。

3.2.1 碰撞率分析

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

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

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

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

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

3.2.2 時間性能分析

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

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

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

因此,對一個元素進行一次哈希操作需要的時間分別為:

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

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

3.2.3 空間性能分析

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

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

4 實驗結果與分析

本文對改進后的哈希算法進行性能測試,并與原來分段哈希算法的性能進行對比,主要從2種哈希算法的碰撞率和時間性能方面進行測試。

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

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

4.1 分段哈希算法碰撞率測試及結果

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

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

表1 2種哈希算法的碰撞情況測試結果

從表1中可以明顯得出,在每個分組中,改進后的哈希算法的碰撞率都遠低于原始分段哈希算法。

4.2 分段哈希算法時間性能測試及結果

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

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

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

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

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

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

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

4.3 實驗分析

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

5 結束語

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

[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表技術實現(xiàn)快速流分類[J].成都理工大學學報:自然科學版,2008,35(1):108-112.

[7] 強士卿,程 光.基于流的哈希函數(shù)比較分析研究[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);鄭州市科技創(chuàng)新團隊基金資助項目(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.