摘 ?要： HashMap內(nèi)存數(shù)據(jù)結(jié)構(gòu)存在相當(dāng)廣泛的應(yīng)用場景，通過Hash函數(shù)的Key直接獲取對(duì)應(yīng)的值，能夠確保搜索的時(shí)間復(fù)雜度為O（1）。HashMap數(shù)據(jù)結(jié)構(gòu)存在哈希沖突與線程安全問題，悲觀鎖機(jī)制實(shí)現(xiàn)線程安全的方法存在很大的性能開銷。本文提出了基于優(yōu)化的CAS算法，實(shí)現(xiàn)線程安全的哈希映射數(shù)據(jù)結(jié)構(gòu)，內(nèi)部采用數(shù)組、鏈表和紅黑樹實(shí)現(xiàn)了高并發(fā)環(huán)境下讀寫操作。通過增加版本戳避免CAS算法的ABA問題，CAS算法實(shí)現(xiàn)的無鎖方式避免了鎖競爭的開銷，使用紅黑樹來優(yōu)化鏈表，確保大規(guī)模數(shù)據(jù)集的檢索時(shí)間復(fù)雜度保持O（logn）。支持多線程擴(kuò)容操作，在執(zhí)行效率方面有良好的表現(xiàn)。通過大規(guī)模的并發(fā)壓力測(cè)試，驗(yàn)證了該數(shù)據(jù)結(jié)構(gòu)在性能上有穩(wěn)定的提升。

關(guān)鍵詞： 無鎖機(jī)制;分段鎖;CAS算法優(yōu)化;紅黑樹;線程安全

中圖分類號(hào)： TP311.12 ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.06.043

本文著錄格式：吳恩慈. 基于優(yōu)化的CAS算法實(shí)現(xiàn)線程安全的HashMap [J]. 軟件，2019，40（6）：185190

【Abstract】： HashMap data structure is widely used in the industry. The Hash function directly reads the corresponding value through the input key， which ensures that the time complexity of the search algorithm is O（1）. There are hash conflicts and thread safety issues in the HashMap. The pessimistic locking mechanism implements thread safety methods with great performance overhead. This paper proposes a HashMap structure based on optimized CAS algorithm to implement thread safety. The internal use of arrays， linked lists， red-black trees. Achieves read and write efficiency in high-concurrency environments. The CAS algorithm implements lock-free mode to avoid the overhead of lock competition. Red-black trees are used to optimize the linked list， ensuring that the time complexity remains O（logn） when the data set is large. Supports multi-thread expansion operations in a lock-free state， and concurrent processing reduces the time overhead of capacity expansion. Through large-scale concurrent testing， it is verified that the data structure has a stable improvement in performance.

【Key words】： Lock-free; Segment Lock; Optimized CAS; Red-black Tree; Thread-safe

0 ?引言

隨著在線業(yè)務(wù)規(guī)模越來越大，信息系統(tǒng)的并發(fā)操作也越來越大，高并發(fā)一直是業(yè)界面臨的問題。Hash函數(shù)根據(jù)Key直接獲取對(duì)應(yīng)的值，能夠提供時(shí)間復(fù)雜度為O（1）的搜索算法，在很大程度上提高了搜索效率，存在非常廣泛的應(yīng)用場景。另外，大規(guī)模數(shù)據(jù)集下HashMap數(shù)據(jù)結(jié)構(gòu)往往存哈希碰撞，以及高并發(fā)環(huán)境下的線程安全問題。悲觀鎖的安全機(jī)制存在性能瓶頸，不能充分發(fā)揮多核處理器的作用。當(dāng)大量進(jìn)程同時(shí)訪問堆棧時(shí)，會(huì)競爭讀取與更新共享變量，從而導(dǎo)致大量干擾。在各種工作負(fù)載下提供良好性能的并發(fā)算法，通常不使用鎖，并使用各種機(jī)制來減少對(duì)共享內(nèi)存的爭用，增加并行執(zhí)行的可能性。本文在研究相關(guān)文獻(xiàn)與總結(jié)實(shí)際經(jīng)驗(yàn)的基礎(chǔ)上，主要完成了3個(gè)方面的工作。

（1）分析了HashMap內(nèi)存數(shù)據(jù)結(jié)構(gòu)存在哈希沖突與線程安全的問題，指出通過悲觀鎖機(jī)制實(shí)現(xiàn)線程安全的方法存在很大的性能開銷，不適合大規(guī)模、高并發(fā)操作的應(yīng)用場景。

