李鵬飛，張坤龍，康超凡

（天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津300072）

基于低沖突幫助機(jī)制的快速無等待哈希表算法

李鵬飛，張坤龍，康超凡

（天津大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津300072）

針對現(xiàn)有無等待哈希表算法未充分利用哈希表的固有并行性，造成線程之間存在高沖突和高冗余的問題，提出一種快速無等待哈希表算法。利用可凍結(jié)集合思想簡化哈希表操作，采用CAS原子指令保證插入、刪除與查找操作均為無等待。根據(jù)哈希表結(jié)構(gòu)改進(jìn)幫助機(jī)制，使得哈希桶的實(shí)現(xiàn)為無等待，只有在擴(kuò)展哈希表時(shí)哈希桶之間才提供幫助。實(shí)驗(yàn)結(jié)果表明，該算法能降低線程操作間的沖突，提高幫助操作的并行度，當(dāng)查找率為0、鍵值范圍為0～256且線程數(shù)為8時(shí)，其吞吐率是現(xiàn)有無等待哈希表算法的2.5倍。

并發(fā)數(shù)據(jù)結(jié)構(gòu)；哈希表；無等待；可線性化；可擴(kuò)展

1 概述

在各種并發(fā)數(shù)據(jù)結(jié)構(gòu)中，哈希表因能夠在常數(shù)時(shí)間內(nèi)完成操作而得到應(yīng)用廣泛。哈希表按照存儲結(jié)構(gòu)可分為封閉地址（closed address）哈希表和開放地址（open address）哈希表。前者元素存儲在稱為桶（bucket）的結(jié)構(gòu)中，桶中可存放多個(gè)元素；后者元素存儲在槽（slot）中，一個(gè)槽只能存放一個(gè)元素。哈希表通過散列函數(shù)將操作分散到不同的桶或槽，這使得彼此間的操作沒有沖突，這就是固有并行性。如果哈希表能動(dòng)態(tài)地?cái)U(kuò)張和收縮，則具有可擴(kuò)展性。

2014年，Liu Yujie等人提出了動(dòng)態(tài)可擴(kuò)展的非阻塞封閉地址哈希表算法［1］，包括無鎖（lock-free）哈希表算法和無等待（wait-free）哈希表算法。無鎖和無等待［2］都具有非阻塞特性：一個(gè)線程的延遲不會(huì)影響其他線程的操作。其中無等待的演進(jìn)性最強(qiáng)，它保證即使在其他線程干擾的情況下，每個(gè)線程都能在有限步內(nèi)完成。

研究發(fā)現(xiàn)，雖然文獻(xiàn)［1］中的無等待哈希表算法是目前性能最好的算法，但其性能卻受到抑制。原因是該算法存在過多不必要的幫助，而且利用全局計(jì)數(shù)器來協(xié)調(diào)幫助造成了高爭用。為了提升性能，文獻(xiàn)［1］采用快路徑慢路徑（Fastpath/Slow path）機(jī)制［3］。其核心思想是盡可能地運(yùn)行在無鎖階段（快路徑），無等待階段（慢路徑）只是用來保證無等待特性，以此提升性能。然而，這種提升方法并沒有從根本上解決無等待算法的性能瓶頸問題。為此，本文提出一種新的無等待哈希表算法，該算法要求哈希桶的實(shí)現(xiàn)是無等待的，并且只在哈希表調(diào)整時(shí)才提供幫助，從而充分利用哈希表的固有并行性。

2 相關(guān)工作

哈希表一直是熱門的研究課題。在順序數(shù)據(jù)結(jié)構(gòu)中，哈希表算法層出不窮。然而，在共享數(shù)據(jù)結(jié)構(gòu)中，并發(fā)環(huán)境下，非阻塞的哈希表算法仍是屈指可數(shù)。

