Raft共識算法在分佈式系統中是常用的共識算法之一，論文原文In Search of an Understandable Consensus Algorithm ，作者在論文中指出Poxas共識算法的兩大問題，其一是難懂，其二是應用到實際系統存在困難。針對Paxos存在的問題，作者的目的是提出一個易懂的共識算法，論文中有單獨一小節論述Raft是一個實用的、安全可用、有效易懂的共識算法。本文描述了Raft共識算法的細節，很多內容描述及引用圖片均摘自論文原文。

Raft概述

我們主要分以下三部分對Raft進行討論：

• Leader election——a new leader must be chosen when
  an existing leader fails. （領導人選舉）
• Log replication——the leader must accept log entries from clients and replicate them across the cluster,
  forcing the other logs to agree with its own.（日誌複製）
• Safety——the key safety property for Raft. （安全性）

正常工作過程中，Raft分為兩部分，首先是leader選舉過程，然後在選舉出來的leader基礎上進行正常操作，比如日誌複製操作等。

一個Raft集群通常包含\(2N+1\)個服務器，允許系統有\(N\)個故障服務器。每個服務器處於3個狀態之一：leader、follower或candidate。正常操作狀態下，僅有一個leader，其他的服務器均為follower。follower是被動的，不會對自身發出的請求而是對來自leader和candidate的請求做出響應。leader處理所有的client請求（若client聯繫follower，則該follower將轉發給leader)。candidate狀態用來選舉leader。狀態轉換如下圖所示：

為了進行領導人選舉和日誌複製等，需要服務器節點存儲如下狀態信息：

狀態	所有服務器上持久存在的
currentTerm	服務器最後一次知道的任期號（初始化為 0，持續遞增）
votedFor	在當前獲得選票的候選人的 Id
log[]	日誌條目集；每一個條目包含一個用戶狀態機執行的指令，和收到時的任期號

狀態	所有服務器上經常變的
commitIndex	已知的最大的已經被提交的日誌條目的索引值
lastApplied	最後被應用到狀態機的日誌條目索引值（初始化為 0，持續遞增）

狀態	在領導人里經常改變的 （選舉后重新初始化）
nextIndex[]	對於每一個服務器，需要發送給他的下一個日誌條目的索引值（初始化為領導人最後索引值加一）
matchIndex[]	對於每一個服務器，已經複製給他的日誌的最高索引值

Raft在任何時刻都滿足如下特性：

• Election Safety：在一個任期中只能有一個leader；
• Leader Append-Only：leader不會覆蓋或刪除日誌中的entry，只有添加entry（follower存在依據leader回滾日誌的情況）；
• Log Matching：如果兩個日誌包含了一條具有相同index和term的entry，那麼這兩個日誌在這個index之前的所有entry都相同；
• Leader Completeness： 如果在某一任期一條entry被提交committed了，那麼在更高任期的leader中這條entry一定存在；（領導人選舉時會保證這一性質，後面會講到這個問題）
• State Machine Safety：如果一個節點將一條entry應用到狀態機中，那麼任何節點也不會再次將該index的entry應用到狀態機里；

下面我們詳細討論這幾部分。

Leader選舉（Leader election）

一個節點初始狀態為follower，當follower在選舉超時時間內未收到leader的心跳消息，則轉換為candidate狀態。為了避免選舉衝突，這個超時時間是一個隨機數（一般為150~300ms）。超時成為candidate后，向其他節點發出RequestVoteRPC請求，假設有\(2N+1\)個節點，收到\(N+1\)個節點以上的同意回應，即被選舉為leader節點，開始下一階段的工作。如果在選舉期間接收到eader發來的心跳信息，則candidate轉為follower狀態。

在選舉期間，可能會出現多個candidate的情況，可能在一輪選舉過程中都沒有收到多數的同意票，此時再次隨機超時，進入第二輪選舉過程，直至選出leader或着重新收到leader心跳信息，轉為follower狀態。

正常狀態下，leader會不斷的廣播心跳信息，follower收到leader的心跳信息後會重置超時。當leader崩潰或者出現異常離線，此時網絡中follower節點接收不到心跳信息，超時再次進入選舉流程，選舉出一個leader。

這裏還有補充一些細節，每個leader可以理解為都是有自己的任期(term)的，每一期起始於選舉階段，直到因節點失效等原因任期結束。每一期選舉期間，每個follower節點只能投票一次。圖中t3可能是因為沒有獲得超半數票等造成選舉失敗，須進行下一輪選舉，此時follower可以再次對最先到達的candidate發出的RequestVote請求投票（先到先得）。

對所有的請求（RequestVote、AppendEntry等請求），如果發現其Term小於當前節點，則拒絕請求，如果是candidate選舉期間，收到不小於當前節點任期的leader節點發來的AppendEntry請求，則認可該leader，candidate轉換為follower。

日誌複製（Log replication）

leader選舉成功后，將進入有效工作階段，即日誌複製階段，其中日誌複製過程會分記錄日誌和提交數據兩個階段。

整個過程如下：

1. 首先client向leader發出command指令；（每一次command指令都可以認為是一個entry，或者說是日誌項）
2. leader收到client的command指令后，將這個command entry追加到本地日誌中，此時這個command是uncommitted狀態，因此並沒有更新節點的當前狀態；
3. 之後，leader向所有follower發送這條entry，也就是通過日誌複製AppendEntries消息 (可以是一條也可以是多條日誌項) 將日誌項複製到集群其他節點上，follower接收到后 （這裡有判斷條件的，並不是所有leader發送來的日誌項都無條件接收，而且還可能存在本地與leader日誌不一致的情況，後面會詳細說明，這裏先看正常情況） 追加到本地日誌中，並回應leader成功或者失敗；
4. leader收到大多數follower的確認回應后，此entry在leader節點由uncommitted變為committed狀態，此時按這條command更新leader狀態，或者說將該日誌項應用到狀態機，然後向client返回執行結果；
5. 在下一心跳中(這裏也可以是或者說多數情況下是新的日誌複製AppendEntries消息，會帶有相關信息，後面后詳細的字段說明會講到)，leader會通知所有follower更新確認的entry，follower收到后，更新狀態，這樣，所有節點都完成client指定command的狀態更新。

可以看到client每次提交command指令，服務節點都先將該指令entry追加記錄到日誌中，等leader確認大多數節點已追加記錄此條日誌后，在進行提交確認，更新節點狀態。如果還對這個過程有些模糊的話，可以參考Raft動畫演示，較為直觀的演示了領導人選舉及日誌複製的過程。

安全（Safety）

前面描述了Raft算法是如何選舉和複製日誌的。然而，到目前為止描述的機制並不能充分的保證每一個狀態機會按照相同的順序執行相同的指令。我們需要再繼續深入思考以下幾個問題：

• 第一個問題，leader選舉時follower收到candidate發起的投票請求，如果同意就進行回應，但具體的規則是什麼呢？是所有的follower都有可能被選舉為領導人嗎？
• 第二個問題，leader可能在任何時刻掛掉，新任期的leader怎麼提交之前任期的日誌條目呢？

選舉限制

針對第一個問題，之前並沒有細講，如果當前leader節點掛了，需要重新選舉一個新leader，此時follower節點的狀態可能是不同的，有的follower可能狀態與剛剛掛掉的leader相同，狀態較新，有的follower可能記錄的當前index比原leader節點的少很多，狀態更新相對滯后，此時，從系統最優的角度看，選狀態最新的candidate為佳，從正確性的角度看，要確保Leader Completeness，即如果在某一任期一條entry被提交成功了，那麼在更高任期的leader中這條entry一定存在，反過來講就是如果一個candidate的狀態舊於目前被committed的狀態，它一定不能被選為leader。具體到投票規則：
1） 節點只投給擁有不比自己日誌狀態舊的節點；
2）每個節點在一個term內只能投一次，在滿足1的條件下，先到先得；

我們看一下請求投票 RPC（由候選人負責調用用來徵集選票）的定義：

參數	解釋
term	候選人的任期號
candidateId	請求選票的候選人的 Id
lastLogIndex	候選人的最後日誌條目的索引值
lastLogTerm	候選人最後日誌條目的任期號

返回值	解釋
term	當前任期號，以便於候選人去更新自己的任期號
voteGranted	候選人贏得了此張選票時為真

接收者實現：

1. 如果term < currentTerm返回 false
2. 如果 votedFor 為空或者為 candidateId，並且候選人的日誌至少和自己一樣新，那麼就投票給他

可以看到RequestVote投票請求中包含了lastLogIndex和lastLogTerm用於比較日誌狀態。這樣，雖然不能保證最新狀態的candidate成為leader，但能夠保證被選為leader的節點一定擁有最新被committed的狀態，但不能保證擁有最新uncommitted狀態entries。

提交之前任期的日誌條目

領導人知道一條當前任期內的日誌記錄是可以被提交的，只要它被存儲到了大多數的服務器上。但是之前任期的未提交的日誌條目，即使已經被存儲到大多數節點上，也依然有可能會被後續任期的領導人覆蓋掉。下圖說明了這種情況：

如圖的時間序列展示了為什麼領導人無法決定對老任期號的日誌條目進行提交。在 (a) 中，S1 是領導者，部分的複製了索引位置 2 的日誌條目。在 (b) 中，S1崩潰了，然後S5在任期3里通過S3、S4和自己的選票贏得選舉，然後從客戶端接收了一條不一樣的日誌條目放在了索引 2 處。然後到 (c)，S5又崩潰了；S1重新啟動，選舉成功，開始複製日誌。在這時，來自任期2的那條日誌已經被複制到了集群中的大多數機器上，但是還沒有被提交。如果S1在(d)中又崩潰了，S5可以重新被選舉成功（通過來自S2，S3和S4的選票），然後覆蓋了他們在索引 2 處的日誌。反之，如果在崩潰之前，S1 把自己主導的新任期里產生的日誌條目複製到了大多數機器上，就如 (e) 中那樣，那麼在後面任期裏面這些新的日誌條目就會被提交（因為S5 就不可能選舉成功）。 這樣在同一時刻就同時保證了，之前的所有老的日誌條目就會被提交。

為了消除上圖裡描述的情況，Raft永遠不會通過計算副本數目的方式去提交一個之前任期內的日誌條目。只有領導人當前任期里的日誌條目通過計算副本數目可以被提交；一旦當前任期的日誌條目以這種方式被提交，那麼由於日誌匹配特性，之前的日誌條目也都會被間接的提交。

當領導人複製之前任期里的日誌時，Raft 會為所有日誌保留原始的任期號。

對Raft中幾種情況的思考

follower節點與leader日誌內容不一致時怎麼處理？

我們先舉例說明：正常情況下，follower節點應該向B節點一樣與leader節點日誌內容一致，但也會出現A、C等情況，出現了不一致，以A、B節點為例，當leader節點向follower節點發送AppendEntries<prevLogIndex=7,prevLogTerm=3,entries=[x<-4]>,leaderCommit=7時，我們分析一下發生了什麼，B節點日誌與prevLogIndex=7,prevLogTerm=3相匹配，將index=7（x<-5）這條entry提交committed，並在日誌中新加入entryx<-4，處於uncommitted狀態；A節點接收到時，當前日誌index<prevLogIndex與prevLogIndex=7,prevLogTerm=3不相匹配，拒接該請求，不會將x<-4添加到日誌中，當leader知道A節點因日誌不一致拒接了該請求后，不斷遞減preLogIndex重新發送請求，直到A節點index,term與prevLogIndex,prevLogTerm相匹配，將leader的entries複製到A節點中，達成日誌狀態一致。

我們看一下附加日誌AppendEntries RPC（由領導人負責調用複製日誌指令；也會用作heartbeat）的定義：

參數	解釋
term	領導人的任期號
leaderId	領導人的 Id，以便於跟隨者重定向請求
prevLogIndex	新的日誌條目緊隨之前的索引值
prevLogTerm	prevLogIndex 條目的任期號
entries[]	準備存儲的日誌條目（表示心跳時為空；一次性發送多個是為了提高效率）
leaderCommit	領導人已經提交的日誌的索引值

返回值	解釋
term	當前的任期號，用於領導人去更新自己
success	跟隨者包含了匹配上 prevLogIndex 和 prevLogTerm 的日誌時為真

接收者實現：

