基于優(yōu)化的CAS算法實現(xiàn)線程安全的HashMap

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

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

中圖分類號： TP311.12 ? ?文獻標識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.06.043

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

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

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

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

1 ?相關工作

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

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

2 ?問題分析

2.1 ?HashMap線程安全問題

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

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

2.2 ?悲觀鎖的性能問題

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

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

3 ?分段鎖算法

3.1 ?分段鎖的數(shù)據(jù)結構

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

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

3.2 ?分段鎖的并行度

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

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

4.1 ?CAS算法原子性原理

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

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

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

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

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

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

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

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

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

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

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

5 ?無鎖的數(shù)據(jù)結構與擴容方法

5.1 ?無鎖實現(xiàn)的數(shù)據(jù)結構

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

使用Node數(shù)組代替Segment存儲數(shù)據(jù)，Node可以是鏈表或紅黑樹結構。如果插入的元素鍵具有相同的哈希值，則鍵位于Node節(jié)點數(shù)組中的同一單元格中。如果鏈表存儲的數(shù)據(jù)超過8個，將鏈表轉換為紅黑樹結構。即使所有Key的哈希值完全相同，紅黑樹中查找某個特定元素復雜度仍然是O（logn）。根據(jù)哈希值計算表中新插入點的位置索引，如果該位置為空則直接插入，否則判斷如果位置是樹節(jié)點，將新節(jié)點作為樹節(jié)點插入，或將其插入到鏈表的末尾。

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

5.2 ?多線程的擴容方法

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

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

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

6 ?實驗和結果分析

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

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

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

7 ?結語

本文提出了基于CAS算法實現(xiàn)線程安全的哈希映射數(shù)據(jù)結構，內部采用數(shù)組、鏈表和紅黑樹實現(xiàn)了高并發(fā)環(huán)境下讀寫效率。通過增加版本戳避免CAS算法中的ABA問題，CAS算法實現(xiàn)的無鎖方式，避免了鎖競爭的開銷，使用紅黑樹來優(yōu)化鏈表，確保數(shù)據(jù)集很大時時間復雜度是O（logn）。在無鎖狀態(tài)下的多線程擴容操作，減少了擴容的時間開銷。通過大規(guī)模的并發(fā)測試，驗證了該數(shù)據(jù)結構在性能上有穩(wě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結構并行擴展算法[J]. 國防科技大學學報， 2017， 39（06）： 59-63.

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

[6] 李濤， 董前琨， 張帥. 基于線程池的GPU任務并行計算模式研究[J]. 計算機學報， 2018， 41（10）： 2175-2192.

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

[8] 陳之彥， 李曉杰. 基于Hash結構詞典的雙向最大匹配分詞法[J]. 計算機科學， 2015， 42（S2）： 49-54.

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

[10] 劉志強， 宋君強. 基于線程的MPI通信加速器技術研究[J]. 計算機學報， 2011， 34（01）： 154-164.

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

[12] 錢振江， 盧亮. 微內核架構多線程機制的形式化設計研究[J]. 計算機科學， 2013， 40（04）： 136-141+163.

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

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

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