文獻(xiàn)［4］提出無鎖封閉地址哈希表算法。該算法使用改進(jìn)的Harris無鎖鏈表［5］作為桶，通過散列函數(shù)將操作映射到相應(yīng)桶上進(jìn)行。算法能和內(nèi)存管理方法相適應(yīng)。然而，該算法不是可擴(kuò)展的。

文獻(xiàn)［6］提出動(dòng)態(tài)可擴(kuò)展的無鎖封閉地址哈希表算法。但是該算法基于DCAS（Double Compare and Sw ap）原子指令［7］，DCAS在目前硬件結(jié)構(gòu)中還不支持，而且軟件模擬開銷太大。

文獻(xiàn)［8］提出動(dòng)態(tài)可擴(kuò)展的無鎖開放地址哈希表算法。該算法在調(diào)整時(shí)有2個(gè)表：當(dāng)前的舊哈希表和擴(kuò)展后的新哈希表。在功能調(diào)整過程中，先標(biāo)記舊哈希表中的數(shù)據(jù)元素，然后將標(biāo)記的元素拷貝到新哈希表中，最后將完成拷貝的舊哈希表元素設(shè)置為特殊值，表示已被遷移。哈希表的操作在當(dāng)前的舊哈希表上進(jìn)行，一旦發(fā)現(xiàn)被標(biāo)記的數(shù)據(jù)元素，就參與調(diào)整操作。調(diào)整結(jié)束后，新的哈希表成為當(dāng)前的舊哈希表。該算法是真正意義上的可擴(kuò)展哈希，可是該文中并沒有給出算法的性能信息。

文獻(xiàn)［9］提出無鎖開放地址哈希表算法。該算法不具有可擴(kuò)展性，但是可以重復(fù)利用元素刪除后的空間，是空間有效的。

文獻(xiàn)［10］提出遞歸有序劃分可擴(kuò)展哈希表算法，該算法的擴(kuò)展方式為：不在桶內(nèi)插入元素，而是在元素間插入桶。算法基于一個(gè)無鎖的有序鏈表［5］和一個(gè)目錄結(jié)構(gòu)。鏈表中的元素分為數(shù)據(jù)元素和索引元素，這兩者之間用最高位區(qū)分。元素按照它們的二進(jìn)制比特位反轉(zhuǎn)后排序，這樣索引元素就實(shí)現(xiàn)了數(shù)據(jù)元素的有序劃分。算法先在目錄結(jié)構(gòu)上找到相應(yīng)的桶（沒有則建立），然后通過桶找索引元素，若該索引元素的父索引還沒建立，就遞歸建立。但是該算法并沒有提供收縮的特性，而且索引元素一經(jīng)建立就永不刪除，并且算法還對內(nèi)存的大小做了假設(shè)。

文獻(xiàn)［11］采用完美哈希（perfect hash）的思想構(gòu)造無等待可擴(kuò)展哈希映射算法，能輕易實(shí)現(xiàn)哈希表。該算法使用一個(gè)桶數(shù)組，結(jié)構(gòu)類似樹：每個(gè)桶要么是一個(gè)數(shù)據(jù)項(xiàng)（葉子結(jié)點(diǎn)），要么指向一個(gè)數(shù)組（中間結(jié)點(diǎn)）。然而，算法實(shí)現(xiàn)的哈希表大小有上限，不是嚴(yán)格意義上可擴(kuò)展的。

文獻(xiàn)［12］提出無鎖布谷哈希算法。布谷哈希（cuckoo hash）是開放地址哈希算法，使用2個(gè)獨(dú)立的哈希表，每個(gè)哈希表有不同的散列函數(shù)。布谷哈希處理沖突時(shí)將某個(gè)表里存在的元素剔除，將新元素放入，而后將剔除的元素在另一個(gè)表上做類似操作，重復(fù)這個(gè)過程直到找到空槽將元素放入。無鎖布谷哈希算法使用邏輯時(shí)鐘策略解決查找丟失問題。插入操作使用幫助機(jī)制，保證了非阻塞特性。然而，該算法沒有提供可擴(kuò)展的功能，而且在最壞情況下，查找操作并不能在常數(shù)時(shí)間內(nèi)完成。

