胡學萱 奚建清 林妙

（1.華南理工大學 計算機科學與工程學院，廣東 廣州510006；2.華南理工大學 軟件學院，廣東 廣州510006）

哈希索引是一種快速的數(shù)據(jù)檢索方法，已廣泛應用于文件系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及一些情報檢索系統(tǒng)中［1］.動態(tài)哈希能優(yōu)雅地擴展存儲空間，根據(jù)其方法的不同，可分為可擴展哈希［2］和線性哈希［3］.如 何擴展和收縮哈希表，快速更新索引記錄以便有效地使用哈希索引，一直以來受到人們的廣泛關(guān)注.Ellis［4］提出了一種基于目錄鎖和桶鎖的兩級鎖模式的可擴展并行哈希算法；Hsu 等［5］提出了一種可以并發(fā)插入刪除的可擴展哈希算法；Kumar［6］提出的EHCW算法使用了兩階段鎖和事務回滾的策略，可并發(fā)擴展/收縮目錄，分裂/合并數(shù)據(jù)頁；Lea［7］提出了一種基于復雜鎖模式的Java 并發(fā)包，允許在改變表大小的同時進行并行查詢；Gao 等［8］提出的可擴展哈希算法周期性地切換到全局以調(diào)整哈希表大小狀態(tài)，進行多進程協(xié)作執(zhí)行數(shù)據(jù)項遷移；Shalev 等［9］提出的RSO 算法通過改變桶地址來擴展或收縮表；Zhang 等［10］提出了基于線性哈希和RSO算法的LHlf 算法；陳虎等［11］提出了一種利用多核處理器的并行計算能力提升批量插入線性哈希表性能的算法；黃玉龍等［12］提出了一種圖形處理器（GPU）加速的線性哈希表的批量插入算法GBLHT.

高性能和可擴展的哈希表是當代大數(shù)據(jù)應用的需求，故需要提高哈希表的并發(fā)處理能力.可編程圖形處理器因其眾核和高存儲器帶寬而成為并行計算的超強工具，統(tǒng)一計算設備架構(gòu)（CUDA）這種基于GPU 的計算架構(gòu)，提供了易用的編程模型和應用程序接口（API），使得將GPU 用于通用計算成為可能［13］.為充分利用GPU 的高并發(fā)計算能力，提升可擴展哈希方法的性能，文中提出了一種基于GPU 的可擴展哈希方法gEHT.

1 相關(guān)的哈希方法

1.1 可擴展哈希方法

可擴展哈希方法分裂和合并桶時，不像線性哈希方法那樣按順序進行，而是按需要進行［2］，即當向桶內(nèi)插入的數(shù)據(jù)量超過桶的剩余容量時，就分裂該桶，一次分裂產(chǎn)生的兩個桶互為對應桶；反之，當桶及其對應桶內(nèi)數(shù)據(jù)被刪除后不足一個桶的容量時，就合并這兩個桶.

圖1給出了一個初始桶經(jīng)過多次分裂形成的分裂樹，其中樹根為初始桶，實節(jié)點為已分裂產(chǎn)生的桶，稱為實桶，虛節(jié)點為預分裂產(chǎn)生的桶，稱為虛桶；實有向邊為已產(chǎn)生的分裂，虛有向邊為預產(chǎn)生的分裂.桶分裂一次，產(chǎn)生實有向邊所指的下一層的兩個桶，最底層的所有實桶為現(xiàn)有桶.可見，桶000、001、100、101、10 和11 為現(xiàn)有桶.

圖1 桶的分裂樹Fig.1 Split tree of bucket

由于各桶的層次無序，必然導致有些目錄項所指的桶為虛桶，解決的方法是將這樣的目錄項指向該虛桶的實上級桶，即分裂樹上該虛桶到初始桶的分裂路徑上最大深度的實桶.這樣，在檢索數(shù)據(jù)時，能一次定位到不同局部深度的桶上，而不用層層探索，加快了檢索速度.

1.2 基于并行技術(shù)的動態(tài)哈希