1. 如果 term < currentTerm 就返回 false；
2. 如果日誌在 prevLogIndex 位置處的日誌條目的任期號和 prevLogTerm 不匹配，則返回 false；
3. 如果已經存在的日誌條目和新的產生衝突（索引值相同但是任期號不同），刪除這一條和之後所有的；（raft中follower處理不一致的一個原則就是一切聽從leader）
4. 附加日誌中尚未存在的任何新條目；
5. 如果 leaderCommit > commitIndex，令 commitIndex 等於 leaderCommit 和 新日誌條目索引值中較小的一個；

簡單總結一下，出現不一致時核心的處理原則是一切遵從leader。當leader向follower發送AppendEntry請求，follower對AppendEntry進行一致性檢查，如果通過，則更新狀態信息，如果發現不一致，則拒絕請求，leader發現follower拒絕請求，出現了不一致，此時將遞減nextIndex，並重新給該follower節點發送日誌複製請求，直到找到日誌一致的地方為止。然後把follower節點的日誌覆蓋為leader節點的日誌內容。

leader掛掉了，怎麼處理？

前面可能斷斷續續的提到這種情況的處理方法，首要的就是選出新leader，選出新leader后，可能上一任期還有一些entries並沒有提交，處於uncommitted狀態，該怎麼辦呢？處理方法是新leader只處理提交新任期的entries，上一任期未提交的entries，如果在新leader選舉前已經被大多數節點記錄在日誌中，則新leader在提交最新entry時，之前處於未提交狀態的entries也被committed了，因為如果兩個日誌包含了一條具有相同index和term的entry，那麼這兩個日誌在這個index之前的所有entry都相同；如果在新leader選舉前沒有被大多數節點記錄在日誌中，則原有未提交的entries有可能被新leader的entries覆蓋掉。

出現網絡分區時怎麼處理？

分佈式系統中網絡分區的情況基本無法避免，出現網絡分區時，原有leader在分區的一側，此時如果客戶端發來指令，舊leader依舊在分區一測進行日誌複製的過程，但因收不到大多數節點的確認，客戶端所提交的指令entry只能記錄在日誌中，無法進行提交確認，處於uncommitted狀態。而在分區的另一側，此時收不到心跳信息，會進入選舉流程重新選舉一個leader，新leader負責分區零一側的請求，進行日誌複製等操作。因為新leader可以收到大多數follower確認，客戶端的指令entry可以被提交，並更新節點狀態，當網絡分區恢復時，此時兩個leader會收到彼此廣播的心跳信息，此時，舊leader發現更大term的leader，舊leader轉為follower，此時舊leader分區一側的所有操作都要回滾，接受新leader的更新。

成員變更

在分佈式系統中，節點數量或者說服務器數量不是一成不變的，我們有可能會隨時增減節點數量，當增加節點時，有可能會出現兩個leader選舉成功的情況，主要是新舊配置不一致造成的，怎麼處理呢？最簡單粗暴的就是把目前所有節點都停掉，更新配置，再重啟所有節點，但會造成一段時間服務不可用，很多情況下這是不能被允許的。raft的解決辦法原論文中是聯合共識（Joint Consensus）的辦法，後來又提出了單節點變更（single-server changes）的方法。我們下面詳細描述一下這個問題。

Raft要求，在任一任期內，只能有一個leader，而成員變更的麻煩就在於，成員變更時可能會出現兩個leader，以一個例子說明：原系統有3個節點，成員為[1,2,3]，現新增成員4、5。假設在成員變更時，1、2與3發生分區，此時，[1,2]為一組，1通過1、2兩節點選舉為leader，而5通過3、4、5選舉為leader，就形成了2個leader並存的情況。

因為每個節點新舊配置更新的時間不同，造成了在某一時刻，可能會存在新舊配置的兩個大多數情況的存在，上圖中，舊配置的大多數是兩個節點，而新配置的大多數是三個節點，在圖中紅線頭的時刻存在兩個大多數的情況，如果此時出現網絡分區進行選舉時就會出現兩個leader的情況。

怎麼解決呢？用什麼辦法才能不讓上面兩個大多少情況的出現呢？可通過單節點變更解決，即通過一次變更一個節點實現成員變更。主要思想是利用“一次變更一個節點，不會同時存在舊配置和新配置的兩個大多數”的特性，實現成員變更。比如上面的情況，就可先將3節點集群[A,B,C]變更為4節點集群[A,B,C,D]，再將4節點集群變更為5節點集群[A,B,C,D]。

為什麼單節點變更不會造成兩個大多數情況的出現呢？我們可以進行如下推理：假設原節點數為2n+1，則舊配置的大多數major_old=n+1，新加入1個節點，新配置節點數為2n+2，則新配置的大多數為major_new=n+2，同時存在兩個大多數所需節點數目為major=major_old+major_new=n+1+n+2=2n+3>2n+2，也就是兩個大多數所需節點數超出了節點總數，故不存在這種情況，如何是刪除成員，其推理過程類似，結論相同。

具體的，我們依舊以這個3節點集群變更為5節點集群為例進行說明。假設現3節點集群[A,B,C]，節點A為leader，配置為[A,B,C]，我們先向集群加入節點D,新的配置為[A,B,C,D]，成員變更通過以下兩步實現：

• 第一步，leader節點A向新節點D同步數據；
• 第二步，leader將新配置[A,B,C,D]作為一個日誌項複製到新配置中的所有節點（A,B,C,D）上，然後將新配置的日誌項應用到本地狀態機，完成單節點變更。

在變更后，現有集群的配置項就是[A,B,C,D]，添加E節點也是同樣的步驟。上面的描述如果理解的比較模糊的話，其實raft是採用將修改集群配置的命令放在日誌條目中來處理的，其修改配置項，就是一條日誌項，其流程與普通的日誌項相同，只不過最後狀態機執行的結果是配置變更。

日誌壓縮

日誌壓縮主要是為了解決無限增長的日誌與有限的存貯空間的矛盾，可以想一個問題：對於已經committed的日誌項，是否有必要一直保存下去？如果沒有必要的話，是否可以對部分已committed的日誌項刪減或壓縮呢？raft的主要的解決辦法是採用快照進行日誌壓縮。

如上圖所示，對於日誌索引5之前的日誌項可以刪除，只保留一個快照（保存有當前狀態以及一些任期索引號等元信息）即可。

具體工程實現時，一般每個節點獨立打快照，當日誌超過一定量會觸發快照操作，具體實現以及更多細節待以後深究。

Client Protocol

raft共識算法真正工作時還需有一個客戶端協議（client protocol），綜合解決一些列的問題。比如會遇到下面這些問題：client怎麼和集群交互呢？client如果知道leader節點的話，可以直接將command發給leader節點，如果不知道的話，可以隨意發給集群中已知的節點，節點會將client的請求轉給leader。其實上面還有個問題，client發送請求（或者command）給leader,但是leader遲遲不給回應怎麼辦？重試是一個辦法。連接的leader崩潰了client怎麼辦？如果client超時重發command，怎麼保證command不被狀態機執行兩次？client生成command的時候要給加上唯一ID，當server的日誌中已存在相同command時會忽略。

附錄

這裏附加一張論文中的截圖，裏面詳細講明了不同節點需要維護什麼信息，每個消息是怎麼定義的，以及消息該如何處理等，不包含日誌壓縮以及成員變更部分：

這裏補充一點，raft共識算法與pbft共識算法解決的是不同的問題，即raft節點不能存在惡意節點，節點消息可以延遲、丟失，但不能造假或作惡，即不能存在拜占庭節點。

本文對raft共識算法做了一個整體的梳理學習，可能會存在某些細節描述不清晰的地方，在真正工程代碼實現時，還會存在更多的細節問題，同時，這裏缺少證明為什麼raft算法是正確的證明，有待今後更深一步理解共識算法后再行補充。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※新北清潔公司,居家、辦公、裝潢細清專業服務

※別再煩惱如何寫文案,掌握八大原則!

※教你寫出一流的銷售文案?

※超省錢租車方案

※FB行銷專家,教你從零開始的技巧

這是why的第 53 篇原創文章

荒腔走板

大家好，我是why。

時間過的真是快，一周又要結束了。那麼，你比上周更博學了嗎？先來一個簡短的荒腔走板，給冰冷的技術文注入一絲色彩。

上面這圖是我之前拼的一副拼圖，一共劃分了800塊，背面無提示，難度極高，我花了兩周的時間才拼完。

拼的是壇城，傳說中佛祖居住生活的地方。

第一次知道這個名詞是 2015 年，窩在寢室看紀錄片《第三極》。

其中有一個片段講的就是僧人為了某個節日用沙繪畫壇城，他們的那種專註，虔誠，真摯深深的打動了我，當宏偉的壇城畫完之後，他靜靜的等待節日的到來。

本以為節日當天眾人會對壇城頂禮膜拜，而實際情況是大家手握一炷香，看着眾僧人快速的摧毀壇城。

還沒來得及仔細欣賞那複雜的美麗的圖案，卻又用掃把掃的乾乾凈凈。

掃把掃下去的那一瞬間，我的心受到了一種強烈的撞擊：可以辛苦地拿起，也可以輕鬆地放下。

看到摧毀壇城的片段的時候，有一個彈幕是這樣說的：

一切有為法，如夢幻泡影，如露亦如電，應作如是觀。

這句話出自《金剛般若波羅蜜經》第三十二品，應化非真分。

因為之前翻閱過幾次《金剛經》，看到這句話的時候我一下就想起了它。

因為讀的時候我就覺得這句話很有哲理，但是也似懂非懂。所以印象比較深刻。

當他再次在壇城這個畫面上以彈幕的形式展現在我的眼前的時候，我一下就懂了其中的哲理，不敢說大徹大悟，至少領悟一二。

觀看摧毀壇城，這個色彩斑斕的世界變幻消失的過程，正常人的感受都是震撼，轉而覺得可惜，心裏久久不能平靜。

但是僧人卻風輕雲淡的說：一切有為法，如夢幻泡影，如露亦如電，應作如是觀。

好了，說迴文章。

先說AtomicLong

關於 AtomicLong 我就不進行詳細的介紹了。

先寫這一小節的目的是預熱一下，拋出一個問題，而這個問題是關於 CAS 操作和 volatile 關鍵字的。

我不知道源碼為什麼這樣寫，希望知道答案的朋友指點一二。

抱拳了，老鐵。

為了順利的拋出這個問題，我就得先用《Java併發編程的藝術》一書做引子，引出這個問題。

首先在書的第 2.3 章節《原子操作的實現原理》中介紹處理器是如何實現原子操作時提到了兩點：

• 使用總線鎖保證原子性。

• 使用緩存鎖保證原子性。

所謂總線鎖就是使用處理器提供一個提供的一個 LOCK # 信號，當一個處理器在總線上輸出此信號時，其他處理器的請求將被阻塞住，那麼該處理器可以獨佔共享內存。

總線鎖保證原子性的操作有點簡單粗暴直接了，導致總線鎖定的開銷比較大。

所以，目前處理器在某些場合下使用緩存鎖來進行優化。

緩存鎖的概念可以看一下書裏面怎麼寫的：

其中提到的圖 2-3 是這樣的：

其實關鍵 Lock 前綴指令。

被 Lock 前綴指令操作的內存區域就會加鎖，導致其他處理器不能同時訪問。

而根據 IA-32 架構軟件開發者手冊可以知道，Lock 前綴的指令在多核處理器下會引發兩件事情：

• 將當前處理器緩存行的數據寫回系統內存。
• 這個寫回內存的操作會使在其他 CPU 里緩存了該內存地址的數據無效。

對於 volatile 關鍵字，毫無疑問，我們是知道它是使用了 Lock 前綴指令的。

那麼問題來了，JVM 的 CAS 操作使用了 Lock 前綴指令嗎？

是的，使用了。

JVM 中的 CAS 操作使用的是處理器通過的 CMPXCHG 指令實現的。這也是一個 Lock 前綴指令。

好，接下來我們看一個方法：

java.util.concurrent.locks.AbstractQueuedLongSynchronizer#compareAndSetState

這個方法位於 AQS 包裏面，就是一個 CAS 的操作。現在只需要關心我框起來的部分。

英文部分翻譯過來是：這個操作具有 volatile 讀和寫的內存語言。

而這個操作是什麼操作？

就是 344 行 unsafe 的 compareAndSwapLong 操作，這個方法是一個 native 方法。

public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);