動(dòng)態(tài)可擴(kuò)展的非阻塞封閉地址哈希表算法［1］的實(shí)現(xiàn)建立在抽象的可凍結(jié)集合上?？蓛鼋Y(jié)集合提供凍結(jié)操作，集合在凍結(jié)之后，任何更新操作將會(huì)失敗?？蓛鼋Y(jié)集合可以由當(dāng)前最新的無序鏈表實(shí)現(xiàn)［13］，也可以使用數(shù)組實(shí)現(xiàn)，以提高緩存特性。該算法有新表和舊表2個(gè)操作位置，2個(gè)表中的桶都由可凍結(jié)集合實(shí)現(xiàn)。在哈希表調(diào)整時(shí)，凍結(jié)舊表中的相應(yīng)桶，使用寫時(shí)復(fù)制（copy on w rite）機(jī)制，將桶中元素遷移至新表中的桶。元素遷移完后，新建一個(gè)空表，根據(jù)調(diào)整是擴(kuò)張還是收縮設(shè)定空表的大小，然后將舊表置為空。此時(shí)新表成為“舊”表，新建的空表成為“新”表。算法通過哈希表在調(diào)整時(shí)維護(hù)新表和舊表的不變式關(guān)系，保證了操作的正確性。

3 算法設(shè)計(jì)

3.1 基本設(shè)計(jì)思想

無等待算法被認(rèn)為是低效和難以實(shí)現(xiàn)的［14］，其很大原因在于幫助機(jī)制的設(shè)計(jì)［15］。大多數(shù)幫助機(jī)制存在兩大缺陷：高沖突和高冗余［3］。在執(zhí)行自己的操作之前，先幫助其他的線程，通常造成線程之間的高沖突。其實(shí)在大多數(shù)情況下，如果給定足夠的時(shí)間，一個(gè)線程能自己完成操作。幫助機(jī)制必須設(shè)計(jì)成操作順序一致，即并發(fā)幫助某個(gè)操作的線程執(zhí)行過程是一樣的，而該操作只能被正確的執(zhí)行一次，這樣就造成了高冗余。

文獻(xiàn)［1］中的無等待算法使用一個(gè)全局共享的幫助數(shù)組，通過優(yōu)先級決定幫助的次序，從而保證無等待特性。每個(gè)線程在完成自己的操作之前先掃描幫助數(shù)組，幫助完成優(yōu)先級比自己高的操作。這種幫助機(jī)制沒有考慮到封閉地址哈希表這種特殊的數(shù)據(jù)結(jié)構(gòu)：哈希表具有雙重結(jié)構(gòu)，包括哈?？蚣芎痛娣艛?shù)據(jù)元素的桶。使用這種幫助機(jī)制，本來映射到不同桶上毫不相干的2個(gè)操作因?yàn)閮?yōu)先級的原因而不得不建立聯(lián)系，沒有充分利用哈希表的固有并行性，造成線程之間的高沖突和高冗余。

本文采用文獻(xiàn)［1］的可凍結(jié)集合思想，使用CAS（Com pare and Sw ap）原子指令來實(shí)現(xiàn)無等待特性。為了更充分地利用哈希表的固有并行性，算法重新設(shè)計(jì)了幫助機(jī)制，具體表現(xiàn)在以下2個(gè)方面：（1）算法要求桶的實(shí)現(xiàn)必須是無等待的。然而與此不同的是文獻(xiàn)［1］中桶的實(shí)現(xiàn)只要求無阻塞，一些快速的無鎖鏈表算法，比如無鎖鏈表算法［5］、LFList鏈表算法［13］與自組織鏈表算法［16］等均能夠適用。（2）只有在哈希表進(jìn)行調(diào)整時(shí)，哈希表上才提供幫助，而且只有調(diào)整線程才能幫助其他未完成操作的線程。這樣在不同桶上做操作的線程之間不會(huì)相互干擾，降低了沖突，而只在必要時(shí)才提供幫助的策略提升了操作的并行度。