文獻［4-7］中提出基于鎖的算法，具有死鎖、長時間延遲和優(yōu)先級倒置的缺點，當進行表的擴展或收縮時，這些情況更加嚴重.文獻［8］算法使用了write-all 算法，時間復雜度為常數(shù).RSO 算法［9］使用鏈表來存儲數(shù)據(jù)，故其訪問效率低，僅適用于將關(guān)鍵字的低位作為最高有效位的哈希函數(shù).文獻［10-12］算法使用了溢出桶，降低了檢索效率，并且延遲的分裂使得分裂前溢出桶的數(shù)據(jù)要重新遷移到分裂后的桶中，這種冗余的數(shù)據(jù)遷移必然會降低插入的效率.

2 可擴展哈希方法在GPU 上的實現(xiàn)

2.1 基于GPU 的存儲結(jié)構(gòu)

為了在GPU 上動態(tài)伸縮表并克服可擴展哈希表成倍擴展的缺陷，文中采用兩層表結(jié)構(gòu)，分別是段表segList 和桶表bucketList，段表存放段地址，桶表存放桶地址.以桶表的伸縮實現(xiàn)少量的表擴展，段表的重構(gòu)實現(xiàn)大量的表擴展［12］.當擴展的桶集中在少數(shù)的段時，只需擴展少數(shù)的桶表，其他未擴展桶表可被重用.另外，段表、桶表和桶內(nèi)數(shù)據(jù)都采用數(shù)組（即便于GPU 并行處理的結(jié)構(gòu)），并且桶內(nèi)數(shù)據(jù)采用數(shù)組的結(jié)構(gòu)體（SOA）結(jié)構(gòu)而非結(jié)構(gòu)體的數(shù)組（AOS），以適應GPU 的存儲器的優(yōu)化存取要求.文獻［12］的兩層存儲結(jié)構(gòu)僅用于動態(tài)伸縮.文中采用的存儲結(jié)構(gòu)如下：

上述定義中，Gd 為全局深度，bucketNum 為現(xiàn)有桶的數(shù)量，Ld 為桶的局部深度，insertLoc 為桶內(nèi)下一個空閑地址，數(shù)組is_df 是每條數(shù)據(jù)的刪除標記.初始時有M 段，每段由N 個桶構(gòu)成，每個桶的容量為b 條記錄.維護這種結(jié)構(gòu)的挑戰(zhàn)在于保證桶分裂/合并和表擴展/收縮后，目錄項能指向改變后的桶.表及桶的改變分為以下4 種情況：

（1）桶分裂，段表不擴展.如果桶b［i］分裂產(chǎn)生新桶b［i+M·N·2b［i］.Ld］，分裂后所有桶的最大局部深度未超過全局深度，則段表不擴展.如果沒有第（i+M·N·2b［i］.Ld）/N 段桶表則增加它，修改該桶表第（i+M·N·2b［i］.Ld）%N 項指向新桶，其他項指向相應虛桶的實上級桶.桶b［i］和b［i+M·N·2b［i］.Ld］的局部深度為b［i］.Ld+1.

（2）桶合并，段表不收縮.若桶b［i］和b［i+M·N·2b［i］.Ld］合并，合并后所有桶的最大局部深度不小于全局深度，則段表不收縮.釋放桶b［i+M·N·2b［i］.Ld］，修改桶表目錄項i+M·N·2b［i］.Ld指向桶b［i］，桶b［i］的局部深度為b［i］.Ld-1.若第（i+M·N·2b［i］.Ld）/N 段桶表所有表項指向的桶的局部深度都小于全局深度，則釋放該段桶表.

（3）段表擴展.若分裂后所有桶的最大局部深度大于全局深度，則段表擴展.擴展后的第（i+M·N·2b［i］.Ld）/N 項指向新增的桶表，其他表項指向其實上級桶所在的桶表.

（4）段表收縮.合并后所有桶的最大局部深度小于全局深度，則段表收縮.