為什麼這個操作具有 volatile 讀和寫的內存語言呢？

書裏面是這樣寫的：

這個本地方法的最終實現在 openjdk 的如下位置：
openjdk-7-fcs-src-b147- 27_jun_2011\openjdk\hotspot\src\os_cpu\windows_x86\vm\atomic_windows_x86.inline.hpp（對應於Windows操作系統，X86處理器）

intel 的手冊對 Lock 前綴的說明如下。

• 確保對內存的讀-改-寫操作原子執行。在 Pentium 及 Pentium 之前的處理器中，帶有 Lock 前綴的指令在執行期間會鎖住總線，使得其他處理器暫時無法通過總線訪問內存。很顯然，這會帶來昂貴的開銷。從Pentium 4、Intel Xeon及P6處理器開始，Intel使用緩存鎖定（Cache Locking） 來保證指令執行的原子性。緩存鎖定將大大降低lock前綴指令的執行開銷。

• 禁止該指令，與之前和之後的讀和寫指令重排序。

• 把寫緩衝區中的所有數據刷新到內存中。

上面的第2點和第3點所具有的內存屏障效果，足以同時實現 volatile 讀和volatile 寫的內存語義。

好，如果你說你對書上的內容存疑。那麼我帶大家再看看官方文檔：

https://docs.oracle.com/javase/8/docs/api/

我框起來的部分：

compareAndSet 和所有其他的諸如 getAndIncrement 這種讀然後更新的操作擁有和 volatile 讀、寫一樣的內存語義。

原因就是用的到了 Lock 指令。

好，到這裏我們可以得出結論了：

compareAndSet 同時具有volatile讀和volatile寫的內存語義。

那麼問題就來了！

這個操作，在 AtomicLong 裏面也有調用：

而 AtomicLong 裏面的 value 又是被 volatile 修飾了的：

請問：為什麼 compareAndSwapLong 操作已經同時具有 volatile 讀和 volatile 寫的內存語義了，其操作的 value 還需要被 volatile 修飾呢？

這個問題也是一個朋友拋出來探討的，探討的結果是，我們都不知道為什麼：

我猜測會不會是由於操作系統不同而不同。在 x86 上面運行是這樣，其他的操作系統就不一定了，但是沒有證據。

希望知道為什麼這樣做的朋友能指點一下。

好，那麼前面說到 CAS ，那麼一個經典的面試題就來了：

請問，CAS 實現原子操作有哪些問題呢？

• ABA問題。

• 循環時間開銷大。

• 只能保證一個共享變量的原子操作。

如果上面這三點你不知道，或者你說不明白，那我建議你看完本文後一定去了解一下，屬於面試常問系列。

我主要說說這個循環時間開銷大的問題。自旋 CAS 如果長時間不成功，就會對 CPU 帶來比較大的執行開銷。

而回答這個問題的朋友，大多數舉例的時候都會說： “AtomicLong 就是基於自旋 CAS 做的，會帶來一定的性能問題。巴拉巴拉……”

而我作為面試官的時候只是微笑着看着你，讓你錯以為自己答的很完美。

我知道你為什麼這樣答，因為你看了幾篇博客，刷了刷常見面試題，那裡面都是這樣寫的 ：AtomicLong 就是基於自旋 CAS 做的。

但是，朋友，你可以這樣說，但是回答不完美。這題得分別從 JDK 7 和 JDK 8 去答：

JDK 7 的 AtomicLong 是基於自旋 CAS 做的，比如下面這個方法：

while(true) 就是自旋，自旋裏面純粹依賴於 compareAndSet 方法：

這個方法裏面調用的 native 的 comareAndSwapLong 方法，對應的 Lock 前綴指令就是我們前面說到的 cmpxchg。

而在 JDK 8 裏面 AtomicLong 裏面的一些方法也是自旋，但是就不僅僅依賴於 cmpxchg 指令做了，比如還是上面這個方法：

可以看到這裏面還是有一個 do-while 的循環，還是調用的 compareAndSwapLong 方法：

這個方法對應的 Lock 前綴指令是我們前面提到過的 xadd 指令。

從 Java 代碼的角度來看，都是自旋，都是 compareAndSwapLong 方法。沒有什麼差異。

但是從這篇 oracle 官網的文章，我們可以窺見 JDK 8 在 x86 平台上對 compareAndSwapLong 方法做了一些操作，使用了 xadd 彙編指令代替 CAS 操作。

xadd 指令是 fetch and add。

cmpxchg 指令是 compare and swap。

xadd 指令的性能是優於 cmpxchg 指令的。

具體可以看看這篇 oracle 官網的文章：

https://blogs.oracle.com/dave/atomic-fetch-and-add-vs-compare-and-swap

文章下面的評論，可以多注意一下，我截取其中兩個，大家品一品：

然後是這個：

總之就是：這篇文章說的有道理，我們（Dave and Doug）也在思考這個問題。所以我們會在 JIT 上面搞事情，在 x86 平台上把 CAS 操作替換為 LOCK:XADD 指令。

（這個地方我之前理解的有問題，經過朋友的指正後才修改過來。）

所以，JDK 8 之後的 AtomicLong 裏面的方法都是經過改良后， xadd+cmpxchg 雙重加持的方法。

另外需要注意的是，我怕有的朋友懵逼，專門多提一嘴：CAS 是指一次比較並交換的過程，成功了就返回 true，失敗了則返回 false，強調的是一次。而自旋 CAS 是在死循環裏面進行比較並交換，只要不返回 true 就一直循環。

所以，不要一提到 CAS 就說循環時間開銷大。前面記得加上“自旋”和“競爭大”兩個條件。

至於 JDK 8 使用 xadd 彙編指令代替 CAS 操作的是否真的是性能更好了，可以看看這篇 oracle 官網的文章：

https://blogs.oracle.com/dave/atomic-fetch-and-add-vs-compare-and-swap

文章下面的評論，可以多注意一下，我截取其中一個，大家品一品：

經過我們前面的分析，AtomicLong 從 JDK 7 到 JDK 8 是有一定程度上的性能優化的，但是改動並不大。

還是存在一個問題：雖然它可以實現原子性的增減操作，但是當競爭非常大的時候，被操作的這個 value 就是一個熱點數據，所有線程都要去對其進行爭搶，導致併發修改時衝突很大。

所以，歸根到底它的主要問題還是出在共享熱點數據上。

為了解決這個問題，Doug Lea 在 JDK 8 裏面引入了 LongAdder 類。

更加牛逼的LongAdder

大家先看一下官網上的介紹：

上面的截圖一共兩段話，是對 LongAdder 的簡介，我給大家翻譯並解讀一下。

首先第一段：當有多線程競爭的情況下，有個叫做變量集合（set of variables）的東西會動態的增加，以減少競爭。sum() 方法返回的是某個時刻的這些變量的總和。

所以，我們知道了它的返回值，不論是 sum() 方法還是 longValue() 方法，都是那個時刻的，不是一個準確的值。

意思就是你拿到這個值的那一刻，這個值其實已經變了。

這點是非常重要的，為什麼會是這樣呢？

我們對比一下 AtomicLong 和 LongAdder 的自增方法就可以知道了：

AtomicLong 的自增是有返回值的，就是一個這次調用之後的準確的值，這是一個原子性的操作。

LongAdder 的自增是沒有返回值的，你要獲取當前值的時候，只能調用 sum 方法。

你想這個操作：先自增，再獲取值，這就不是原子操作了。

所以，當多線程併發調用的時候，sum 方法返回的值必定不是一個準確的值。除非你加鎖。

該方法上的說明也是這樣的：

至於為什麼不能返回一個準確的值，這就是和它的設計相關了，這點放在後面去說。

然後第二段：當在多線程的情況下對一個共享數據進行更新（寫）操作，比如實現一些統計信息類的需求，LongAdder 的表現比它的老大哥 AtomicLong 表現的更好。在併發不高的時候，兩個類都差不多。但是高併發時 LongAdder 的吞吐量明顯高一點，它也佔用更多的空間。這是一種空間換時間的思想。

這段話其實是接着第一段話在進行描述的。

因為它在多線程併發情況下，沒有一個準確的返回值，所以當你需要根據返回值去搞事情的時候，你就要仔細思考思考，這個返回值你是要精準的，還是大概的統計類的數據就行。

比如說，如果你是用來做序號生成器，所以你需要一個準確的返回值，那麼還是用 AtomicLong 更加合適。

如果你是用來做計數器，這種寫多讀少的場景。比如接口訪問次數的統計類需求，不需要時時刻刻的返回一個準確的值，那就上 LongAdder 吧。

總之，AtomicLong 是可以保證每次都有準確值，而 LongAdder 是可以保證最終數據是準確的。高併發的場景下 LongAdder 的寫性能比 AtomicLong 高。

接下來探討三個問題：

• LongAdder 是怎麼解決多線程操作熱點 value 導致併發修改衝突很大這個問題的？

• 為什麼高併發場景下 LongAdder 的 sum 方法不能返回一個準確的值？

• 為什麼高併發場景下 LongAdder 的寫性能比 AtomicLong 高？

先帶大家看個圖片，看不懂沒有關係，先有個大概的印象：

接下來我們就去探索源碼，源碼之下無秘密。

從源碼我們可以看到 add 方法是關鍵：

裏面有 cells 、base 這樣的變量，所以在解釋 add 方法之前，我們先看一下 這幾個成員變量。

這幾個變量是 Striped64 裏面的。

LongAdder 是 Striped64 的子類：

其中的四個變量如下：

• NCPU：cpu 的個數，用來決定 cells 數組的大小。

• cells：一個數組，當不為 null 的時候大小是 2 的次冪。裏面放的是 cell 對象。

• base : 基數值，當沒有競爭的時候直接把值累加到 base 裏面。還有一個作用就是在 cells 初始化時，由於 cells 只能初始化一次，所以其他競爭初始化操作失敗線程會把值累加到 base 裏面。

• cellsBusy：當 cells 在擴容或者初始化的時候的鎖標識。

之前，文檔裏面說的 set of variables 就是這裏的 cells。

好了，我們再回到 add 方法裏面：

cells 沒有被初始化過，說明是第一次調用或者競爭不大，導致 CAS 操作每次都是成功的。

casBase 方法就是進行 CAS 操作。

當由於競爭激烈導致 casBase 方法返回了 false 后，進入 if 分支判斷。

這個 if 分子判斷有 4 個條件，做了 3 種情況的判斷

• 標號為 ① 的地方是再次判斷 cells 數組是否為 null 或者 size 為 0 。as 就是 cells 數組。

• 標號為 ② 的地方是判斷當前線程對 cells 數組大小取模后的值，在 cells 數組裡面是否能取到 cell 對象。

• 標號為 ③ 的地方是對取到的 cell 對象進行 CAS 操作是否能成功。

這三個操作的含義為：當 cells 數組裡面有東西，並且通過 getProbe() & m算出來的值，在 cells 數組裡面能取到東西（cell）時，就再次對取到的 cell 對象進行 CAS 操作。

如果不滿足上面的條件，則進入 longAccumulate 函數。

這個方法主要是對 cells 數組進行操作，你想一個數組它可以有三個狀態：未初始化、初始化中、已初始化，所以下面就是對這三種狀態的分別處理：

• 標號為 ① 的地方是 cells 已經初始化過了，那麼這個裡面可以進行在 cell 裏面累加的操作，或者擴容的操作。

• 標號為 ② 的地方是 cells 沒有初始化，也還沒有被加鎖，那就對 cellsBusy 標識進行 CAS 操作，嘗試加鎖。加鎖成功了就可以在這裏面進行一些初始化的事情。

• 標號為 ③ 的地方是 cells 正在進行初始化，這個時候就在 base 基數上進行 CAS 的累加操作。

上面三步是在一個死循環裏面的。

所以如果 cells 還沒有進行初始化，由於有鎖的標誌位，所以就算併發非常大的時候一定只有一個線程去做初始化 cells 的操作，然後對 cells 進行初始化或者擴容的時候，其他線程的值就在 base 上進行累加操作。

上面就是 sum 方法的工作過程。

感受到了嗎，其實這就是一個分段操作的思想，不知道你有沒有想到 ConcurrentHashMap，也不奇怪，畢竟這兩個東西都是 Doug Lea 寫的。

然後再補充說明一下，cells 的初始化大小為 2：

cells 的最大值為 CPU 核數：