（2）研究了并行HashMap算法與數(shù)據(jù)結(jié)構(gòu)，解析算法實(shí)現(xiàn)中的分段鎖技術(shù)、HashEntry對(duì)象的不變性機(jī)制。分段鎖技術(shù)提高了并行度，同時(shí)也使得數(shù)據(jù)結(jié)構(gòu)也變的復(fù)雜，降低了數(shù)據(jù)一致性的要求。

（3）提出了基于CAS（Compare And Swap）算法實(shí)現(xiàn)線程安全的哈希映射數(shù)據(jù)結(jié)構(gòu)，對(duì)CAS算法存在的問題提出了有針對(duì)性的優(yōu)化策略，并且提供了算法實(shí)現(xiàn)代碼。數(shù)據(jù)結(jié)構(gòu)內(nèi)部采用數(shù)組、鏈表和紅黑樹實(shí)現(xiàn)了高并發(fā)環(huán)境下讀寫操作，該方法有效的減少對(duì)鎖競爭。通過大規(guī)模的并發(fā)測(cè)試，驗(yàn)證了該數(shù)據(jù)結(jié)構(gòu)在性能上有穩(wěn)定的提升。

1 ?相關(guān)工作

文獻(xiàn)[1]采用類似于鏈表的數(shù)據(jù)結(jié)構(gòu)，增加哈希表中每個(gè)相同哈希地址對(duì)應(yīng)存儲(chǔ)空間的Value個(gè)數(shù)，達(dá)到是降低哈希沖突的目的[1]。該方法支持的數(shù)據(jù)集容量有限，很難保證持續(xù)穩(wěn)定的讀取速度。文獻(xiàn)[2]使用內(nèi)容尋址存儲(chǔ)器作公共溢出緩存區(qū)，降低了插入時(shí)哈希沖突的概率，改善了哈希表最壞訪問時(shí)間問題[2]。文獻(xiàn)[3]通過引入外部區(qū)分表實(shí)現(xiàn)完美哈希函數(shù)，在查表操作過程中，首先讀取外部區(qū)分表中當(dāng)前Key對(duì)應(yīng)的區(qū)分位，然后將區(qū)分位合并到當(dāng)前Key后再進(jìn)行哈希函數(shù)求值[3]。該方法缺點(diǎn)是構(gòu)建外部區(qū)分表比較耗時(shí)，不支持新的Key動(dòng)態(tài)插入。文獻(xiàn)[4]提出了一種存儲(chǔ)結(jié)構(gòu)塊列表來存儲(chǔ)沖哈希突數(shù)據(jù)的方法，使用緩存機(jī)制提高Key的檢索效率。該方法在桶數(shù)目充足的情況下能夠有效降低內(nèi)存消耗[4]。文獻(xiàn)[5]研究了發(fā)生哈希沖突的本質(zhì)原因，數(shù)據(jù)元素檢索的先驗(yàn)概率[5]。提出了一種減少了碰撞期間搜索長度和響應(yīng)時(shí)間的方法。

文獻(xiàn)[6]提出了一種基于同步原語CAS的無鎖模式，不會(huì)導(dǎo)致ABA問題與環(huán)繞問題，可為多種數(shù)據(jù)類型提供無鎖功能[6]。在讀寫對(duì)象時(shí)輪詢不同的位置，通過其位置檢查對(duì)象的一致性。文獻(xiàn)[7]提出了一種多線程環(huán)境下的無鎖算法，某個(gè)進(jìn)程在嘗試應(yīng)用操作失敗時(shí)，再次嘗試之前等待，減少并發(fā)系統(tǒng)中對(duì)共享資源的競爭[7]。在許多情況下可以提高吞吐量，采用這種方法來實(shí)現(xiàn)可擴(kuò)展的無鎖操作。文獻(xiàn)[8]研究了Haskell語言中的基于無鎖的同步機(jī)制，實(shí)現(xiàn)任務(wù)池模式的不同實(shí)例，通過合成算法與LU分解來檢查其的性能[8]，結(jié)果表明無鎖任務(wù)池的并行性能存在明顯的優(yōu)勢(shì)。文獻(xiàn)[9]提出了一種無鎖的并發(fā)堆棧抽象模型，減少了堆棧上的鎖爭用，允許并行執(zhí)行多對(duì)推送和彈出操作，并行操作可以轉(zhuǎn)換為可線性化的抽象模型[9]。文獻(xiàn)[10]提出了基于無鎖隊(duì)列實(shí)現(xiàn)并發(fā)組合的算法，推導(dǎo)可伸縮堆棧算法，簡化了無鎖算法實(shí)現(xiàn)，且更加易于理解[10]。