3.2 算法描述

3.2.1 集合中使用的結(jié)構(gòu)

集合中使用的結(jié)構(gòu)具體如下：

3.2.2 哈希表中使用的結(jié)構(gòu)

哈希表中使用的結(jié)構(gòu)具體如下：

3.3 算法分析

在文獻(xiàn)［1］的基礎(chǔ)上，可凍結(jié)集合算法中，record FSet增加了共享數(shù)組B，用于同一桶內(nèi)的線程間相互幫助。函數(shù)Invoke是提供給上層的接口，插入和刪除操作在FSet上通過調(diào)用Invoke而發(fā)生作用，更新集合（L50～L51，L50表示算法中代碼的第50行，下同），然后通過GetResponse獲取操作結(jié)果。查找操作通過調(diào)用HasM ember獲得查找結(jié)果。只有當(dāng)FSet中的元素需要遷移時(shí)才會(huì)調(diào)用Freeze。Freeze操作首先將可凍結(jié)標(biāo)記置為true，隨后調(diào)用DoFreeze凍結(jié)集合。Invoke中發(fā)現(xiàn)可凍結(jié)標(biāo)記改變（L6），也幫助做凍結(jié)操作（L7）。

在哈希表算法中，插入和刪除操作通過調(diào)用Apply獲得相應(yīng)的桶，若桶為空，則先進(jìn)行收集（L90）。Apply調(diào)用期間，除了在同一個(gè)桶上調(diào)用Invoke而幫助相關(guān)線程之外，未做其他不相干的操作，提高了并行度。如果達(dá)到某種條件（L54，L59），則調(diào)用Resize對哈希表作調(diào)整（L55，L60）。Resize操作首先調(diào)用InitBucket對當(dāng)前表（新表）做收集，將舊表中的元素遷移到新表中空的桶中（L97）。然后將指向舊表的指針置為空（L78），此時(shí)元素已全部遷移完成。最后新建一個(gè)空表，表的大小根據(jù)調(diào)整類型選擇（L79），通過CAS原子操作使其成為新表（L82），收集后的表相應(yīng)地成為舊表。

如果給定足夠的時(shí)間，一個(gè)線程可能已經(jīng)完成而并不需要其他線程的幫助：只有在必要時(shí)提供幫助才是合理的?；诖耍碌臒o等待哈希表算法增加了函數(shù)HelpWhenResize（L108～L114），這是整個(gè)算法的關(guān)鍵。文獻(xiàn)［1］中的算法不論操作是否在同一個(gè)桶上，只要優(yōu)先級高于自己，就無條件幫助完成，很多時(shí)候這種幫助是不必要的。這樣做的原因是為了保證無等待特性：防止其他線程在不斷地調(diào)整而導(dǎo)致自己的操作始終不能完成的情況發(fā)生。函數(shù)HelpWhen Resize掃描哈希表的共享數(shù)組A中發(fā)布的操作（L109～L110），如果操作沒完成（L111）且在當(dāng)前桶上操作（L113），則在桶上幫助完成（L114）。函數(shù)HelpWhenResize只在調(diào)整時(shí)被調(diào)用（L77），不會(huì)出現(xiàn)線程由于調(diào)整干擾而不能完成的情形。

4 正確性證明

在并發(fā)環(huán)境下，正確性既包含了安全性（safety），也包含了活性（liveness）。所謂安全性，是指該數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)了一個(gè)抽象數(shù)據(jù)結(jié)構(gòu)，例如集合，并且實(shí)現(xiàn)是可線性化的（linearizable）［17］。并發(fā)系統(tǒng)的一次執(zhí)行過程可以采用經(jīng)歷（history）模型來描述。經(jīng)歷是方法調(diào)用事件和響應(yīng)事件的一個(gè)有限序列?？删€性化隱含的基本思想是每個(gè)并發(fā)經(jīng)歷都等價(jià)于某個(gè)順序經(jīng)歷，這樣就將并發(fā)過程映射為順序過程。所謂活性，也叫演進(jìn)性，在使用鎖的結(jié)構(gòu)上指的是無死鎖，無饑餓；在不使用鎖的結(jié)構(gòu)上指的是非阻塞特性。本文將從可線性化性和無等待特性2個(gè)方面進(jìn)行證明。