cell 是被 Contended 註解修飾了，為了解決偽共享的問題：

說起偽共享，我想起了之前的《一個困擾我122天的技術問題，我好像知道答案了》這篇文章中提到的一個猜想：

後來，我也用這個註解去解決偽共享的問題了，可惜最終的實驗結果表明不是這個原因。

那篇文章發布後有很多朋友給我反饋他們的看法，而更多的是在這條路上發現了更多更多的玄學問題，但是最終這些問題的背後都指向了同一個東西：JIT。

扯遠了，說回本文的這個 LongAdder。

總的來說，就是當沒有衝突的時候 LongAdder 表現的和 AtomicLong 一樣。當有衝突的時候，才是 LongAdder 表現的時候，然後我們再回去看這個圖，就能明白怎麼回事了：

好了，現在我們回到前面提出的三個問題：

• LongAdder 是怎麼解決多線程操作熱點 value 導致併發修改衝突很大這個問題的？

• 為什麼高併發場景下 LongAdder 的 sum 方法不能返回一個準確的值？

• 為什麼高併發場景下 LongAdder 的寫性能比 AtomicLong 高？

它們其實是一個問題。

因為 LongAdder 把熱點 value 拆分了，放到了各個 cell 裏面去操作。這樣就相當於把衝突分散到了 cell 裏面。所以解決了併發修改衝突很大這個問題。

當發生衝突時 sum= base+cells。高併發的情況下當你獲取 sum 的時候，cells 極有可能正在被其他的線程改變。一個在高併發場景下實時變化的值，你要它怎麼給你個準確值？當然，你也可以通過加鎖操作拿到當前的一個準確值，但是這種場景你還用啥 LongAdder，是 AtomicLong 不香了嗎？

為什麼高併發場景下 LongAdder 的寫性能比 AtomicLong 高？

你發動你的小腦殼想一想，朋友。

AtomicLong 不管有沒有衝突，它寫的都是一個共享的 value，有衝突的時候它就在自旋。

LongAdder 沒有衝突的時候表現的和 AtomicLong 一樣，有衝突的時候就把衝突分散到各個 cell 裏面了，衝突分散了，寫的當然更快了。

一點思考

本文的題目是《我從LongAdder中窺探到了高併發的秘籍，上面就寫了兩個字……》。

那麼這兩個字是什麼呢？

就是拆分。我淺顯的覺得分佈式、高併發都是基於拆分思想的。

本文的 LongAdder 就不說了。

微服務化、分庫分表、讀寫分離……這些東西都是在拆分，把集中的壓力分散開來。

我們常常說性能不行了，那就堆機器解決，這就是在做拆分。

當然，拆分了帶來好處的同時也是有一定的問題的。

比如老大難的分佈式事務、數據聚合查詢等需求。

舉一個我遇到過的例子吧。

在寫這篇文章之前，我看了 LongAdder 源碼，了解到它這樣的結構后，知道了它和 AtomicLong 之間的差異后，我想起了之前做過的一個需求。

就是賬戶服務，有個大商戶的賬戶是一個熱點賬戶，交易非常的頻繁。

這個賬戶上的金額就相當於是一個共享的熱點數據。

我們當時的做法是把這個賬戶拆分為多個影子賬戶，這樣就把熱點賬戶拆分成了多個影子賬戶，壓力就分攤了。

其實這個思想和 LongAdder 是一脈相承的。

這個場景下拆分帶來的問題是什麼呢？

其中一個問題就是這個賬戶的總餘額是多個影子賬戶之和，而每個影子賬戶上的餘額是時刻在變化的，所以我們不能保證餘額是一個實時準確的值。

但是商戶不關心這個呀。他只關心上日餘額是準確的，每日對賬都能對上就行了。

我們在滿足需求的同時，性能還上去了。

還有一個簡單的思考是如果我們把“實現原子操作進行加減”這句話當做一個需求。

我個人拙見是這樣的，AtomicLong 類就是實現了這個需求，交付出去后，它能用，能正常工作，而且還附送了一個功能是每次都給你返回一個準確的值。

而 LongAdder 就是更加優雅的實現了這個需求，它是在原有的基礎上進行了迭代開發，功能還是能一樣的實現，沒有附加功能，但是針對某些場景來說，更好用了。

它們傳遞給我的思想不是我們常說的：先上，能跑就行，後期再迭代。

而是：它確實能跑，但是還有更加快，更加優雅的實現方式，我們可以實現它。

這是我們需要學習的地方。

最後說兩句（求關注）

才疏學淺，難免會有紕漏，如果你發現了錯誤的地方，還請你留言指出來，我對其加以修改。

感謝您的閱讀，我堅持原創，十分歡迎並感謝您的關注。

我是 why，一個被代碼耽誤的文學創作者，不是大佬，但是喜歡分享，是一個又暖又有料的四川好男人。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※教你寫出一流的銷售文案?

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※回頭車貨運收費標準

※別再煩惱如何寫文案,掌握八大原則!

※超省錢租車方案

※產品缺大量曝光嗎?你需要的是一流包裝設計!

本周我們繼續來看5道磨人的小妖精，圖解leetcode6-10～

多說一句，leetcode10 殺死了233醬不少腦細胞…

另：

沉迷算法，無法自拔。快來加入我們吧！

別忘了233醬的一條龍服務：

公眾號文章題解 -> 私信答疑 -> 刷題群答疑 -> 視頻講解

我們的目的是成為套路王～

嘿嘿，廣告完畢 , Let’s go!

leetcode6: Z 字形變換

題目描述：

將一個給定字符串根據給定的行數，以從上往下、從左到右進行 Z 字形排列。

題目示例:

輸入: s = "LEETCODEISHIRING", numRows = 4
輸出: "LDREOEIIECIHNTSG"

解釋:

L     D     R
E   O E   I I
E C   I H   N
T     S     G

解題思路:

相信小夥伴看到這道題目，也和233一樣覺得Z字形排列的字符串冥冥中有些規律。為了方便解釋 ，我們假設輸入：

字符串s=”0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15″
numRows=4
注意： s中的輸入字符依次為：為0-15，中間的空格是我為了展示清楚額外加的。

那麼s的Z字形排列如下：

需要輸出的結果是：“0 6 12 15 7 11 13 2 4 8 10 14 3 9 15”

假設我們將Z字形排列后的字符串每一行i 用一個數組arr[i]存起來，最後按行數i的順序輸出arr[i]中的值，那麼就可以得到最終的輸出結果。

如何知道字符串s中的各個字符在哪個arr數組的哪個索引位置呢？這就是我們用数字字符的字符串來舉例子的好處了，因為数字的值就對應着字符在字符串s中的下標。當我們遍歷字符串s時，是我們可以用pointer表示當前遍歷的字符所對應的行數i，代表這個字符是要放到arr[i]中的。

我們可以發現每當遍歷numRows=4 個字符，pointer就從 0->3 轉化為 3->0。所以我們可以用一個flag記錄pointer的變化量。

思路有了，我們來看一下時間空間複雜度：

• 時間複雜度：遍歷一遍字符串s: O(n)。
• 空間複雜度：數組arr的存儲：O(n)。

可以寫出代碼嗎：）

Java版本

class Solution {
    public String convert(String s, int numRows) {
        if(numRows <= 1){
            return s;
        }
        List<StringBuilder> arr = new ArrayList<>();
        for(int i = 0 ;i< numRows;i++){
            arr.add(new StringBuilder());
        }
        int flag = -1;
        int pointer = 0;
        for(int i =0;i<s.length();i++){
           char ch = s.charAt(i);
           arr.get(pointer).append(ch);
           if(pointer == 0 || pointer == numRows -1) flag = - flag;
            pointer += flag;
            
        }
        StringBuilder res = new StringBuilder();
        for(StringBuilder row : arr) res.append(row);
        return res.toString();
    }
}

leetcode7: 整數反轉

題目描述：

給出一個 32 位的有符號整數，你需要將這個整數中每位上的数字進行反轉。

題目示例:

輸入: 123
輸出: 321

輸入: -123
輸出: -321

輸入: 120
輸出: 21

注意:
假設我們的環境只能存儲得下 32 位的有符號整數，則其數值範圍為 [−231,  231 − 1]。請根據這個假設，如果反轉后整數溢出那麼就返回 0。

解題思路:
這道題考的還是 數學運算。

Step1:需要分別取出十進制数字的個位，十位，百位..一直到最高位的数字。

阿姨來教你小學數學的除法運算：

所以當我們 取余再取模 就可以得到高位的数字。

Step2:將取出來的個位，十位，百位..一直到最高位的数字 依次放到 最高位,…,百位，十位，個位。

阿姨來教你小學數學的乘法運算：

至於示例中列舉的幾個邊界條件，Java中的整數是帶有符號的。剛好符合我們的乘除運算。

另外，需要判斷乘法計算時正負数字的越界問題。當然如果res用long表示，也就不需要考慮這個問題了。代碼如下：

Java版本

class Solution {
    public int reverse(int x) {
        int res = 0;
        while(x!=0){
            if(x>0 && res > ((Integer.MAX_VALUE-x%10)/10)) return 0;
            if(x<0 && res < ((Integer.MIN_VALUE-x%10)/10)) return 0;
            res = res*10 + x%10;
            x/=10;
        }
        return res;
    }
}

leetcode8: 字符串轉換整數(atoi)

題目描述：

請你來實現一個 atoi 函數，使其能將字符串轉換成整數。

首先，該函數會根據需要丟棄無用的開頭空格字符，直到尋找到第一個非空格的字符為止。接下來的轉化規則如下：

如果第一個非空字符為正或者負號時，則將該符號與之後面盡可能多的連續数字字符組合起來，形成一個有符號整數。
假如第一個非空字符是数字，則直接將其與之後連續的数字字符組合起來，形成一個整數。
該字符串在有效的整數部分之後也可能會存在多餘的字符，那麼這些字符可以被忽略，它們對函數不應該造成影響。
注意：假如該字符串中的第一個非空格字符不是一個有效整数字符、字符串為空或字符串僅包含空白字符時，則你的函數不需要進行轉換，即無法進行有效轉換。

在任何情況下，若函數不能進行有效的轉換時，請返回 0 。

提示：

本題中的空白字符只包括空格字符 ‘ ‘ 。
假設我們的環境只能存儲 32 位大小的有符號整數，那麼其數值範圍為 [−231,  231 − 1]。如果數值超過這個範圍，請返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。

題目示例:

示例 1:
輸入: "42"
輸出: 42

示例 2:
輸入: "   -42"
輸出: -42
解釋: 第一個非空白字符為 '-', 它是一個負號。
     我們盡可能將負號與後面所有連續出現的数字組合起來，最後得到 -42 。

示例 3:
輸入: "4193 with words"
輸出: 4193
解釋: 轉換截止於数字 '3' ，因為它的下一個字符不為数字。

示例 4:
輸入: "words and 987"
輸出: 0
解釋: 第一個非空字符是 'w', 但它不是数字或正、負號。
     因此無法執行有效的轉換。

示例 5:
輸入: "-91283472332"
輸出: -2147483648
解釋: 数字 "-91283472332" 超過 32 位有符號整數範圍。 
     因此返回 INT_MIN (−231) 。

解題思路:
放這麼多 題目示例 阿姨並不是為了湊字數，而是這類問題就是屬於考邊界情況的問題，邊界情況拎清了，就不會被磨到了～

假設輸入一個字符串 ” -4193 with words” ， 我們可以從左到右遍歷這個字符串，用k 表示當前遍歷到的字符：

另外，我們還需要注意 示例5的情況，當乘法計算時的值超過INT_MAX or INT_MIN時，結束並返回 INT_MAX or INT_MIN.

Java版本

class Solution {
    public int myAtoi(String str) {
        int res = 0;
        int k = 0;

        while(k< str.length() &&  ' ' == str.charAt(k))k++;
        int minus = 1;
        if(str.length() == k) return res;
        if('-' == str.charAt(k)) {
            minus = -1;
            k++;
        }else if('+' == str.charAt(k)){
            k++;
        }

        while(k<str.length() && str.charAt(k) >= '0' && str.charAt(k) <='9'){
            int x = str.charAt(k) - '0';
            if(minus >0 && res> (Integer.MAX_VALUE - x)/ 10){
                return Integer.MAX_VALUE;
            }
            //-res * 10 - str.charAt(k) < Integer.MIN_VALUE
            if(minus <0 && -res < (Integer.MIN_VALUE + x)/10) 
                return Integer.MIN_VALUE;
            //最大的負數是存不下來的
            if((-res * 10 - x) == Integer.MIN_VALUE ) {
                return Integer.MIN_VALUE;
            }
            res = res* 10 + x;
            k++;
        }
        res *= minus;
        return res;

    }
}