2 ?問題分析

2.1 ?HashMap線程安全問題

HashMap內(nèi)部使用數(shù)組保存鍵值對(duì)數(shù)據(jù)，插入一個(gè)新的鍵值對(duì)時(shí)，根據(jù)Key的哈希值對(duì)數(shù)組的大小取模，計(jì)算結(jié)果作為數(shù)組的下標(biāo)，把鍵值對(duì)插入到數(shù)組的該位置。如果數(shù)組的該位置上已經(jīng)存在元素，表明產(chǎn)生了哈希沖突問題，需要在該位置生成鏈表數(shù)據(jù)結(jié)構(gòu)。哈希沖突最嚴(yán)重的情況，所有元素都定位到數(shù)組的同一個(gè)下標(biāo)位置，生成一個(gè)很大的鏈表結(jié)構(gòu)，檢索某個(gè)Key需要遍歷鏈表的所有節(jié)點(diǎn)，時(shí)間復(fù)雜度變成O（N）。

在多線程環(huán)境且未作同步的情況下，對(duì)同一個(gè)HashMap做寫入操作，可能導(dǎo)致兩個(gè)或以上線程同時(shí)做Rehash動(dòng)作，可能導(dǎo)致循環(huán)鍵表出現(xiàn)，一旦出現(xiàn)線程將無法終止。當(dāng)另外一個(gè)線程獲取循環(huán)鏈表的Key的時(shí)候，Get動(dòng)作會(huì)一直執(zhí)行，導(dǎo)致越來越多的線程死循環(huán)，最后服務(wù)器資源被耗盡。另外，插入一個(gè)新節(jié)點(diǎn)前，需要確定當(dāng)前內(nèi)部元素是否達(dá)到設(shè)定的閾值，如果達(dá)到閾值則需要進(jìn)行擴(kuò)容操作。鏈表中的元素是散列分布的，在多線程高并發(fā)環(huán)境下，擴(kuò)容操作時(shí)可能會(huì)引發(fā)鏈表結(jié)構(gòu)循環(huán)，引起服務(wù)器CPU消耗在短時(shí)間內(nèi)急劇上升。

2.2 ?悲觀鎖的性能問題

HashMap數(shù)據(jù)結(jié)構(gòu)存在線程安全問題，不考慮性能時(shí)通過對(duì)整個(gè)哈希表結(jié)構(gòu)做鎖定操作。鎖定期間其他線程一直處于阻塞狀態(tài)。很顯然，不適合大規(guī)模高并發(fā)操作。高效的哈希函數(shù)能夠在確保計(jì)算效率的前提下，使得散列地址相對(duì)均勻的分布，當(dāng)前使用的哈希函數(shù)很難達(dá)到預(yù)期效果。數(shù)組初始化時(shí)要申請(qǐng)一個(gè)連續(xù)的固定長度內(nèi)存空間，哈希函數(shù)很難保證生成的哈希值不發(fā)生沖突。

悲觀鎖實(shí)際上是將并發(fā)請(qǐng)求轉(zhuǎn)變?yōu)榇衼韺?shí)現(xiàn)，對(duì)系統(tǒng)的響應(yīng)時(shí)間和吞吐量有較大影響，并發(fā)控制鎖也是阻止線程執(zhí)行的悲觀方法。當(dāng)一個(gè)線程被掛起時(shí)就會(huì)加入到阻塞隊(duì)列，在特定條件下通過Notify方法喚醒。共享資源不可用的時(shí)，該線程將讓渡CPU切換為阻塞狀態(tài)。等到共享資源可用時(shí)，喚醒線程進(jìn)入Runnable狀態(tài)等待CPU調(diào)度，線程掛起和恢復(fù)的執(zhí)行過程中存在著很大的開銷。

3 ?分段鎖算法

3.1 ?分段鎖的數(shù)據(jù)結(jié)構(gòu)