4.1 可線性化特性

定義 集合中的元素來自哈希表新表、舊表中的元素，從哈希表元素到集合元素的映射關(guān)系定義如下：

（1）若新表中的桶b不為空，則桶b中元素屬于集合。

（2）若新表中的桶b為空，且新表的大小是舊表的2倍，則舊表中滿足L99～L100的桶中元素屬于集合。

（3）若新表中的桶b為空，且舊表的大小是新表的2倍，則舊表中滿足L102～L104的2個(gè)桶中元素屬于集合。

引理1 插入或刪除操作的可線性化的點(diǎn)在Invoke返回true時(shí)刻，即操作完成時(shí)刻L49。

引理2 查找操作的可線性化的點(diǎn)：若桶不是凍結(jié)的，則取在HasM ember（L71）上；否則，桶一定被某個(gè)Freeze操作凍結(jié)，可線性化的點(diǎn)取Freeze將凍結(jié)標(biāo)記fflag設(shè)置為true（L19）或獲取哈希表新表（L63）這2個(gè)操作中發(fā)生較晚的一個(gè)。

定理1 哈希表實(shí)現(xiàn)的抽象數(shù)據(jù)結(jié)構(gòu)是集合。

證明：由引理1可知，在可線性化點(diǎn)對桶（FSet）進(jìn)行插入操作：要么桶里沒有插入操作的元素（L43結(jié)果為true），于是桶里增加了一個(gè)元素（L44）；要么L43結(jié)果為false，桶與先前一樣。在可線性化點(diǎn)對桶進(jìn)行刪除操作：要么桶里沒有刪除操作的元素（L47結(jié)果為false），桶與先前一樣；要么L47結(jié)果為true，于是桶里減少了一個(gè)元素（L47）。對于查找操作，由引理2可知，在調(diào)用HasM ember（b，k）返回操作結(jié)果時(shí)，對于操作的桶b（一定不為空），可能出現(xiàn)以下情況：（1）桶b沒有被凍結(jié)，則桶b所在的表要么是新表，要么是舊表且新表的相應(yīng)桶為空；由定義可知，相關(guān)元素在桶b中。（2）桶b被凍結(jié)，則桶b所在的表一定是舊表或已過時(shí)（既不是新表，又不是舊表）。若桶被凍結(jié)在執(zhí)行L63之前，則執(zhí)行L63時(shí)，將從L66獲得桶b，由定義可知，相關(guān)元素在桶b中。若桶被凍結(jié)在執(zhí)行L63之后，則直到桶b被凍結(jié)的時(shí)刻，桶b在舊表中且新表的相應(yīng)桶為空，由定義可知，相關(guān)元素在桶b中。

4.2 無等待特性

引理3 一旦FSet的凍結(jié)標(biāo)記fflag設(shè)置為true，則經(jīng)過有限的操作步，F(xiàn)Set將被凍結(jié)（即執(zhí)行L33成功）。

引理4 成為FSet的操作節(jié)點(diǎn)（執(zhí)行L12成功）的更新操作節(jié)點(diǎn)，在有限步內(nèi)不是自己完成就是別人幫助完成。

定理2 集合算法是無等待的。