leetcode9: 迴文數

題目描述：

判斷一個整數是否是迴文數。迴文數是指正序（從左向右）和倒序（從右向左）讀都是一樣的整數。

題目示例:

示例 1:

輸入: 121
輸出: true
示例 2:

輸入: -121
輸出: false
解釋: 從左向右讀, 為 -121 。 從右向左讀, 為 121- 。因此它不是一個迴文數。
示例 3:

輸入: 10
輸出: false
解釋: 從右向左讀, 為 01 。因此它不是一個迴文數。

解題思路:

上篇文章中我們講過最長迴文子串的查找。再來看這道題就很easy了。這道題的解法也很多：
比如我們可以把它變為字符串。然後reverse一下，判斷前後兩個字符串是否相等。

但是我們用一種更簡單的方式，只需要反轉整數，然後判斷兩個整數是否相等，就可以確定是不是迴文整數。又回到leetcode7了，有沒有覺得阿姨的乘除法運算還是有幫助的：）

Java版本

class Solution {
    public boolean isPalindrome(int x) {
        
        if(x<0) return false;
        if(x<=9) return true;
        int oringin = x;
        int res = 0;
        while(x>0){
            //如果越界了說明不對稱
            res = res*10 + x%10;
            x/=10;
        }
        return oringin == res;
    }
}

leetcode10: 正則表達式匹配

題目描述：

給你一個字符串 s 和一個字符規律 p，請你來實現一個支持 ‘.’ 和 ‘*’ 的正則表達式匹配。

‘.’ 匹配任意單個字符
‘*’ 匹配零個或多個前面的那一個元素
所謂匹配，是要涵蓋 整個 字符串 s的，而不是部分字符串。

說明:

• s 可能為空，且只包含從 a-z 的小寫字母。
• p 可能為空，且只包含從 a-z 的小寫字母，以及字符 . 和 *。

題目示例:

示例 1:
輸入:
s = "aa"
p = "a*"
輸出: true
解釋: 因為 '*' 代表可以匹配零個或多個前面的那一個元素, 在這裏前面的元素就是 'a'。因此，字符串 "aa" 可被視為 'a' 重複了一次。

示例 2:
輸入:
s = "ab"
p = ".*"
輸出: true
解釋: ".*" 表示可匹配零個或多個（'*'）任意字符（'.'）。

神奇的.*來了，Hard模式，大家坐好～

判斷 字符串s 是否與 一個 可能還有“.” or “*” 的字符規律 p 匹配，其實就是從 p 代表的所有的字符串中枚舉出一個 匹配值。 簡單暴力枚舉的時間複雜度是指數級的。我們需要考慮對於求解一個最優解 或 匹配解的類似問題，有哪些可以降低時間複雜度的方案？

好了，不饒彎子了，動態規劃 要來了。

溫馨後記：寫着寫着就列舉了一堆動態規劃的理論，比較了解的朋友可以直接翻過這段看後面這一題的圖解。

解題之前，我們先了解下：動態規劃是什麼？為什麼動態規劃能降低時間複雜度？什麼類型的問題又能用動態規劃去解決？如何構造解題步驟？

動態規劃是什麼

動態規劃與分治方法相似，都是通過組合子問題的解來求解原問題。

分治算法將問題劃分為互不相交的子問題，遞歸地求解子問題，再將他們的解組合起來，求出原問題的解。如歸併排序，劃分的左右排序子問題是對不同的数字序列進行排序的，最後再把他們合併起來。

而動態規劃應用於子問題重疊的情況，即不同的子問題具有公共的子子問題。這種情況下分治算法需要對子子問題反覆求解，而動態規劃算法只對子子問題求解一次，將其結果保存到備忘錄中 or 按照 自底向下 的順序 求解每個子問題（也就是保證在求解子問題時，它所依賴的子子問題的解已經求出來了）這兩種方式，避免不必要的計算工作，降低時間複雜度。

舉一個簡單的斐波那契數列的例子：

斐波那契數列指的是這樣一個數列：
1、1、2、3、5、8…

相信小夥伴們都知道，它的遞推規律是：

假設求f(10),則遞推公式展開為：

可以看到其中有大量的重複子問題：f(6),f(5) 等。

動態規劃的兩種做法就是：
1.用 遞歸的代碼求解時，將第一次計算的f(6)保存起來，如f(8)中的f(6). 這樣再求解f(7)中的f(6)就可以直接獲取到結果了
2.按照求f(3), ->(4)->…->f(10)的自底向下的順序求解，這樣再求 f(8)時，只需要保存下來 f(7) 和 f(6)的值，就可以求出了，f(10)同理。這種方式大多是循環的寫法。

動態規劃解決的問題類型

初步明白后，我們再來看下動態規劃解決問題的類型：

極客時間的王爭大佬 概括為： 一個模型，三個特徵。

一個模型：多階段決策最優解模型
我們一般是用動態規劃來解決最優問題。而解決問題的過程，需要經歷多個決策階段。每個決策階段都對應着一組狀態。然後我們尋找一組決策序列，經過這組決策序列，能夠產生最終期望求解的最優值。
特徵1:最優子結構

指的是，問題的最優解包含子問題的最優解。反過來說就是，我們可以通過子問題的最優解，推導出問題的最優解。如果我們把最優子結構，對應到我們前面定義的動態規劃問題模型上，那我們也可以理解為，後面階段的狀態可以通過前面階段的狀態推導出來。

特徵2:無後效性

無後效性有兩層含義，第一層含義是，在推導後面階段的狀態的時候，我們只關心前面階段的狀態值，不關心這個狀態是怎麼一步一步推導出來的。第二層含義是，某階段狀態一旦確定，就不受之後階段的決策影響。無後效性是一個非常“寬鬆”的要求。只要滿足前面提到的動態規劃問題模型，其實基本上都會滿足無後效性。

特徵3. 重複子問題
這個就是我們前面提到的，不同的決策序列，到達某個相同的階段時，可能會產生重複的狀態。

動態規劃的解題步驟