如圖1所示，分段鎖實(shí)現(xiàn)的線程安全的HashMap數(shù)據(jù)結(jié)構(gòu)，內(nèi)部結(jié)構(gòu)包括一個(gè)Segment數(shù)組和多個(gè)Hash Entry對(duì)象，通過鎖分離的方法提供并發(fā)操作，解決線程安全問題。Segment數(shù)組把一個(gè)大的表切割為多個(gè)小的表來進(jìn)行加鎖，降低鎖的范圍的同時(shí)增加了并發(fā)度。每一個(gè)Segment元素存儲(chǔ)的是HashEntry數(shù)組和鏈表。在插入和檢索元素時(shí)，首先通過哈希算法定位到所在分段，然后使用特定算法對(duì)元素的哈希值進(jìn)行再一次哈希計(jì)算，目的是為了減少哈希沖突，使元素能夠相對(duì)均勻的分布在不同的分段上，從而提高整個(gè)數(shù)據(jù)結(jié)構(gòu)的插入和檢索效率。

對(duì)整個(gè)HashMap進(jìn)行操作時(shí)，首先不加鎖循環(huán)執(zhí)行，循環(huán)所有的分段獲得對(duì)應(yīng)的值。如果連續(xù)兩次所有分段的返回的值相等，則認(rèn)為過程中沒有發(fā)生其他線程修改的情況，返回獲得的值。鎖分離方法減少了請(qǐng)求同一鎖的頻率，有效地縮短了鎖的持有時(shí)間，使得HashMap的并發(fā)性能有了質(zhì)的提高。當(dāng)循環(huán)次數(shù)超過預(yù)定義值時(shí)需要依次鎖定所有分段，獲取返回值后按順序解鎖。加鎖過程中強(qiáng)制鎖定所有的分段，避免出現(xiàn)其他線程創(chuàng)建分段與插入等操作。

3.2 ?分段鎖的并行度

分段鎖保證了鎖競爭只存在于同一分段內(nèi)，不同Segment之間不存在鎖競爭。與鎖定整表的設(shè)計(jì)相比，分段鎖在高并發(fā)環(huán)境下，有效的提升了程序的處理能力，但是由于不是對(duì)整個(gè)數(shù)據(jù)結(jié)構(gòu)加鎖，導(dǎo)致一些需要掃描全表的方法需要使用特殊的實(shí)現(xiàn)方式，如Clear方法就降低了對(duì)一致性的要求。除了第一個(gè)分段鎖之外，剩余的分段鎖采用的是延遲初始化的機(jī)制，在每次插入操作前需要檢查Key對(duì)應(yīng)的分段是否存在[11]。如果不存在就創(chuàng)建分段鎖，當(dāng)鏈表的長度太長時(shí)會(huì)經(jīng)常發(fā)生哈希沖突，插入和刪除鏈表的操作需要很長的時(shí)間。并發(fā)度是不產(chǎn)生鎖競爭的最大線程數(shù)，實(shí)際上就是Segment數(shù)組長度，默認(rèn)的并發(fā)度為16，同時(shí)支持用戶自定義并發(fā)度。如果并發(fā)設(shè)置太小，會(huì)出現(xiàn)嚴(yán)重的鎖爭用問題。如果并發(fā)性設(shè)置得太大，最初位于同一段中的數(shù)據(jù)訪問將擴(kuò)展到不同的分段鎖，命中率會(huì)下降引起檢索效率下降。

4 ?CAS算法優(yōu)化

4.1 ?CAS算法原子性原理

進(jìn)行CAS操作時(shí)將，首先變量的期望值與當(dāng)前值進(jìn)行比較，如果變量的當(dāng)前值等于預(yù)期值，則使用新值替換當(dāng)前變量的值[12]。采用CAS算法實(shí)現(xiàn)并發(fā)環(huán)境下的無鎖策略，檢測(cè)到線程沖突時(shí)協(xié)調(diào)當(dāng)前操作。使用沒有鎖定機(jī)制的Volatile原語，保證了線程之間數(shù)據(jù)的可見性，可以直接讀取變量值。Volatile變量的讀寫與CAS實(shí)現(xiàn)線程之間的通信的可見性與有序性，不會(huì)阻塞線程，并且比同步鎖的響應(yīng)更好。采用CAS操作每次從內(nèi)存中讀取數(shù)據(jù)，確保對(duì)內(nèi)存的讀改寫操作是原子執(zhí)行。無鎖是一種樂觀的策略，假設(shè)在訪問資源時(shí)沒有沖突，線程不需要阻塞。相對(duì)于悲觀鎖策略，CAS算法使程序設(shè)計(jì)有明顯的優(yōu)勢(shì)，無鎖方式避免了鎖競爭的性能開銷，以及在線程間調(diào)度的性能開銷，提供了更好的并發(fā)讀寫性能，也降低了對(duì)讀一致性的要求。