證明：觀察3.2節(jié)中的集合算法，發(fā)現(xiàn)只有函數(shù)DoFreeze與函數(shù)Invoke中有while循環(huán)。只有將凍結(jié)標(biāo)記置為true才會(huì)調(diào)用函數(shù)DoFreeze，根據(jù)引理3，函數(shù)DoFreeze將在有限步內(nèi)完成。函數(shù)Invoke中退出循環(huán)的條件是當(dāng)前操作完成或該集合被凍結(jié)（L5）。若集合沒被凍結(jié)，當(dāng)前操作執(zhí)行L12不能成功的原因是其他線程不斷地干擾。假設(shè)線程總數(shù)為P，因?yàn)橛袔椭鷶?shù)組B，線程調(diào)用Invoke都會(huì)掃描一遍數(shù)組（L3），操作完成的線程再次運(yùn)行時(shí)一定會(huì)發(fā)現(xiàn)這個(gè)未完成的操作，則最多經(jīng)過P次操作完成，未完成的操作一定成為FSet的操作節(jié)點(diǎn)，由引理4可知，當(dāng)前操作能在有限步內(nèi)完成。若集合被凍結(jié)，則直接退出循環(huán)。

定理3 哈希表算法是無等待的。

證明：觀察3.2節(jié)中的哈希表算法，發(fā)現(xiàn)只有函數(shù)Apply中有while循環(huán)。函數(shù)Apply不能結(jié)束的原因是操作始終沒有完成。若哈希表沒有發(fā)生調(diào)整，則每次調(diào)用函數(shù)Invoke將作用在同一個(gè)桶上，由定理2可知，函數(shù)Apply將在有限步內(nèi)完成。若哈希表發(fā)生調(diào)整，函數(shù)HelpW henResize將掃描整個(gè)幫助數(shù)組（L109），調(diào)整線程將幫助未完成的操作。

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

實(shí)驗(yàn)在4核8線程（3.5 GHz，一級緩存64 KB，二級緩存256 KB）64 bit英特爾i7-4770K機(jī)器上進(jìn)行，算法全都用Java實(shí)現(xiàn)。實(shí)驗(yàn)環(huán)境：Linux操作系統(tǒng)CentOS release 6.5，Java版本1.7.0-60。

實(shí)驗(yàn)的4個(gè)算法均是無等待的。其中，WFList是文獻(xiàn)［1］中的算法，用文獻(xiàn)［13］中的無鎖無序鏈表實(shí)現(xiàn)桶；FastWFList是本文提出的算法，用文獻(xiàn)［13］中的無等待無序鏈表實(shí)現(xiàn)桶；WFArray是文獻(xiàn)［1］中算法的數(shù)組實(shí)現(xiàn)；FastWFA rray是本文算法的數(shù)組實(shí)現(xiàn)。

實(shí)驗(yàn)以吞吐率作為性能指標(biāo)，為了避免調(diào)整操作對算法性能的影響，插入與刪除操作的比率相同。操作數(shù)據(jù)在鍵值范圍內(nèi)隨機(jī)生成。初始時(shí)哈希表中預(yù)先插入個(gè)數(shù)為鍵值范圍一半的數(shù)據(jù)。實(shí)驗(yàn)參數(shù)如下：（1）函數(shù)contains，insert，remove的調(diào)用百分比有2種情況：1）0，50%，50%；2）80%，10%，10%。根據(jù)函數(shù)調(diào)用比例，線程隨機(jī)地選擇操作類型，主要考察沖突、爭用的高低對算法性能的影響。（2）線程數(shù)目為1～8。（3）鍵值范圍為0～256，0～65 536。主要考察鍵值范圍大小對算法性能的影響。以上共4組實(shí)驗(yàn)，每組實(shí)驗(yàn)運(yùn)行5次，每次運(yùn)行5 s，最終結(jié)果取平均值。實(shí)驗(yàn)數(shù)據(jù)的標(biāo)準(zhǔn)偏差可忽略。實(shí)驗(yàn)結(jié)果見圖1～圖4。

圖1 查找率為0、鍵值范圍為0～256時(shí)的算法吞吐率

圖2 查找率為0、鍵值范圍為0～65 536時(shí)的算法吞吐率

圖3 查找率為80%、鍵值范圍為0～256時(shí)的算法吞吐率

圖4 查找率為80%、鍵值范圍為0～65 536時(shí)的算法吞吐率