圖2為桶分裂/合并和表擴展/收縮的一個例子.圖2（a）所示的桶經(jīng)過收縮和擴展，產(chǎn)生圖2（b）、2（c）所示的桶和表.其中，圖2（a）的桶00 和10、01和11 分別合并為圖2（b）的兩個桶0 和1，則原指向桶00、10 的表項合并后指向其實上級桶0，指向01、11 的表項合并后指向其實上級桶1，桶的最大局部深度小于合并前的全局深度，段表和桶表收縮為原表的一半.圖2（a）的桶00 擴展為圖2（c）的桶000 和100，桶的最大局部深度大于原全局深度，段表擴展一倍，桶表擴展第2 段，使段表的第2 項指向新增的桶表，第3 項指向第1 段桶表.新增的桶表中，第4 項指向新增的桶100，其他擴展的表項5 指向虛桶101 的實上級桶01.可見，采用這種目錄結(jié)構(gòu)雖然擴展了指向新增桶的桶表，但能尋址倍增的桶（包括虛桶）.

圖2 表的收縮和擴展Fig.2 Shrinking and growing of table

2.2 創(chuàng)建哈希表算法

哈希索引的創(chuàng)建包括創(chuàng)建段表、桶表和桶，并使段表和桶表的各項指向新創(chuàng)建的桶表和桶.算法并行創(chuàng)建段內(nèi)的桶，偽代碼如下：

2.3 查詢算法

檢索數(shù)據(jù)先計算該數(shù)據(jù)的散列值，然后定位到桶中并在桶中搜索該數(shù)據(jù).在GPU 中，可使每個數(shù)據(jù)用一個線程處理，高并發(fā)地執(zhí)行.文獻［12］的查詢算法是基于線性哈希的，因而，對每個數(shù)據(jù)的查詢，延遲比可擴展哈希大.文中查詢算法的偽代碼如下：

2.4 刪除算法

本算法采用延遲刪除的策略，即刪除并不立即執(zhí)行，只對刪除數(shù)據(jù)做標記.在批量插入數(shù)據(jù)時，用插入數(shù)據(jù)覆蓋有刪除標記的數(shù)據(jù).該算法只需要在查詢算法queryEHTable 中加入對要刪除的索引記錄做標記，文中不再贅述.

2.5 插入算法

當批量插入的數(shù)據(jù)量大于該桶的剩余容量時，需要分裂桶，如果分裂后仍不能滿足插入需要，則要繼續(xù)分裂直到滿足需求為止.分裂會使部分數(shù)據(jù)遷移到新桶中，這些中間過程的數(shù)據(jù)遷移是不必要的，會降低索引更新速度，成為插入過程的性能瓶頸［11］.因此，文中采用預分裂技術(shù)，先循環(huán)預測桶的分裂情況，再分裂桶或擴展表并插入數(shù)據(jù)；充分利用GPU的計算能力，并行處理預測過程和實際插入過程以提高插入效率.

批量插入算法流程如圖3所示，預測部分和插入部分的算法主要由子算法A、B、C、D 構(gòu)成.插入算法的步驟如下：

圖3 批量插入算法流程圖Fig.3 Flowchart of batch insertion algorithm

（1）計算數(shù)據(jù)插入的桶號insert_bucketNo、各桶插入數(shù)據(jù)量insert_bucketNum、待分裂的桶號needSMBucketNo、待分裂的段號needSMSegNo、桶預計分裂到的局部深度SMBucketLd、待分裂桶的數(shù)量needSMBucketNum、所有待分裂桶預計分裂到的最大局部深度maxOfBucketLd.若待分裂桶的數(shù)量needSMBucketNum＞0，則置待分裂桶標記needSMBucketFlag=1，并根據(jù)上輪循環(huán)預計的桶分裂到的局部深度SMBucketLd，循環(huán)計算以上數(shù)據(jù)，直到needSMBucketNum=0，如算法A（countInsert）.

（2）若所有待分裂桶預計分裂到的最大局部深度maxOfBucketLd＞Gd，則轉(zhuǎn)步驟（3），否則轉(zhuǎn)步驟（4）.

（3）擴展段表和桶表，將擴展的段表表項指向新建的桶表，如算法B（growsTable）.