CAS使用處理器提供的機(jī)器級(jí)原子指令，以原子方式對(duì)存儲(chǔ)器執(zhí)行讀寫操作，這是多處理器實(shí)現(xiàn)同步的關(guān)鍵。支持原子讀寫指令的計(jì)算機(jī)是一個(gè)順序計(jì)算圖靈機(jī)的異步等價(jià)機(jī)器，多處理器都支持對(duì)內(nèi)存執(zhí)行原子讀寫的指令。如果該值在同一時(shí)間被另一個(gè)線程更新，則寫入失敗，采用自旋的方式繼續(xù)進(jìn)行CAS操作。CPU提供的特殊指令能夠自動(dòng)更新共享數(shù)據(jù)，排除其他線程的干擾，CPU實(shí)現(xiàn)原子操作有以下兩種方式。

1）通過總線鎖保證原子性?？偩€鎖是處理器提供的Lock#信號(hào)，能夠阻止其他處理器的請(qǐng)求，確保當(dāng)前處理器可以獨(dú)占共享內(nèi)存。例如多個(gè)處理器同時(shí)讀取與修改共享變量，則必須確保CPU1在讀取與寫入共享變量時(shí)，CPU2無法讀取共享變量。通過總線鎖定CPU和存儲(chǔ)器之間的通信，使得其他處理器在鎖定期間，無法操縱該存儲(chǔ)器地址的數(shù)據(jù)，總線鎖定開銷相對(duì)較大。

2）使用緩存鎖保證原子性。如果在執(zhí)行鎖定前綴指令期間，要訪問的存儲(chǔ)區(qū)已鎖定在處理器的內(nèi)部高速緩存中，并且存儲(chǔ)區(qū)完全包含在單個(gè)高速緩存行中，處理器將直接執(zhí)行指令。由于在執(zhí)行指令期間，始終鎖定高速緩存行，其他處理器不能讀取與寫入指令要訪問的存儲(chǔ)區(qū)域，從而確保指令執(zhí)行的原子性。緩存鎖定將大大降低Lock前綴指令的執(zhí)行開銷，但是當(dāng)多個(gè)處理器之間的競爭程度很高，或指令訪問的內(nèi)存地址未對(duì)齊時(shí)，總線仍然處于 ?鎖定狀態(tài)，禁止指令與先前和后續(xù)的讀寫指令重新排序。

4.2 ?CAS算法優(yōu)化方法

CAS算法可以有效地解決原子操作問題，但CAS算法存在三個(gè)問題，包括ABA問題、長周期的時(shí)間開銷問題，以及只能保證單個(gè)共享變量的原子操作。針對(duì)以上三個(gè)問題采取以下方法進(jìn)行優(yōu)化處理。

（1）增加版本戳避免ABA問題。將版本標(biāo)記附加到變量的前面，并在每次更新變量時(shí)增加版本標(biāo)記。CAS操作首先檢查當(dāng)前引用值是否等于預(yù)期值，并且當(dāng)前版本標(biāo)記是否等于預(yù)期值，如果全部相等，以原子方式將引用和版本標(biāo)記的值設(shè)置為給定的更新值。Zookeeper中保持?jǐn)?shù)據(jù)一致性也是用的這種方式，假設(shè)完成操作時(shí)不發(fā)生沖突。

（2）如果自旋CAS長時(shí)間不成功，將給CPU帶來非常大的執(zhí)行開銷。如果支持處理器提供的暫停指令，那么效率將得到提高。Pause指令可以延遲管道執(zhí)行指令，以便CPU不會(huì)消耗太多的執(zhí)行資源。此外，還可以避免在退出循環(huán)時(shí)，由于存儲(chǔ)器序列沖突而清空CPU流水線，提高CPU執(zhí)行效率。