從圖1～圖4可以看出，本文算法的性能優(yōu)于文獻(xiàn)［1］算法，無論是鏈表實(shí)現(xiàn)還是數(shù)組實(shí)現(xiàn)。在相同的鍵值范圍，查找率大的吞吐率較高。原因是查找并不改變集合元素，沒有線程間的相互干擾，而且查找也不需要幫助，在相同時(shí)間內(nèi)所做的操作更多。查找率為0時(shí)，各線程之間的競爭激烈。在圖1中，隨著線程數(shù)的增加，新算法的性能與文獻(xiàn)［1］算法的性能差距越來越大，在線程數(shù)為8時(shí)吞吐率是其2.5倍。查找率為80%時(shí)，插入操作與刪除操作發(fā)生沖突的概率較低，本文算法利用固有并行的優(yōu)勢減弱，提升的幅度降低。

在圖2中，當(dāng)線程數(shù)大于4時(shí)，本文算法的性能曲線趨于平緩，原因值得進(jìn)一步研究。在小鍵值時(shí)，桶用數(shù)組實(shí)現(xiàn)的一類算法性能優(yōu)于桶用鏈表實(shí)現(xiàn)的一類算法，而在大鍵值時(shí)情況正相反，可能是數(shù)組利用的緩存效應(yīng)在大鍵值時(shí)優(yōu)勢不明顯。

6 結(jié)束語

本文分析了無等待哈希表算法性能差的原因，根據(jù)哈希表的結(jié)構(gòu)改進(jìn)幫助機(jī)制，提出一種快速無等待哈希表算法，能更充分地利用哈希表的固有并行性。實(shí)驗(yàn)結(jié)果表明，該算法提高了無等待哈希表算法的性能下界，最好時(shí)是已知最快算法的2.5倍。下一步工作是分析大鍵值范圍下本文算法性能趨于平緩的原因，以及在實(shí)際應(yīng)用中使用并發(fā)數(shù)據(jù)結(jié)構(gòu)，并結(jié)合多核并行運(yùn)算的優(yōu)勢，進(jìn)一步提高吞吐性能。

［1］ Liu Yujie，Zhang Kunlong，Spear M.Dynamic-sized Nonblocking Hash Tables［C］//Proceedings of 2014 ACM Symposium on Principles of Distributed Computing.Paris，F(xiàn)rance：ACM Press，2014：242-251.

［2］ Herlihy M.Wait-free Synchronization［J］.ACM Transactions on Programming Languages and Systems，1991，13（1）：124-149.

［3］ Kogan A，Petrank E.A Methodology for Creating Fast Wait-free Data Structures［C］//Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming.New York，USA：ACM Press，2012：141-150.

［4］ M ichael M M.High Performance Dynamic Lock-free Hash Tables and List-based Sets［C］//Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures.New York，USA：ACM Press，2002：73-82.

［5］ Harris T L.A Pragmatic Implementation of Non-blocking Linked-lists［C］//Proceedings of the 15th International Conference on Distributed Computing.Berlin，Germany：Springer，2001：300-314.

［6］ Greenwald M.Two-handed Emulation：How to Build Nonblocking Implementations of Complex Data-structures Using DCAS［C］//Proceedings of the 21st Annual Symposium on Principles of Distributed Computing.New York， USA：ACM Press，2002：260-269.

［7］ Luchangco V，Moir M，Shavit N.Nonblocking k-comparesingle-swap［C］//Proceedings of the 15th Annual ACM Symposium on Parallel Algorithms and Architectures. New York，USA：ACM Press，2003：314-323.

［8］ Gao Hui，Groote J F，Hesselink W H.Lock-free Dynamic Hash Tables w ith Open Addressing［J］. Distributed Computing，2005，18（1）：21-42.

［9］ Purcell C，Harris T.Non-blocking Hashtables with Open Addressing［C］//Proceedings of the 19th International Conference on Distributed Computing.Berlin，Germany：Springer，2005：108-121.