（4）若有需要分裂的桶，即needSMBucketFlag=1，則轉(zhuǎn)步驟（5），否則轉(zhuǎn)步驟（6）.

（5）分裂桶，修改桶表指針，如算法C（splitBucket）.

（6）插入數(shù)據(jù)，如算法D（insertData）.

如2.4 節(jié)所述，插入數(shù)據(jù)將覆蓋有刪除標記的數(shù)據(jù)，因此批量插入數(shù)據(jù)除了上述情況外，也會有合并桶和收縮表的情況.限于篇幅，以下偽代碼僅為分裂桶和擴展表的情況：

2.6 算法優(yōu)化

根據(jù)CUDA 的編程模型，將計算密集的任務交給GPU 線程網(wǎng)格處理，如核函數(shù)A、B、C、D，而CPU執(zhí)行邏輯復雜的處理.在GPU 上的并行優(yōu)化主要從以下幾個方面考慮：

1）任務粒度劃分.粒度越細，越能充分利用GPU大量的輕量級線程，算法的并行度越高.文中的創(chuàng)建算法中，桶間并行執(zhí)行；查詢算法中，各數(shù)據(jù)可并行查詢；插入算法的預測部分中，對各數(shù)據(jù)的插入位置、各桶分裂情況的計算相互獨立；在擴展表、分裂桶和插入數(shù)據(jù)算法中，段間、桶間和數(shù)據(jù)間的操作相互獨立，蘊含大量并行操作，如For each tid…parallel do 與End for 之間的代碼所示.

2）程序重構(gòu).GPU 的體系結(jié)構(gòu)使其適于進行邏輯簡單和數(shù)據(jù)并行的密集計算.文中合并多個循環(huán)以增強計算密度，隱藏訪存延遲；重構(gòu)分支以避免warp 內(nèi)分支轉(zhuǎn)移造成性能下降；將不同粒度的并行操作合并為一個核函數(shù)，以增強計算密度、減少核函數(shù)啟動開銷和數(shù)據(jù)傳輸開銷.

計算每個桶是否分裂、分裂到的層次等，其迭代空間是所有的桶，因而可合并循環(huán)，如A7-A13 行；計算每個數(shù)據(jù)的插入位置與計算每個桶是否需要分裂，其任務粒度不同，故不能合并循環(huán)，但可以合并為一個核函數(shù)，以便將待插入數(shù)據(jù)eData 放入共享存儲器重用，如算法A.計算桶是否分裂以及桶的層數(shù)，需要根據(jù)插入數(shù)據(jù)量與桶的剩余容量大小比較進行分支選擇，文中重構(gòu)該分支語句，將比較插入數(shù)據(jù)量與桶的剩余容量大小的邏輯值賦給記錄桶是否分裂的數(shù)組needSMBucketNo，并將該數(shù)組作為桶層數(shù)的增量，如A8、A9 行.

3）數(shù)據(jù)的組織與存儲訪問.適合并行處理的數(shù)據(jù)結(jié)構(gòu)、對GPU 上各存儲器的充分利用以及規(guī)則的訪問模式是存儲優(yōu)化的主要方法.

（1）數(shù)組能體現(xiàn)數(shù)據(jù)的并行性，適于GPU 上的密集計算.文中對哈希表結(jié)構(gòu)、算法的輸入數(shù)據(jù)eData、中 間 變 量（如insert_bucketNo、insert_bucket Num、needSMBucketNo、SMBucketLd 等）及輸出結(jié)果qResult 都使用數(shù)組.為了全局存儲器的合并訪問，盡量將數(shù)據(jù)由AOS 轉(zhuǎn)為SOA 結(jié)構(gòu)［14］，如桶內(nèi)數(shù)據(jù)Data 和輸入數(shù)據(jù)eData.文獻［12］采用數(shù)組結(jié)構(gòu)，但沒有將AOS 轉(zhuǎn)為SOA 結(jié)構(gòu).