Step1.刻畫一個最優解的結構特徵
也就是能夠把問題抽象轉化為一種數學描述，通俗說 就是 狀態的定義。如上述斐波那契數列 中 f(n）就是狀態的定義。

Step2.遞歸地定義最優解的值。
就是問題與子問題之間的遞推表達式是什麼，通俗說 就是 狀態轉移方程的定義。如上述斐波那契數列 中的f(n) = f(n-1) + f(n-2)

Step3.計算最優解的值
就是採用的動態規劃具體計算的做法，包括 遞歸+備忘錄 or 循環+自底向下 求解兩種方式。

Step4.利用計算出的信息構造一個最優解
因為我們步驟一定義的狀態有時並不是我們直接要求的最優解，所以這一步就是利用狀態和狀態轉移方式 表達出我們最終要求的最優解怎麼得到。

我們會根據leetcode10來理解這些理論知識。

解題思路:

Step1.抽象出狀態

這個問題實際求的是字符串s能否從字符規律p代表的所有字符串集合中找出一個匹配值。一般求兩個字符串的匹配問題的狀態用二維的數組來定義，為什麼。。聽大佬說：靠經驗，靠悟。我們定義：
dp[i,j] : 代表 所有 字符串s[0,i-1] (前i個字符) 和 字符規律p[0,j-1] （前j個字符）的匹配方案 集合。
dp[i,j] 的值： 代表是否存在一種方案 使得 字符規律p 匹配 字符串s。這個值就是我們這個問題的解。true：存在。false：不存在。

Step2.遞歸地定義最優解的值。

這一步其實就是求狀態遞推式，找出問題dp[i,j] 和子問題之間的關係。

對於字符串s[i] 和 p[j] 是否匹配，因為p[j] 可能是* or . 。我們需要枚舉出p所代表的所有字符串。我們我們可以從最後的字符 s[i] 和 p[j]來考慮。

可分為p[j] == * or p[j] != * 兩種情況。因為 ‘*’ 代表着0-多個字符，會影響p的枚舉數。’.’ 我們只需要把它當成一個萬能字符就好，’.’ 不會影響p的枚舉數量。

• 當p[j] != '*' 時，則 s 與 p 是否匹配 取決於 s[i] 是否等於 p[j] && dp[i][j] 是否為true

• 當p[j] == '*' 時，我們需要枚舉* 代表的從0-多個字符的字符序列集合中，s 是否與他們其中之一匹配。

如圖所示，考慮p[j] == '*' 所代表的字符數，我們需要列舉出 組成dp[i+1,j+1] 的所有可能情況，同時我們其實靠yy也能推斷出：
dp[i+1,j+1] 和 它的子問題：dp[i,j+1] 的關係，圖中我也有列舉出公式推導來源。

這裡有一點需要注意： dp[i+1,j+1]才表示s[0,i] 和 p[0,j] 匹配。因為s[0]就代表了第一個字符。而我們也需要表示 s長度為0的dp[0,..]的值。不然會影響到我們遞推公式的求值。

好了，到這裏我們先總結下 這個問題動態規劃解法的狀態和狀態轉移方程：

Step3.計算最優解的值。
這個步驟就是具體計算遞推公式dp[i+1,j+1]的過程了，我們可以採用 循環+ 自底向下的方式來求解，也就是對於二維數組先填第0行的值，再填第0列的值，以此類推。
假設s=”aa”, p=”a*” 。則它的二維填狀態表的順序和結果為：

Step4.利用計算出的信息構造一個最優解

在Step1的時候，我們其實就定義了。 s與p是否匹配 等價於 dp[i+1][j+1] 的值 是否為 true。 所以我們只需要返回 dp[i+1][j+1]的值 就是這道題的結果。

徹底完了，看懂了沒，上代碼吧。

Java版本

class Solution {
    public boolean isMatch(String s, String p) {
        int slen = s.length();
        int plen = p.length();
        //需要分別取出s和p為空的情況，所以dp數組大小+1
        boolean[][] dp = new boolean[slen + 1][plen + 1];
        //初始化dp[0][0]=true,dp[0][1]和dp[1][0]~dp[s.length][0]默認值為false所以不需要顯式初始化
        dp[0][0] = true;
        //填寫第一行dp[0][2]~dp[0][p.length]
        for (int k = 2; k <= plen; k++) {
            //p字符串的第2個字符是否等於'*',此時j元素需要0個，所以s不變p減除兩個字符
            dp[0][k] = p.charAt(k - 1) == '*' && dp[0][k - 2];
        }
        //填寫dp數組剩餘部分
        for (int i = 0; i < slen; i++) {
            for (int j = 0; j < plen; j++) {
                //p第j個字符是否為*
                if (p.charAt(j) == '*') {
                    //兩種情況:1.s不變[i+1],p移除兩個元素[j+1-2]。
                    // 2.比較s的i元素和p的j-1(因為此時j元素為*)元素,相等則移除首元素[i+1-1],p不變。
                    dp[i + 1][j + 1] = dp[i + 1][j - 1] ||
                            (dp[i][j + 1] && headMatched(s, p, i, j - 1));
                } else {
                    //s的i元素和p的j元素是否相等,相等則移除s的i元素[i+1-1]和p的j元素[j+1-1]
                    dp[i + 1][j + 1] = dp[i][j] && headMatched(s, p, i, j);
                }
            }
        }
        return dp[slen][plen];
    }

    //判斷s第i個字符和p第j個字符是否匹配
    public boolean headMatched(String s, String p, int i, int j) {
        return s.charAt(i) == p.charAt(j) || p.charAt(j) == '.';
    }

}

能看到這裏看來是真愛了，233醬都要對你豎起大拇指，要不要也在看，轉發 對233醬豎起大拇指 …… ^ _ ^。不管對文章是否有疑問，都歡迎可愛的你加入我們的刷題群，有疑問233醬會在群里答疑哦～

參考資料：
[1].《算法導論》
[2].https://time.geekbang.org/column/article/75702

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※新北清潔公司,居家、辦公、裝潢細清專業服務

※別再煩惱如何寫文案,掌握八大原則!

※教你寫出一流的銷售文案?

※超省錢租車方案

※FB行銷專家,教你從零開始的技巧

前言

JDK的bin目錄中有一系列的小工具，除了java.exe、javac.exe這兩個編譯和運行Java程序外，還有打包、部署、簽名、調試、監控、運維等各種場景都會用到這些小工具。

這些工具根據軟件可用性和授權的不同，可以把它們劃分為三類：

• 商業授權工具： 主要是JMC（Java Mission Control）及它要使用到的JFR（Java Flight Recorder）,JMC在個人開發環境中使用是免費的，但是在商業環境中使用它則是付費的。
• 正式支持工具： 這一類工具屬於被長期支持的工具，不同平台、不同版本的JDK之間，這類工具可能會略有差異，但是不會出現某一個工具突然消失的情況。
• 實驗性工具： 這一類工具在它們的使用說明中被聲明為“沒有技術支持，並且是實驗性質的”（Unsupported and Experimental）產品，日後可能會轉載，也可能會在某個JDK版本中國無聲無息地消失。

jps：虛擬機進程狀態工具

JDK的一些小工具都參考了UNIX的命名方式，jps（JVM Process Status Tool）是其中的典型。
功能也是和UNIX的ps的命令類似：
可以列出正在運行的虛擬機進程，並显示虛擬機執行主類（Main Class，main()函數所在的類）名稱以及這些進程的本地虛擬機唯一ID（LVMID，Local Virtual Machine Identifier）。
jps命令格式：

jps [ options ]  [ hostid ]

jps工具主要選項：

jstat：虛擬機統計信息監視工具

jstat（ JVM Statistics Monitoring Tool ）是用戶監視虛擬機各種運行狀態信息的命令行工具。可以显示本地虛擬機進程中 類加載、內存、垃圾收集、即時編譯等運行時數據，這個命令是在服務器是哪個運行期定位虛擬機性能問題的常用工具。
jstat 命令格式為：

jstat [ option  vmid [ interval [ s | ms ] [ count ] ] ]

參數interval 和 count 代表查詢間隔和次數，如果省略這2個參數，說明只查詢一次假設需要每250毫秒查詢一次進程 1440 垃圾收集狀況，一共查詢20次，那命令應當是：

jstat -gc 1440 250 20 

option 代表用戶希望查詢的虛擬機信息，主要分三類：
類加載、垃圾收集、運行期間編譯狀況。
jstat工具主要選項

jinfo：Java配置信息工具

jinfo（Configuration Info for Java）的作用是實時查看和調整虛擬機各項參數。使用jps命令的-v參數可以查看虛擬機啟動時显示指定的參數列表，但如果想知道未被显示指定的參數的系統默認值，除了去找資料外，就只能使用jinfo的-flag選項進行查詢了。jinfo還可以使用-sysprops選項把虛擬機進程的

System.getProperties()

的內容打出來。
jinfo 命令格式：

jinfo [ option ] pid

jmap：Java內存映像工具

jmap （Memory Map for Java）命令用於生成堆轉儲快照（一般稱為heapdump 或 dump文件）。
jmap的作用並不僅僅是為了獲取堆轉儲快照，它還可以查詢finalize執行隊列、Java堆和方法區的詳細信息，如空間使用率、當前用的是哪種收集器等。
jmap 命令格式：

jmap [ option ] vmid

jmap工具主要選項

jhat：虛擬機堆轉儲快照分析工具

JDK提供jhat（JVM Heap Analysis Tool）命令與jmap搭配使用，來分析jmap生成的堆轉儲快照。jhat內置了一個微型的HTTP/Web服務器，生成堆轉儲快照的分析結果后，可以在瀏覽器中查看。但是一般在實際工作中，都不會直接使用jhat命令來分析堆轉儲快照文件，一是因為分析工作耗時而且極為耗費資源，一般不會直接在服務器上使用，而是在其他機器上進行分析。二是jhat的分析功能比較簡陋，不如VisualVM，以及一些專業的分析工具例如：Eclipse Memory Analyzer、IBM HeapAnalyzer。

jstack：Java堆棧跟蹤工具

jstack（Stack Trace for Java）命令用於生成虛擬機當前時刻的線程快照（一般稱為threaddump或者javacore文件）。
線程快照就是當前虛擬機內每一條線程正在執行的方法堆棧的集合，生成線程快照的目的通常是定位線程出現長時間停頓的原因，如線程死鎖、死循環、請求外部資源導致長時間掛起等，都是導致線程長時間停頓的常見原因。
jstack命令格式：

jstack [ option ] vmid 

線程出現停頓時通過jstack來查看各個線程的調用堆棧，就可以獲知沒有響應的線程到底在後頭做些什麼事情，或者等待着什麼資源。
jstack工具主要選項

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※超省錢租車方案

※別再煩惱如何寫文案,掌握八大原則!

※回頭車貨運收費標準

※教你寫出一流的銷售文案?

※FB行銷專家,教你從零開始的技巧

在前面兩篇中，我們從基本概念理解了canal是一個什麼項目，能應用於什麼場景，然後通過一個demo體驗，有了基本的體感和認識。

從這一篇開始，我們將從源碼入手，深入學習canal的實現方式。了解canal相關功能的實現方式，其中有很多機制是非常值得深入了解的，從代碼實現角度去學習實時數據訂閱與同步的實現與核心技術點。當然，如果要在生產中使用這個開源項目，了解源碼更是必不可少，是解決問題和新特性定製的前提條件。

本文使用的版本是1.1.4，這也是筆者寫這篇博客時的最新穩定版。

1.準備工作

下載源碼

git clone https://github.com/alibaba/canal.git

切換到1.1.4這個tag

git checkout canal-1.1.4

 

或者可以關注我的源碼註釋版本(正在不斷更新中)

https://github.com/saigu/JavaKnowledgeGraph/tree/master/code_reading/canal

2.canal項目模塊介紹

canal項目是基於maven構建的，將不同的功能模塊劃分了不同的子模塊。

我們可以簡單執行可執行模塊deployer，也可以將模塊通過maven依賴的方式，將你需要的子模塊引入到你自己的項目中進行使用開發。

 

簡單介紹下核心模塊的功能：

• deployer模塊：獨立部署模塊，用於canal-server的獨立啟動，包括本地配置解析、拉取遠程配置、啟動canal-server。
• server模塊：canal-server的實現邏輯，一個canal-server一般是一個jvm進程。重點關注兩種canal-server的實現方式，內嵌型的canalServerEmbed和獨立使用的canalServerWithNetty。新版本中新增了直接對接mq的canal-server實現。
• instance模塊：具體實時訂閱任務是由一個個instance組成的，每個canal-server中可以同時運行多個instance。instance由parser、sink、store三個重點模塊組成。
• parser模塊：數據源接入，模擬slave協議和master進行交互，協議解析。parser模塊依賴於dbsync、driver模塊。
• sink模塊：將parser抓取到的數據，進行過濾，加工，然後發送到store模塊進行存儲。核心接口為CanalEventSink。
• store模塊：數據存儲模塊，類似內存模式到消息隊列，本質上是一個RingBuffer。核心接口為CanalEventStore。
• meta模塊：增量訂閱&消費信息管理器，核心接口為CanalMetaManager，主要用於記錄canal消費到的mysql binlog的位置
• client模塊：項目最早的消費客戶端，通過將client模塊引入自己的項目中，然後直接消費canal-server獲取的數據。
• client-adapter模塊：1.1.x后新出的模塊，可以獨立部署為canal-server的消費服務端，是一個springboot項目。通過SPI機制，能夠加載不同plugins，將消費信息投遞到ES\hbase\rdb等下游。
• admin模塊：1.1.x新出的模塊，可以獨立部署為canal-server的控制台，配置canal-server、instance相關配置，非常好用。

3.模塊關聯

那這些模塊之間是如何組織、如何關聯的呢？

我們從整體到局部來看一下。

整體架構關聯，包括admin模塊、server模塊、client-adapter模塊

 

1）server模塊是服務端核心模塊，用來拉取binlog的實時變更，然後投遞到客戶端。

2）server可以通過配置，選擇投遞到MQ，或者是啟動一個netty，讓客戶端來拉取。

3）client-adapter就是一個獨立部署到服務，可以直接拉取canal-server的消息（或者拉取mq的消息），轉發到對應RDS/Redis/HBase，當然，你也可以自己實現一個轉發到redis的adapter

4）admin模塊是管理控制台，可以調度canal-server組成一個個集群實現instance的高可用、可以更改server、instance的配置信息。

Canal-server模塊局部關係，包括deployer模塊、server模塊、instance模塊、parser模塊、sink模塊、store模塊、meta模塊、client模塊。

 

1）deployer模塊是一個啟動模塊，可以啟動canal-server。

2）一個server是一個獨立應用，是一個jvm進程，裏面可以有多個instance對象。

3）instance內包括了parser、sink、store、meta

4）parser負責獲取binlog變更，然後sink將parser獲取的binlog變更轉換為event，存入store。

5）meta是元信息管理器

6）client模塊可以內嵌入你的應用，用來消費canal-server的消息事件。

基本上核心模塊的關係就是這樣了，後續會按照模塊的維度進行源碼分析，敬請期待。

 

都看到最後了，原創不易，點個關注，點個贊吧～

文章持續更新，可以微信搜索「阿丸筆記 」第一時間閱讀，回復關鍵字【學習】有我準備的一線大廠面試資料。

知識碎片重新梳理，構建Java知識圖譜： github.com/saigu/JavaK…（歷史文章查閱非常方便）

 

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※新北清潔公司,居家、辦公、裝潢細清專業服務

※別再煩惱如何寫文案,掌握八大原則!

※教你寫出一流的銷售文案?

※超省錢租車方案

※FB行銷專家,教你從零開始的技巧

我是風箏，公眾號「古時的風箏」，一個兼具深度與廣度的程序員鼓勵師，一個本打算寫詩卻寫起了代碼的田園碼農！
文章會收錄在 JavaNewBee 中，更有 Java 後端知識圖譜，從小白到大牛要走的路都在裏面。

這是上篇文章 有趣的條漫版 HashMap，25歲大爺都能看懂 的文字版。有不少同學說條漫版的比較有意思，簡單易懂，但是畢竟圖片畫不了那麼詳細，只能從大面而上理解。

真正的了解細節，還得看這一篇。其實是這篇先寫完，然後畫了不少圖片，所以就寫了一篇圖片版的。本篇 7000 多字，建議三連呦。

在 Java 中，最常用的數據類型是 8 中基本類型以及他們的包裝類型以及字符串類型，其次應該就是 ArrayList和HashMap了吧。HashMap存的是鍵值對類型的數據，其存儲和獲取的速度快、性能高，是非常好用的一個數據結構，每一個 Java 開發者都肯定用過它。

而且 HashMap的設計巧妙，其結構和原理也經常被拿去當做面試題。其中有很多巧妙的算法和設計，比如 Hash 算法、拉鏈法、紅黑樹設計等，值得每一個開發者借鑒學習。

想了老半天，怎麼才能簡單易懂的把 HashMap說明白呢，那就從我理解它的思路和過程去說吧。要理解一個事物最好的方式就是先了解整體結構，再去追究細節。所以，我們先從結構談起。

先從結構說起

拿我自身的一個體會來說吧，風箏我作為一個專業路痴，對於迷路這件事兒絕不含糊，雖然在北京混跡多年，但是只在中關村能分清南北，其他地方，哪怕是我每天住的小區、每天工作的公司也分不太清方向，回家只能認一條路，要是打車換條路回家，也得迷糊一陣，這麼說吧，在小區前面能回家，小區後面找不到家。去個新地方，得盯着地圖看半天。這時，我就在想啊，要是我能在城市上空俯瞰下面的街道，那我就再也不怕找不到回家的路了。這不就是三體里的降維打擊嗎，站在高維的立場，理解低維的事物，那就簡單多了。

理解數據結構也是一個道理，大多數時候，我們都是停留在會用的層面上，理解一些原理也只是支離破碎的，困在數據機構的迷宮裡跌跌撞撞，迫切的需要一張地圖或者一架直升機。

先來看一下整個 Map家族的集成關係圖，一看東西還不少，但其他的可能都沒怎麼用過，只有 HashMap最熟悉。

以下描述可能不夠專業，只為簡單的描述 HashMap的結構，請結合下圖進行理解。

HashMap主體上就是一個數組結構，每一個索引位置英文叫做一個 bin，我們這裏先管它叫做桶，比如你定義一個長度為 8 的 HashMap，那就可以說這是一個由 8 個桶組成的數組。當我們像數組中插入數據的時候，大多數時候存的都是一個一個 Node 類型的元素，Node 是 HashMap中定義的靜態內部類。

當插入數據（也就是調用 put 方法）的時候，並不是按順序一個一個向後存儲的，HashMap中定義了一套專門的索引選擇算法，叫做散列計算，但散列計算存在一種情況，叫哈希碰撞，也就是兩個不一樣的 key 散列計算出來的 hash 值是一致的，這種情況怎麼辦呢，採用拉鏈法進行擴展，比如圖中藍色的鏈表部分，這樣一來，具有相同 hash 值的不同 key 即可以落到相同的桶中，又保證不會覆蓋之前的內容。

但隨着插入的元素越來越多，發生碰撞的概率就越大，某個桶中的鏈表就會越來越長，直到達到一個閾值，HashMap就受不了了，為了提升性能，會將超過閾值的鏈錶轉換形態，轉換成紅黑樹的結構，這個閾值是 8 。也就是單個桶內的鏈表節點數大於 8 ，就會將鏈表變身為紅黑樹。

以上概括性的描述就是 HashMap的整體結構，也是我們進一步研究細節的藍圖。我們將從中抽取出幾個關鍵點一一解釋，從整體到細節，降維打擊 HashMap。

接下來就是說明為什麼會設計成這樣的結構以及從單純數組到桶內鏈表產生，接着把鏈錶轉換成紅黑樹的詳細過程。

認清幾個關鍵概念

存儲容器

因為HashMap內部是用一個數組來保存內容的，數組定義如下：

transient Node<K,V>[] table;

Node 類型

table 是一個 Node類型的數組，Node是其中定義的靜態內部類，主要包括 hash、key、value 和 next 的屬性。比如之後我們使用 put 方法像其中加鍵值對的時候，就會轉換成 Node 類型。

static class Node<K,V> implements Map.Entry<K,V> {
  final int hash;
  final K key;
  V value;
  Node<K,V> next;
}

TreeNode

前面說了，當桶內鏈表到達 8 的時候，會將鏈錶轉換成紅黑樹，就是 TreeNode類型，它也是 HashMap中定義的靜態內部類。

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
  TreeNode<K,V> parent;  // red-black tree links
  TreeNode<K,V> left;
  TreeNode<K,V> right;
  TreeNode<K,V> prev;    // needed to unlink next upon deletion
  boolean red;
}