［10］ Shalev O，Shavit N.Split-ordered Lists：Lock-free Extensible Hash Tables［J］.Journal of the ACM，2006，53（3）：379-405.

［11］ Feldman S，Laborde P，Dechev D.Concurrent Multilevel Arrays：Wait-free Extensible Hash Maps［C］// Proceedings of International Conference on Embedded Computing System s：Architectures，Modeling，and Simulation.Washington D.C.，USA：IEEE Press，2013：155-163.

［12］ Nguyen D N，Tsigas P.Lock-free Cuckoo Hashing［C］// Proceedings of the 34th International Conference on Distributed Computing Systems.Washington D.C.，USA：IEEE Computer Society，2014：627-636.

［13］ Zhang Kunlong，Zhao Yujiao，Yang Yajun，et al.Practical Non-blocking Unordered Lists［C］//Proceedings of the 27th International Conference on Distributed Computing. Berlin，Germany：Springer，2013：239-253.

［14］ Herlihy M，Shavit N.多處理器編程的藝術(shù)［M］.金 海，胡 侃，譯.北京：機(jī)械工業(yè)出版社，2009.

［15］ Herlihy M，Luchangco V，Moir M.Obstruction-free Synchronization：Double-ended Queues as an Example［C］// Proceedings of the 23rd International Conference on Distributed Computing Systems.Washington D.C.，USA：IEEE Computer Society，2003：522-529.

［16］ 陳春光，張坤龍，譚龍飛，等.并發(fā)非阻塞自組織鏈表算法［J］.計(jì)算機(jī)工程，2013，39（8）：31-37.

［17］ Herlihy M P，W ing J M.Linearizability：A Correctness Condition for Concurrent Objects［J］.ACM Transactions on Programming Languages and System s，1990，12（3）：463-492.

編輯 陸燕菲

Fast Wait-free Hash Table Algorithm Based on Low-conflict Help Mechanism

LI Pengfei，ZHANG Kunlong，KANG Chaofan
（School of Computing Science and Technology，Tianjin University，Tianjin 300072，China）

Existing wait-free hash table algorithms do not take full advantage of the inherent parallelism of hash table，which results in the high redundancy and conflict between threads.In order to solve the problem，this paper proposes a fast wait-free hash table algorithm.It makes use of the freezable set to simplify the operations of hash table.And the Com pare and Swap（CAS）primitive is applied to realize the wait-free of insertion，deletion and search operations.It improves the help mechanism based on the structure of hash table to realize the wait-free of hash buckets.In order to avoid the conflics between the operations on different buckets，the help is given only when the hash table extends.Experimental results show that the algorithm can reduce the conflict between thread operation，and improve the parallelism of help operation.W hen the percentage of lookup is 0，the data range is 0～256 and the thread number reaches 8，throughput of the proposed algorithm is 2.5 times than the existing wait-free hash table algorithm.

concurrent data structure；hash table；wait-free；linearizability；extensibility

李鵬飛，張坤龍，康超凡.基于低沖突幫助機(jī)制的快速無等待哈希表算法［J］.計(jì)算機(jī)工程，2015，41（11）：52-58.

英文引用格式：Li Pengfei，Zhang Kunlong，Kang Chaofan.Fast Wait-free Hash Table Algorithm Based on Low-conflict Help Mechanism［J］.Computing Engineering，2015，41（11）：52-58.

1000-3428（2015）11-0052-07

A

TP311.1

10.3969/j.issn.1000-3428.2015.11.010

國家自然科學(xué)基金資助項(xiàng)目（61303021）；水利部公益性行業(yè)科研專項(xiàng)基金資助項(xiàng)目（201401033）。

李鵬飛（1990-），男，碩士研究生，主研方向：并發(fā)數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)庫技術(shù)；張坤龍，副教授、博士；康超凡，碩士研究生。

2014-10-05

2014-12-15 E-m ail：lpf2013@tju.edu.cn