（2）GPU 的多層次存儲器可滿足不同需求，共享存儲器訪問速度快但容量有限，為塊內(nèi)線程所共有，適合存放重用的局部性數(shù)據(jù)；全局存儲器容量大但速度慢.高效利用片上局部存儲器，可提高計算全局訪存比CGMA［13］，且采用規(guī)則訪問的模式能顯著改善程序的存儲墻問題.如算法A 中，待插入數(shù)據(jù)eData 循環(huán)重用，宜用共享存儲器存儲.從上述算法可以看出，各數(shù)組的訪存模式中，除insert_bucketNum 為隨機訪存，needSMSegNo 為跳步訪存外，其他都是規(guī)則訪問，使得全局存儲器能合并訪問，不產(chǎn)生局部訪存沖突，而這兩個數(shù)組的非規(guī)則訪存，并不適宜進行循環(huán)重構(gòu)和數(shù)組重構(gòu)［15］來改變其訪存模式.文獻［12］未提到共享存儲器的使用以及數(shù)據(jù)的規(guī)則訪問.

4）使用cuda 提供的原子函數(shù)和并行算法庫以提高代碼的性能，如A5、A11、A12 和D1 行所示.

3 算法性能分析

文中從時間和空間兩方面討論gEHT 的性能.假設哈希表初始段數(shù)為M，每段的桶數(shù)為N，每個桶的容量為b，現(xiàn)有桶的數(shù)量為bucketNum，現(xiàn)有記錄數(shù)為m，批處理的數(shù)據(jù)規(guī)模為batchNum.

3.1 時間開銷

（1）查詢時間開銷.由queryEHTable 算法可知，其時間開銷tq主要由計算搜索鍵對應散列值的時間tc、定位包含數(shù)據(jù)的桶以及在桶中檢索目標數(shù)據(jù)的時間ts構(gòu)成.由Q3 和Q4-Q8 行知，tc的復雜度為O（1），ts的復雜度為O（b），因此，查詢時間tq的復雜度為O（b）+O（1），即為常數(shù)時間，且數(shù)據(jù)規(guī)模batch-Num 越大，越能充分利用GPU 的并行計算能力，從而獲得更高的吞吐量.

（2）插入時間開銷.由insertEHTable 算法可知，其總時間開銷ti主要由預測部分和實際操作部分各子算法的執(zhí)行時間tA、tB、tC和tD組成.

子算法A 循環(huán)執(zhí)行，在最好情況下數(shù)據(jù)平均插入所有桶中，循環(huán)次數(shù)為batchNum/（bucketNum·b）；在最壞情況下數(shù)據(jù)都插入同一個桶中，循環(huán)次數(shù)為batchNum/b，其循環(huán)內(nèi)部的A2-A6、B7-B13 行并行執(zhí)行，時間開銷為O（1）.算法B、C 中B2-C11、C1-C7行也是并行執(zhí)行，其并行內(nèi)部循環(huán)次數(shù)與預測部分的循環(huán)次數(shù)相同，循環(huán)內(nèi)部的時間開銷為O（1）.算法D 中D1 行的時間代價為O（logrbatchNum）［14］（r 為基數(shù)），D2-D4 行并行執(zhí)行的時間開銷為O（1）.因此，總時間開銷ti在最好情況下為O（batchNum/（bucketNum·b）+ logrbatchNum），在最壞情況下為O（batchNum/b+logrbatchNum））.

3.2 空間開銷

文中從總空間開銷和表擴展的開銷兩個方面來分析.

1）總空間開銷.在GPU 上建立的哈希索引，如2.1 節(jié)所述，其顯存的開銷S 主要包括段表空間SsegList、桶表空間SbucketList和桶空間Sbucket.

若m 條記錄占有桶數(shù)L（m）≈m/（bln 2）［16］，則占有空間Sbucket=bL（m）≈m/ln2，桶表所需空間SbucketList為O（m（1+1/b）/b）［17］，段表空間SsegList為O（m（1+1/b）/（Nb）），總空間S 為O（m/ln2+m（1+1/b）/b+m（1+1/b）/（Nb））.