（3）當(dāng)對(duì)共享變量執(zhí)行操作時(shí)，使用循環(huán)CAS方法保證原子操作，但是當(dāng)對(duì)多個(gè)共享變量進(jìn)行操作時(shí)，循環(huán)CAS不能保證操作的原子性，可以將多個(gè)變量放在CAS操作的對(duì)象中，實(shí)現(xiàn)對(duì)多個(gè)共享變量的原子操作。

4.3 ?CAS算法優(yōu)化實(shí)現(xiàn)

如圖2所示，CAS算法優(yōu)化代碼實(shí)現(xiàn)。創(chuàng)建一個(gè)Pair類來保存對(duì)象的引用和版本標(biāo)記。Pair對(duì)象是不可變的，所有屬性都用Final修飾，并且該方法每次都返回一個(gè)新的不可變對(duì)象。Volatile類型引用用于指向當(dāng)前的Pair對(duì)象。使用Volatile修改的變量強(qiáng)制將修改后的值立即寫入主內(nèi)存，主內(nèi)存值的更新使緩存中的值無效。當(dāng)Set方法設(shè)置的對(duì)象與當(dāng)前Pair對(duì)象不同時(shí)，創(chuàng)建一個(gè)新的不可變的Pair對(duì)象。在更新方法中，只有期望對(duì)象的引用和版本號(hào)，與目標(biāo)對(duì)象的引用和版本相同，將創(chuàng)建一個(gè)新Pair對(duì)象，然后使用新對(duì)象和原始對(duì)象執(zhí)行CAS操作。實(shí)際上，CAS操作將當(dāng)前Pair對(duì)象與新的Pair對(duì)象進(jìn)行比較，而Pair對(duì)象封裝了引用和版本標(biāo)記。

5 ?無鎖的數(shù)據(jù)結(jié)構(gòu)與擴(kuò)容方法

5.1 ?無鎖實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)

如圖3所示，鏈表和紅黑樹實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)?；贑AS算法實(shí)現(xiàn)并行的HashMap數(shù)據(jù)結(jié)構(gòu)，內(nèi)部采用數(shù)組、鏈表和紅黑樹實(shí)現(xiàn)線程安全操作[13]。HashMap的初始化只能由單線程完成，通過控制標(biāo)識(shí)符確保初始化方法的線程安全，控制標(biāo)識(shí)符不同的取值代表不同的含義。如果控制標(biāo)識(shí)符的值小于0，表示其他線程正在進(jìn)行初始化，當(dāng)前線程放棄操作。如果獲得了初始化權(quán)限，控制標(biāo)識(shí)符的值置為–1，防止其他線程進(jìn)入。

使用Node數(shù)組代替Segment存儲(chǔ)數(shù)據(jù)，Node可以是鏈表或紅黑樹結(jié)構(gòu)。如果插入的元素鍵具有相同的哈希值，則鍵位于Node節(jié)點(diǎn)數(shù)組中的同一單元格中。如果鏈表存儲(chǔ)的數(shù)據(jù)超過8個(gè)，將鏈表轉(zhuǎn)換為紅黑樹結(jié)構(gòu)。即使所有Key的哈希值完全相同，紅黑樹中查找某個(gè)特定元素復(fù)雜度仍然是O（logn）。根據(jù)哈希值計(jì)算表中新插入點(diǎn)的位置索引，如果該位置為空則直接插入，否則判斷如果位置是樹節(jié)點(diǎn)，將新節(jié)點(diǎn)作為樹節(jié)點(diǎn)插入，或?qū)⑵洳迦氲芥湵淼哪┪病?/p>

CAS算法能夠確保Node操作的原子性，標(biāo)識(shí)符的不同值來代表不同含義起到了控制的作用。采用Node降低鎖的粒度，分段鎖的粒度是Segment包含多個(gè)HashEntry，而CAS算法的鎖的粒度就是首節(jié)點(diǎn)HashEntry，減低了數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的復(fù)雜度。遍歷數(shù)據(jù)集很大的鏈表的是非常耗時(shí)，使用紅黑樹來優(yōu)化鏈表結(jié)構(gòu)，檢索效率上存在一定的優(yōu)勢(shì)。

5.2 ?多線程的擴(kuò)容方法