容量和默認容量

容量就是 table 數組的長度，也就是我們所說的桶的個數。其定義如下

int threshold;

默認是 16，如果我們在初始化的時候沒有指定大小，那就是 16。當然我們也可以自己指定初始大小，而 HashMap 要求初始大小必須是 2 的 冪次方。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

元素個數

容量是指定了桶的個數，而 size 是說 HashMap中實際存了多少個鍵值對。

transient int size;

最大容量

table 的長度也是有限制的，不能無限大，HashMap規定最大長度為 2 的30次方。

static final int MAXIMUM_CAPACITY = 1 << 30;

負載因子

這是一個係數，它和 threshold 結合起作用，默認是 0.75。一般情況下不要改。

final float loadFactor;

擴容閾值

閾值 = 容量 x 負載因子，假設當前 HashMap的容量是 16，負載因子是默認值 0.75，那麼當 size 到達 16 x 0.75= 12 的時候，就會觸發擴容。

初始化 HashMap

使用 HashMap肯定要初始化吧，很多情況下都是用無參構造方法創建。

Map<String,String> map = new HashMap<>();

這種情況下所有屬性都是默認值，比如容量是 16，負載因子是 0.75。

另外推薦的一種初始化方式，就是給定一個默認容量，比如指定默認容量是 32。

Map<String,String> map = new HashMap<>(32);

但是 HashMap 要求初始大小必須是 2 的 n 次方，但是又不能要求每個開發人員指定初始容量的時候都按要求來，比如我們指定初始大小為為 7、18 這種會怎麼樣呢？

沒關係，HashMap中有個方法專門負責將傳過來的參數值轉換為最接近、且大於等於指定參數的 2 的 n 次方的值，比如指定大小為 7 的話，最後實際的容量就是 8 ，如果指定大小為 18的話，那最後實際的容量就是 32 。

public HashMap(int initialCapacity, float loadFactor) {
  if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal initial capacity: " +
                                       initialCapacity);
  if (initialCapacity > MAXIMUM_CAPACITY)
    initialCapacity = MAXIMUM_CAPACITY;
  if (loadFactor <= 0 || Float.isNaN(loadFactor))
    throw new IllegalArgumentException("Illegal load factor: " +
                                       loadFactor);
  this.loadFactor = loadFactor;
  this.threshold = tableSizeFor(initialCapacity);
}

執行這個轉換動作的就是 tableSizeFor方法，經過轉換后，將最終的結果賦值給 threshold變量，也就是初始容量，也就是本篇中所說的桶個數。

static final int tableSizeFor(int cap) {
  int n = cap - 1;
  n |= n >>> 1;
  n |= n >>> 2;
  n |= n >>> 4;
  n |= n >>> 8;
  n |= n >>> 16;
  return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

tableSizeFor這個方法就有意思了，先把初始參數減 1，然後連着做或等於和無符號右移操作，最後算出一個接近的 2 的冪次方，下圖演示了初始參數為 18 時的一系列操作，最後得出的初始大小為 32。

這個算法很有意思了，比如你給的初始大小是 63，那得到的結果就是 64，如果初始大小給定 65 ，那得到的結果就是 128，總是能得出不小於給定初始大小，並且最接近的2的n次方的最終值。

從 put 方法解密核心原理

put方法是增加鍵值對最常用的方法，也是最複雜的過程，增加鍵值對的過程涉及了 HashMap最核心的原理，主要包括以下幾點：

1. 什麼情況下會擴容，擴容的規則是什麼？
2. 插入鍵值對的時候如何確定索引，HashMap可不是按順序插入的，那樣不就真成了數組了嗎。
3. 如何確保 key 的唯一性？
4. 發生哈希碰撞怎麼處理？
5. 拉鏈法是什麼？
6. 單桶內的鏈表如何轉變成紅黑樹？

以下是 put 方法的源碼，我在其中做了註釋。

public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
  HashMap.Node<K,V>[] tab; // 聲明 Node 數組 tab
  HashMap.Node<K,V> p;    // 聲明一個 Node 變量 p
  int n, i;
  /**
  * table 定義 transient Node<K,V>[] table; 用來存儲 Node 節點
  * 如果 當前table為空，則調用resize() 方法分配數組空間
  */
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  // n 總是為 2 的冪次方，(n-1) & hash 可確定 tab.length （也就是table數組長度）內的索引
  // 然後 創建一個 Node 節點賦給當前索引
  if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);
  else {
    //如果當前索引位置已經有值了，怎麼辦
    // 拉鏈法出場
    HashMap.Node<K,V> e;
    K k;
    // 判斷 key 值唯一性
    // p 是當前待插入索引處的值
    // 哈希值一致並且（當前位置的 key == 待插入的key(注意 == 符號)，或者key 不為null 並且 key.equals(k)）
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k)))) //如果當前節點只有一個元素，且和待插入key一樣 則覆蓋
      // 將 p（當前索引）節點臨時賦予 e
      e = p;
    else if (p instanceof HashMap.TreeNode) // 如果當前索引節點是一顆樹節點
      //插入節點樹中 並返回
      e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
      // 當前索引節點即不是只有一個節點，也不是一顆樹，說明是一個鏈表
      for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) { //找到沒有 next 的節點，也就是最後一個
          // 創建一個 node 賦給 p.next
          p.next = newNode(hash, key, value, null);
          // 如果當前位置+1之後大於 TREEIFY_THRESHOLD 則要進行樹化
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            //執行樹化操作
            treeifyBin(tab, hash);
          break;
        }
        //如果又發生key衝突則停止 後續這個節點會被相同的key覆蓋
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        p = e;
      }
    }
    if (e != null) { // existing mapping for key
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
        e.value = value;
      afterNodeAccess(e);
      return oldValue;
    }
  }
  ++modCount;
  // 當實際長度大於 threshold 時 resize
  if (++size > threshold)
    resize();
  afterNodeInsertion(evict);
  return null;
}

首次初始化數組和擴容

在執行 put方法時，第一步要檢查 table 數組是否為空或者長度是否為 0，如果是這樣的，說明這是首次插入鍵值對，需要執行 table 數組初始化操作。

另外，隨之鍵值對添加的越來越多，HashMap的 size 越來越大，注意 size 前面說了，是實際的鍵值對數量，那麼 size 到了多少就要擴容了呢，並不是等 size 和 threshold（容量）一樣大了才擴容，而是到了閾值就開始擴容，閾值上面也說了，是容量 x 負載因子。

為什麼放在一起說呢，因為首次初始化和擴容都是用的同一個方法，叫做 resize()。以下是我註釋的 resize()方法。

final HashMap.Node<K,V>[] resize() {
  // 保存 table 副本，接下來 copy 到新數組用
  HashMap.Node<K,V>[] oldTab = table;
  // 當前 table 的容量，是 length 而不是 size
  int oldCap = (oldTab == null) ? 0 : oldTab.length;
  // 當前桶大小
  int oldThr = threshold;

  int newCap, newThr = 0;
  if (oldCap > 0) { //如果當前容量大於 0，也就是非第一次初始化的情況（擴容場景下）
    if (oldCap >= MAXIMUM_CAPACITY) { //不能超過最大允許容量
      threshold = Integer.MAX_VALUE;
      return oldTab;
    }
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY) // 雙倍擴容
      newThr = oldThr << 1; // double threshold
  }
  else if (oldThr > 0) // 初始化的場景（給定默認容量），比如 new HashMap(32)
    newCap = oldThr; //將容量設置為 threshold 的值
  else {               // 無參數初始化場景，new HashMap()
    // 容量設置為 DEFAULT_INITIAL_CAPACITY
    newCap = DEFAULT_INITIAL_CAPACITY;
    // 閾值 超過閾值會觸發擴容
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  if (newThr == 0) { //給定默認容量的初始化情況
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
              (int)ft : Integer.MAX_VALUE);
  }
  // 保存新的閾值
  threshold = newThr;
  // 創建新的擴容后數組，然後將舊的元素複製過去
  @SuppressWarnings({"rawtypes","unchecked"})
  HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
  table = newTab;
  if (oldTab != null) {
    for (int j = 0; j < oldCap; ++j) {
      HashMap.Node<K,V> e;
      //遍歷 獲得得到元素 賦給 e
      if ((e = oldTab[j]) != null) { //如果當前桶不為空
        oldTab[j] = null; // 置空回收
        if (e.next == null) //節點 next為空的話 重新尋找落點 
          newTab[e.hash & (newCap - 1)] = e;
        else if (e instanceof HashMap.TreeNode) //如果是樹節點
          //紅黑樹節點單獨處理
          ((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        else { // 保持原順序
          HashMap.Node<K,V> loHead = null, loTail = null;
          HashMap.Node<K,V> hiHead = null, hiTail = null;
          HashMap.Node<K,V> next;
          do {
            next = e.next;
            if ((e.hash & oldCap) == 0) {
              if (loTail == null)
                loHead = e;
              else
                loTail.next = e;
              loTail = e;
            }
            else {
              if (hiTail == null)
                hiHead = e;
              else
                hiTail.next = e;
              hiTail = e;
            }
          } while ((e = next) != null);
          if (loTail != null) {
            loTail.next = null;
            newTab[j] = loHead;
          }
          if (hiTail != null) {
            hiTail.next = null;
            newTab[j + oldCap] = hiHead;
          }
        }
      }
    }
  }
  return newTab;
}

首次初始化

put方法中線先檢查 table 數組是否為空，如果為空就初始化。

if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

首次初始化分為無參初始化和有參初始化兩種情況，前面在講 HashMap初始化的時候說了，無參情況默認就是 16，也就是 table 的長度為 16。有參初始化的時候，首先使用 tableSizeFor()方法確定實際容量，最後 new 一個 Node 數組出來。

HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];

其中 newCap就是容量，默認16或者自定義的。

而這個過程中還有很重要的一步，就是維護擴容閾值。