2）表擴展的開銷.假設分裂桶產(chǎn)生a 個桶段的擴展，0≤a≤M（M 為擴展前桶的段數(shù)，即段表長度），則段表增加M 項，桶表增加aN 項（N 為每段桶表的長度），共擴展M+aN 項.若無段表僅有桶表，則表項要增加MN 項.

（1）當數(shù)據(jù)傾斜，分裂的桶不多，即a?M 時，雙層表結(jié)構(gòu)中表的擴展是線性的，而單層表結(jié)構(gòu)中表的擴展是二次的，更加劇烈；

（2）當數(shù)據(jù)均勻分布，每段都有桶分裂，即a≈M時，雙層結(jié)構(gòu)表的擴展接近M+MN 項，單層結(jié)構(gòu)表的擴展接近MN 項，而M?MN，因此這種情況下，雙層結(jié)構(gòu)比單層結(jié)構(gòu)多的表項也是有限的.

4 實驗

實驗在CPU+GPU 的異構(gòu)平臺上進行，CPU 為Intel Core i7-4770k，四核3.50 GHz 主頻，GPU 為NVIDIA GeForce GTX 770，1536 CUDA Cores，每個核的頻率為1.19 GHz，顯存容量為4 GB.集成開發(fā)環(huán)境為VisioStudio2010，GPU 開發(fā)工具包為CUDA5.5.

文中設計兩部分實驗，分別從時間和空間兩個方面檢驗gEHT 算法的有效性.測試數(shù)據(jù)集是隨機產(chǎn)生的鍵值對構(gòu)成的記錄，每條記錄平均長度為10B，每桶的記錄容量b 為64 條，初始桶的總數(shù)M×N 為8×1024.

實驗1對比Lea 算法、RSO 算法、GBLHT 算法和gEHT 算法在數(shù)據(jù)操作上的時間性能，其中Lea算法和RSO 算法均采用4 線程.

在包含90%的查詢數(shù)據(jù)、6%的插入數(shù)據(jù)和4%的刪除數(shù)據(jù)的負載下，4 種算法的吞吐量如圖4所示.在4 線程算法中，鎖沖突對Lea 算法帶來的影響不大，其性能略高于RSO 算法.RSO 算法和gEHT算法的性能都會隨著數(shù)據(jù)量的增加而有所波動，這是因為表收縮或擴展的時間損耗使其吞吐量下降.GBLHT 算法采用的線性哈希及前述優(yōu)化問題，使其性能略低于gEHT 算法.總的來說，隨著負載的增加，GBLHT 和gEHT 算法充分利用了GPU 的計算能力，顯著地提高了吞吐量.

圖4 不同負載下4 種算法的吞吐量Fig.4 Throughputs of four algorithms under different loads

實驗2測試Fagin 的EH(Extendible Hashing)算法和gEHT 算法隨著數(shù)據(jù)的插入表擴展所占用的空間情況.

圖5 表的大小與插入數(shù)據(jù)量的關(guān)系Fig.5 Directory size versus number of insertions

如圖5所示，EH 算法在擴展表時，表長成倍增長，而gEHT 算法接近線性的增長,并且隨著插入數(shù)據(jù)的增加，表空間擴展的速度放緩，甚至小于EH 算法的表空間大小.這是因為隨著表空間的擴大，更多的段表項指向相同的桶表,越來越多的桶表被重用，以致盡管gEHT 算法比EH 算法多出段表，其總的表空間大小也不會超過EH 算法.

5 結(jié)論

可擴展哈希是一種具有最快檢索速度的動態(tài)哈希，文中利用GPU 實現(xiàn)了可擴展哈希算法gEHT.首先利用GPU 的計算能力和CUDA 的編程模型，設計并實現(xiàn)了哈希表的創(chuàng)建、索引的更新以及數(shù)據(jù)檢索的高并發(fā)算法；為了克服表長增長劇烈的缺陷，文中采用二級表結(jié)構(gòu)，使得段表能重用部分桶表，大大地節(jié)省了表結(jié)構(gòu)對空間的需求.最后，通過實驗驗證了gEHT 算法的性能.