容量不足時(shí)需要對(duì)Table進(jìn)行擴(kuò)容操作，支持無鎖狀態(tài)下的多線程擴(kuò)容，并發(fā)處理能夠減少擴(kuò)容的時(shí)間開銷。擴(kuò)容涉及數(shù)據(jù)從一個(gè)數(shù)組拷貝到另一個(gè)數(shù)組，并發(fā)操作可以在很大程度上提升執(zhí)行效率，整個(gè)擴(kuò)容操作分為兩個(gè)部分。

首先，使用單線程構(gòu)建一個(gè)容量是原來兩倍的目標(biāo)表Next Table。根據(jù)運(yùn)算得到需要遍歷的次數(shù)Index，然后獲得Index位置的元素。如果該位置為空就在原Table中的該位置放入Forward節(jié)點(diǎn)，作為連接兩個(gè)Table的節(jié)點(diǎn)類，包含一個(gè)用于指向下一張表的指針[14]。如果該位置是Node節(jié)點(diǎn)，并且是一個(gè)鏈表的頭節(jié)點(diǎn)就構(gòu)造一個(gè)反序鏈表，分別插入目標(biāo)表Next Table的Index和Index + N的位置。

然后，采用多線程將源Table中的數(shù)據(jù)復(fù)制到目標(biāo)Next Table中。如果被遍歷的節(jié)點(diǎn)是Forward節(jié)點(diǎn)，當(dāng)前線程繼續(xù)向后遍歷。處理一個(gè)節(jié)點(diǎn)并將相應(yīng)的點(diǎn)的值設(shè)置為Forward，其他個(gè)線程檢測(cè)到Forward節(jié)點(diǎn)就繼續(xù)向后遍歷。如果檢測(cè)到要插入的節(jié)點(diǎn)不是空的或者Forward節(jié)點(diǎn)，則鎖定該節(jié)點(diǎn)以確保線程安全[15]。盡管鎖定該節(jié)點(diǎn)有性能開銷，比起同步鎖還是存在一定的性能優(yōu)勢(shì)，交叉執(zhí)行完成數(shù)據(jù)復(fù)制，同時(shí)也保證了線程安全。

6 ?實(shí)驗(yàn)和結(jié)果分析

實(shí)驗(yàn)運(yùn)行環(huán)境的CPU為8 Core、內(nèi)存配置16GB的單臺(tái)服務(wù)器，安裝64位CentOS 7操作系統(tǒng)。使用并發(fā)測(cè)試工具模擬大規(guī)模并發(fā)操作，返回內(nèi)存數(shù)據(jù)結(jié)構(gòu)的響應(yīng)時(shí)間。分別測(cè)試在兩中情況下，單個(gè)線程進(jìn)行10000次相同操作，向哈希映射數(shù)據(jù)結(jié)構(gòu)中插入一個(gè)新鍵值對(duì)，再查詢?cè)揔ey對(duì)應(yīng)的值，并發(fā)量設(shè)置為50。如表1所示，統(tǒng)計(jì)指標(biāo)包括響應(yīng)時(shí)間的平均值、中值、偏離值和吞吐量，吞吐量單位是每分鐘。

如圖4所示，1000個(gè)測(cè)試樣本數(shù)據(jù)響應(yīng)時(shí)間等指標(biāo)統(tǒng)計(jì)，50并發(fā)量循環(huán)20次，得到1000個(gè)測(cè)試樣本，普通HashMap數(shù)據(jù)結(jié)構(gòu)的響應(yīng)時(shí)間隨并發(fā)量增加呈現(xiàn)階梯狀增長?；贑AS算法改進(jìn)的HashMap數(shù)據(jù)結(jié)構(gòu)的階梯幅度明顯小于普通的HashMap數(shù)據(jù)結(jié)構(gòu)，在平均響應(yīng)時(shí)間指標(biāo)也存在明顯的優(yōu)勢(shì)。

如圖5所示，2000個(gè)測(cè)試樣本數(shù)據(jù)響應(yīng)時(shí)間等指標(biāo)統(tǒng)計(jì)，50并發(fā)量循環(huán)40次，得到2000個(gè)測(cè)試樣本呈現(xiàn)相同的規(guī)律，改進(jìn)的HashMap數(shù)據(jù)結(jié)構(gòu)仍然存在明顯的優(yōu)勢(shì)。改進(jìn)的HashMap數(shù)據(jù)結(jié)構(gòu)主要是為高并發(fā)設(shè)計(jì)，通過數(shù)據(jù)的弱一致性帶來性能上的大幅提升，降低了執(zhí)行成本和擁有更高的并發(fā)性。