擴容

put方法中，判斷當 size（實際鍵值對個數）到達 threshold （閾值）時，觸發擴容操作。

// 當實際長度大於 threshold 時 resize
if (++size > threshold)
    resize();

HashMap遵循兩倍擴容規則，每次擴容之後的大小是擴容前的兩倍。另外，說到底，底層的存儲還是一個數組，Java 中沒有真正的動態數組這一說，數組初始化的時候是多大，那它就一直是這麼大，那擴容是怎麼來的呢，答案就是創建一個新數組，然後將老數組的數據拷貝過去。

拷貝的時候可能會有如下幾種情況：

1. 如果節點 next 屬性為空，說明這是一個最正常的節點，不是桶內鏈表，也不是紅黑樹，這樣的節點會重新計算索引位置，然後插入。
2. 如果是一顆紅黑樹，則使用 split方法處理，原理就是將紅黑樹拆分成兩個 TreeNode 鏈表，然後判斷每個鏈表的長度是否小於等於 6，如果是就將 TreeNode 轉換成桶內鏈表，否則再轉換成紅黑樹。
3. 如果是桶內鏈表，則將鏈表拷貝到新數組，保證鏈表的順序不變。

確定插入點

當我們調用 put方法時，第一步是對 key 進行 hash 計算，計算這個值是為了之後尋找落點，也就是究竟要插入到 table 數組的哪個桶中。

hash 算法是這樣的，拿到 key 的 hashCode，將 hashCode 做一次16位右位移，然後將右移的結果和 hashCode 做異或運算，這段代碼叫做「擾動函數」，之所以不直接拿 hashCode 是為了增加隨機性，減少哈希碰撞次數。

/**
* 用來計算 key 的 hash 值
**/
static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

拿到這個 hash 值之後，會進行這樣的運算 i = (n - 1) & hash，其中 i就是最終計算出來的索引位置。

有兩個場景用到了這個索引計算公式，第一個場景就是 put方法插入鍵值對的時候。第二個場景是在 resize 擴容的時候，new 出來新數組之後，將已經存在的節點移動到新數組的時候，如果節點不是鏈表，也不是紅黑樹，而是一個普通的 Node 節點，會重新計算，找到在新數組中的索引位置。

接着看圖，還是圖說的清楚。

HashMap 要求容量必須是 2 的 n 次方，2的 n 次方的二進製表示大家肯定都很清楚，2的6次方，就是從右向左 6 個 0，然後第 7 位是 1，下圖展示了 2 的 6 次方的二進製表示。

然後這個 n-1的操作就厲害了，減一之後，後面之前二進製表示中 1 後面的 0 全都變成了 1，1 所在的位變為 0。比如 64-1 變為 63，其二進製表示是下面這樣的。

下圖中，前面 4 行分別列出了當 map 的容量為 8、16、32、64的時候，假設容量為 n，則對應的 n-1 的二進製表示是下面這樣的，尾部一片紅，都是 1 ，能預感到將要有什麼騷操作。

沒錯，將這樣的二進製表示代入這個公式 (n - 1) & hash中，最終就能確定待插入的索引位了。接着看圖最下面的三行，演示了假設當前 HashMap的容量為 64 ，而待插入的一個 key 經過 hash 計算后得到的結果是 99 時，代入公式計算 index 的值，也就是 （64-1）& 99，最終的計算結果是 35，也就是這個 key 會落到 table[35] 這個位置。

為什麼 HashMap一定要保證容量是 2 的冪次方呢，通過二進製表示可以看出，如果有多位是 1 ，那與 hash 值進行與運算的時候，更能保證最後散列的結果均勻，這樣很大程度上由 hash 的值來決定。

如何確保 key 的唯一性

HashMap中不允許存在相同的 key 的，那怎麼保證 key 的唯一性呢，判斷的代碼如下。

if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))

首先通過 hash 算法算出的值必須相等，算出的結果是 int，所以可以用 == 符號判斷。只是這個條件可不行，要知道哈希碰撞是什麼意思，有可能兩個不一樣的 key 最後產生的 hash 值是相同的。

並且待插入的 key == 當前索引已存在的 key，或者 待插入的 key.equals(當前索引已存在的key)，注意== 和 equals 是或的關係。== 符號意味着這是同一個對象， equals 用來確定兩個對象內容相同。

如果 key 是基本數據類型，比如 int，那相同的值肯定是相等的，並且產生的 hashCode 也是一致的。

String 類型算是最常用的 key 類型了，我們都知道相同的字符串產生的 hashCode 也是一樣的，並且字符串可以用 equals 判斷相等。

但是如果用引用類型當做 key 呢，比如我定義了一個 MoonKey 作為 key 值類型

public class MoonKey {

    private String keyTile;

    public String getKeyTile() {
        return keyTile;
    }

    public void setKeyTile(String keyTile) {
        this.keyTile = keyTile;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        MoonKey moonKey = (MoonKey) o;
        return Objects.equals(keyTile, moonKey.keyTile);
    }
}

然後用下面的代碼進行兩次添加，你說 size 的長度是 1 還是 2 呢？

Map<MoonKey, String> m = new HashMap<>();
MoonKey moonKey = new MoonKey();
moonKey.setKeyTile("1");
MoonKey moonKey1 = new MoonKey();
moonKey1.setKeyTile("1");
m.put(moonKey, "1");
m.put(moonKey1, "2");
System.out.println(hash(moonKey));
System.out.println(hash(moonKey1));
System.out.println(m.size());

答案是 2 ，為什麼呢，因為 MoonKey 沒有重寫 hashCode 方法，導致 moonkey 和 moonKey1 的 hash 值不可能一樣，當不重寫 hashCode 方法時，默認繼承自 Object的 hashCode 方法，而每個 Object對象的 hash 值都是獨一無二的。

划重點，正確的做法應該是加上 hashCode的重寫。

@Override
public int hashCode() {
  return Objects.hash(keyTile);
}

這也是為什麼要求重寫 equals 方法的同時，也必須重寫 hashCode方法的原因之一。 如果兩個對象通過調用equals方法是相等的，那麼這兩個對象調用hashCode方法必須返回相同的整數。有了這個基礎才能保證 HashMap或者HashSet的 key 唯一。

發生哈希碰撞怎麼辦

前面剛說了相等的對象產生的 hashCode 也要相等，但是不相等的對象使用 hash方法計算之後也有可能產生相同的值，這就叫做哈希碰撞。雖然通過算法已經很大程度上避免碰撞的發生，但是卻無法避免。

產生碰撞之後，自然得出的在 table 數組的索引（也就是桶）也是一樣的，這時，怎麼辦呢，一個桶里怎麼放多個鍵值對？

拉鏈法

文章剛開頭就提到了，HashMap可不是簡單的數組而已。當碰撞發生就坦然接收。有一種方法叫做拉鏈法，不是衣服上那種拉鏈。而是，當碰撞發生了，就在當前桶上拉一條鏈表出來，這樣解釋就合理了。

前面介紹關鍵概念的時候提到了 Node類型，裏面有個屬性叫做 next，它就是為了這種鏈表設計的，如下圖所示。node1、node2、node3都落在了同一個桶中，這時候就得用鏈表的方式處理了，node1.next = node2，node2.next = node3，這樣將鏈表串起來。而 node3.next = null，則說明這是鏈表的尾巴。

當有新元素準備插入到鏈表的時候，採用的是尾插法，而不是頭插法了，JDK 1.7 的版本採用的是頭插法，但是頭插法有個問題，就是在兩個線程執行 resize() 擴容的時候，很可能造成環形鏈表，導致 get 方法出現死循環。

鏈錶轉換成樹

鏈表不是碰撞處理的終極結構，終極結構是紅黑樹，當鏈表長度到達 8 之後，再有新元素進來，那就要開始由鏈表到紅黑樹的轉換了。方法 treeifyBin是完成這個過程的。

使用紅黑樹是出於性能方面的考慮，紅黑樹的查找速度要優於鏈表。那為什麼不是一開始就直接生成紅黑樹，而是鏈表長度大於 8 之後才升級成樹呢？

首先來說，哈希碰撞的概率還是很小的，大部分情況下都是一個桶裝一個 Node，即便發生碰撞，都碰撞到一個桶的概率那就更是少之又少了，所以鏈表長度很少有機會能到 8 ，如果鏈表長度到 8 了，那說明當前 HashMap中的元素數量已經非常大了，那這時候用紅黑樹來提高性能是可取的。而反過來，如果 HashMap總的元素很少，即便用紅黑樹對性能的提升也不大，況且紅黑樹對空間的使用要比鏈表大很多。

get 方法

T value = map.get(key);

例如通過上面的語句通過 key 獲取 value 值，是我們最常用到的方法了。

看圖理解，當調用 get方法后，第一步還是要確定索引位置，也就是我們所說的桶的位置，方法和 put方法時一樣，都是先使用 hash這個 擾動函數 確定 hash 值，然後用 (n-1) & hash獲取索引。這不廢話嗎，當然得和 put的時候一樣了，不一樣還怎麼找到正確的位置。

確定桶的位置后，會出現三種情況：

單節點類型： 也就是這個桶內只有一個鍵值對，這也在 HashMap中存在最多的類型，只要不發生哈希碰撞都是這種類型。其實 HashMap最理想的情況就是這樣，全都是這種類型就完美了。

鏈表類型： 如果發現 get 的 key 所在的是一個鏈表結構，就需要遍歷鏈表，知道找到 key 相等的 Node。

紅黑樹類型： 當鏈表長度超過 8 就轉變成紅黑樹，如果發現找到的桶是一顆紅黑樹，就使用紅黑樹專有的快速查找法查找。

另外，Map.containsKey方法其實用的就是 get方法。

remove 方法

remove與put、get方法類似，都是先求出 key 的 hash 值，然後 (n-1) & hash獲取索引位置，之後根據節點的類型採取不同的措施。

單節點類型： 直接將當前桶元素替換為被刪除 node.next ，其實就是 null。

鏈表類型： 如果是鏈表類型，就將被刪除 node 的前一個節點的 next 屬性設置為 node.next。

紅黑樹類型： 如果是一棵紅黑樹，就調用紅黑樹節點刪除法，這裏，如果節點數在 2~6之間，就將樹結構簡化為鏈表結構。

非線程安全

HashMap沒有做併發控制，如果想在多線程高併發環境下使用，請用 ConcurrentHashMap。同一時刻如果有多個線程同時執行 put 操作，如果計算出來的索引（桶）位置是相同的，那會造成前一個 key 被后一個 key 覆蓋。

比如下圖線程 A 和 線程 B 同時執行 put 操作，很巧的是計算出的索引都是 2，而此時，線程A 和 線程B都判斷出索引為 2 的桶是空的，然後就是插入值了，線程A先 put 進去了 key1 = 1的鍵值對，但是，緊接着線程B 又 put 進去了 key2 = 2，線程A 表示痛哭流涕，白忙活一場。最後索引為2的桶內的值是 key2=2，也就是線程A的存進去的值被覆蓋了。

總結

前面沒說，HashMap搞的這麼複雜不是白搞的，它的最大優點就是快，尤其是 get數據，是 O(1)級別的，直接定位索引位置。

HashMap不是單純的數組結構，當發生哈希碰撞時，會採用拉鏈法生成鏈表，當鏈表大於 8 的時候會轉換成紅黑樹，紅黑樹可以很大程度上提高性能。

HashMap容量必須是 2 的 n 次方，這樣設計是為了保證尋找索引的散列計算更加均勻，計算索引的公式為 (n - 1) & hash。

HashMap在鍵值對數量達到擴容閾值「容量 x 負載因子」的時候進行擴容，每次擴容為之前的兩倍。擴容的過程中會對單節點類型元素進行重新計算索引位置，如果是紅黑樹節點則使用 split方法重新考量，是否將紅黑樹變為鏈表。

壯士且慢，先給點個贊吧，總是被白嫖，身體吃不消！

我是風箏，公眾號「古時的風箏」。一個兼具深度與廣度的程序員鼓勵師，一個本打算寫詩卻寫起了代碼的田園碼農！你可選擇現在就關注我，或者看看歷史文章再關注也不遲。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※超省錢租車方案

※別再煩惱如何寫文案,掌握八大原則!

※回頭車貨運收費標準

※教你寫出一流的銷售文案?

※FB行銷專家,教你從零開始的技巧