顯存空間十分有限，文中討論的算法都是在待處理數(shù)據(jù)能夠全部放在顯存中的前提下進行處理的.大數(shù)據(jù)的特征使得批量處理的數(shù)據(jù)量更大，當其大于顯存容量時，又應該如何在GPU 上使用哈希索引，是下一步要考慮的問題.

［1］Du H C，Ghanta S，Maly K J，et al.An efficient file structure for document retrieval in the automated office environment ［J］.IEEE Transactions on Knowledge and Data Engineering，1989，1(2)：258-273.

［2］Fagin Ronald，Nievergelt Jurg，Pippenger Nicholas，et al.Extendible hashing：a fast access method for dynamic files［J］.ACM Transactions on Database Systems，1979，4(3)：315-344.

［3］Lirwzn W.linear hashing：a new tool for files and table addressing ［C］//Proceedings of the 6th Conference on VLDB.Montreal：VLDB Endowment，1980：212-223.

［4］Ellis C S.Concurrency in linear hashing ［J］.ACM Transactions on Database Systems，1987，12(2)：195-217.

［5］Hsu M，Yang W.Concurrent operations in extendible hashing［C］//Proceedings of the 12th Conference on VLDB.Kyoto：Morgan Kaufmann Publishers Inc，1986：241-247.

［6］Kumar Vijay.Concurrent operations on extendible hashing and its performance ［J］.Communications of the ACM，1990，33(6)：681-694.

［7］Lea D.Hash table util.con current.concurrent hash map，revision 1.25，in JSR-166，the proposed Java Concurrency package ［EB/OL］.(2013-12-01)［2014-03-10］.http：//gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/.

［8］Gao H，Groote J F，Hesselink W H.Almost wait-free resizable hashtables［C］//Proceedings of the 18th International Parallel and Distributed Processing Symposium.Santa Fe：IEEE，2004：681-689.

［9］Shalev Ori，Shavit Nir.Split-ordered lists：lock-free extensiblehash tables (poster paper) ［J］.Journal of the ACM，2006，53(3)：379-405.

［10］Zhang D，Larson P-A.LHlf：lock-free linear hashing［C］//Proceedings of the 17th ACM SIGPLAN Symposium on Principles＆Practice of Parallel Programming.New York：ACM，2012：307-308.

［11］陳虎，唐海浩，廖江苗，等.面向批量插入優(yōu)化的并行存儲引擎MTPower ［J］.計算機學報，2010，33(8)：1492-1499.Chen Hu，Tang Hai-hao，Liao Jiang-miao，et al.MTPower：a parallel database storage engine for batch insertion［J］.Chinese Journal of Computers，2010，33(8)：1492-1499.

［12］黃玉龍，奚建清，張平健，等.GBLHT：一種GPU 加速的批量插入線性哈希表［J］.華南理工大學學報：自然科學版，2012，40(4)：49-56.Huang Yu-long，Xi Jian-qing，Zhang Ping-jian，et al.GBLHT：a GPU-accelerated linear Hash table with batch insertion ［J］.Journal of South China University of Technology：Natural Science Edition，2012，40(4)：49-56.

［13］NVIDIA Corporation.NVIDIA CUDA programming guide version 4.2［EB/OL］.(2012-04-16)［2014-03-10］.http：//docs.nvidia.com/cuda/cuda-c-programming-guide/index.html#ixzz3I5UFqJtq.

［14］Bell N，Hoberock J.Thrust：a productivity-oriented library for CUDA［EB/OL］.(2012-12-10)［2014-03-10］.http：//cloud.github.com/downloads/thrust/thrust/Thrust% 3A%20A% 20Productivity-Oriented% 20Library% 20for%20CUDA.pdf.

［15］Leung S-T.Array restructuring for cache locality ［R］.Seattle：Department of Computer Science and Engineering，University of Washington，1996.

［16］Enbody R J，Du H C.Dynamic hashing schemes ［J］.ACM Computing Surveys，1988，20(2)：85-113.

［17］Gonnct G H.算法和數(shù)據(jù)結(jié)構(gòu)手冊［M］.張子讓，周曉東，譯，北京：人民郵電出版社，1988.