7 ?結(jié)語

本文提出了基于CAS算法實(shí)現(xiàn)線程安全的哈希映射數(shù)據(jù)結(jié)構(gòu)，內(nèi)部采用數(shù)組、鏈表和紅黑樹實(shí)現(xiàn)了高并發(fā)環(huán)境下讀寫效率。通過增加版本戳避免CAS算法中的ABA問題，CAS算法實(shí)現(xiàn)的無鎖方式，避免了鎖競爭的開銷，使用紅黑樹來優(yōu)化鏈表，確保數(shù)據(jù)集很大時(shí)時(shí)間復(fù)雜度是O（logn）。在無鎖狀態(tài)下的多線程擴(kuò)容操作，減少了擴(kuò)容的時(shí)間開銷。通過大規(guī)模的并發(fā)測(cè)試，驗(yàn)證了該數(shù)據(jù)結(jié)構(gòu)在性能上有穩(wěn)定的提升。

參考文獻(xiàn)

[1] Al-Wesabi O，Samsudin A. Fast hashing function based on multi-pipeline hash construction （MPHC）[J]. International Journal of Innovative Computing， Information and Control， 2012， 8（11）： 7887-7907.

[2] Li Y T， Xiao D. Parallel Hash function construction based on chaotic maps with changeable parameters[J]. Neural Computing and Applications， 2011， 20（8）： 1305-1312.

[3] Kishore N， Kapoor B. An efficient parallel algorithm for hash computation in security and forensics applications[C]//Pro?ceedings on IEEE International Advance Computing Conference， 2014： 873-877.

[4] 徐勁松， 張民選. Merkle-Damgrd Hash結(jié)構(gòu)并行擴(kuò)展算法[J]. 國防科技大學(xué)學(xué)報(bào)， 2017， 39（06）： 59-63.

[5] 張濱， 樂嘉錦. 基于列存儲(chǔ)的MapReduce分布式Hash連接算法[J]. 計(jì)算機(jī)科學(xué)， 2018， 45（S1）： 471-475+505.

[6] 李濤， 董前琨， 張帥. 基于線程池的GPU任務(wù)并行計(jì)算模式研究[J]. 計(jì)算機(jī)學(xué)報(bào)， 2018， 41（10）： 2175-2192.

[7] 吳泉源， 彭燦. 適用于海量數(shù)據(jù)應(yīng)用的多維Hash表結(jié)構(gòu)[J]. 清華大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2017， 57（06）： 586-590.

[8] 陳之彥， 李曉杰. 基于Hash結(jié)構(gòu)詞典的雙向最大匹配分詞法[J]. 計(jì)算機(jī)科學(xué)， 2015， 42（S2）： 49-54.

[9] 王興， 鮑志偉. 適用于高速檢索的完美Hash函數(shù)[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用， 2016， 25（02）： 250-256.

[10] 劉志強(qiáng)， 宋君強(qiáng). 基于線程的MPI通信加速器技術(shù)研究[J]. 計(jì)算機(jī)學(xué)報(bào)， 2011， 34（01）： 154-164.

[11] 吳恩慈. 基于JAVA大規(guī)模應(yīng)用中GC算法和調(diào)優(yōu)技術(shù)研究[J]. 電子技術(shù)與軟件工程， 2016（04）： 249.

[12] 錢振江， 盧亮. 微內(nèi)核架構(gòu)多線程機(jī)制的形式化設(shè)計(jì)研究[J]. 計(jì)算機(jī)科學(xué)， 2013， 40（04）： 136-141+163.

[13] 張良， 劉敬浩. 命名數(shù)據(jù)網(wǎng)絡(luò)中基于Hash映射的命名檢索. 計(jì)算機(jī)工程， 2014， 40（4）： 108-111.

[14] 母紅芬， 李征. HashMap優(yōu)化及其在列存儲(chǔ)數(shù)據(jù)庫查詢中的應(yīng)用[J]. 計(jì)算機(jī)科學(xué)與探索， 2016， 10（09）： 1250-1261.

[15] 賈剛勇， 萬健， 李曦. 一種結(jié)合頁分配和組調(diào)度的內(nèi)存功耗優(yōu)化方法[J]. 軟件學(xué)報(bào)， 2014， 25（07）： 1403-1415.