本文分析的是源碼,，所以至少讀者要熟悉他們的接口使用，同時(shí),，對(duì)于并發(fā),，讀者至少要知道 CAS、ReentrantLock,、UNSAFE操作這幾個(gè)基本知識(shí),，文中不會(huì)對(duì)這些知識(shí)進(jìn)行介紹。Java8 用到了紅黑樹(shù),，不過(guò)本文不會(huì)進(jìn)行展開(kāi),，感興趣的讀者請(qǐng)自行查找相關(guān)資料。

Hash表，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu),。也就是說(shuō),，它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問(wèn)記錄，以加快查找的速度,。存放記錄的數(shù)組叫做哈希表,。

在HashMap中，就是將所給的“鍵”通過(guò)哈希函數(shù)得到“索引”,，然后把內(nèi)容存在數(shù)組中,，這樣就形成了“鍵”和內(nèi)容的映射關(guān)系。

哈希表

上圖可以發(fā)現(xiàn),，“鍵”轉(zhuǎn)換為“索引”的過(guò)程就是哈希函數(shù),，為了盡可能保證每一個(gè)“鍵”通過(guò)哈希函數(shù)的轉(zhuǎn)換對(duì)應(yīng)不同的“索引”，就需要對(duì)哈希函數(shù)進(jìn)行選擇了,，使其得到的“索引”分布越均勻越好,。

哈希函數(shù)的均勻性：

哈希函數(shù)設(shè)計(jì)

通過(guò)前輩的研究加上實(shí)踐表明，當(dāng)把哈希函數(shù)得到hashcode值對(duì)素?cái)?shù)取模時(shí),，這樣得到的索引是最為均勻的,。但是，在HashMap源碼中,，并不是取模素?cái)?shù)的,，而是一種等效取模2的n次方的位運(yùn)算，hash&(length-1),。hash%length==hash&(length-1)的前提是length是2的n次方,；之所以使用位運(yùn)算替代取模,，是因?yàn)槲贿\(yùn)算的效率更高，所以也就要求數(shù)組的長(zhǎng)度必須是2的n次方（索引的分布也是很均勻的）,。

哈希函數(shù)的一致性：

哈希函數(shù)設(shè)計(jì)原則

哈希函數(shù)的一致性原則是：當(dāng)兩個(gè)對(duì)象的equals相等,，那么他們的hashcode一定相等。

這就要求我們?cè)谥貙?xiě)了equals方法時(shí),，必須重寫(xiě)hashcode方法,。如果不重寫(xiě)hashcode，則會(huì)使用Object的hashcode方法,，該方法是以我們創(chuàng)建的對(duì)象的地址作為參數(shù)求hash的,。所以，如果不重寫(xiě)hashcode,，兩個(gè)equals相等的對(duì)象會(huì)導(dǎo)致hashcode不同（因?yàn)椴煌膶?duì)象）,，這個(gè)是不允許的，因?yàn)檫`背了hash函數(shù)的一致性原則,。

哈希沖突：

當(dāng)兩個(gè)不同的元素,，通過(guò)哈希函數(shù)得到了同一個(gè)hashcode，則會(huì)產(chǎn)生哈希沖突,。HashMap的處理方式是,，JDK8之前，每一個(gè)位置對(duì)應(yīng)一個(gè)鏈表,，鏈?zhǔn)降拇娣殴_突的元素；JDK8開(kāi)始,，當(dāng)哈希沖突達(dá)到一定程度（8個(gè)）,，每一個(gè)位置從鏈表轉(zhuǎn)換成紅黑樹(shù)。因?yàn)榧t黑樹(shù)的時(shí)間復(fù)雜度是O(log n)的,，效率優(yōu)于鏈表,。

鏈地址法

哈希表小結(jié)：

哈希表，均攤復(fù)雜度是O(1),，因?yàn)榈谝徊酵ㄟ^(guò)數(shù)組索引找到數(shù)組位置是O(1),，然后到鏈表中查找元素的均攤復(fù)雜度是O(size/length)，size為元素個(gè)數(shù),，length為數(shù)組長(zhǎng)度,。由于Hash表的容量是動(dòng)態(tài)擴(kuò)容的，也就是說(shuō)隨著size和length成正比的,，即size/length是一個(gè)常數(shù),，于是也是O(1)的復(fù)雜度，即總的來(lái)說(shuō),，均攤復(fù)雜度是O(1),。但是哈希表是沒(méi)有順序性的，即無(wú)法對(duì)元素進(jìn)行排序。

哈希表的缺點(diǎn)

首先,，我們用下面的這張圖來(lái)介紹下HashMap的結(jié)構(gòu)。

Java7 HashMap結(jié)構(gòu)圖

大方向上,，HashMap里面是一個(gè)數(shù)組,，然后每個(gè)數(shù)組中的每個(gè)元素是一個(gè)單向鏈表。

上圖中,，每個(gè)綠色的實(shí)體是嵌套類(lèi)Entry的實(shí)例,，Entry包含四個(gè)屬性：key,value,hash值和用于單向鏈表的next。

capacity：當(dāng)前數(shù)組容量,，始終保持2^n,，可以擴(kuò)容，擴(kuò)容后的大小為當(dāng)前的2倍,，默認(rèn)為16,。

loadFactor：負(fù)載因子，默認(rèn)為 0.75,。

threshold：擴(kuò)容的閾值,，等于 capatity * loadFactor。

put 過(guò)程分析

put 源碼

1,、數(shù)組初始化：在第一個(gè)元素插入 HashMap 的時(shí)候做一次數(shù)組的初始化,，就是先確定初始的數(shù)組大小，并計(jì)算數(shù)組的擴(kuò)容閾值,。這里將數(shù)組保持在 2 的 n 次方的做法,，java7 和 java8 的HashMap 和 ConcurrentHashMap 都有相應(yīng)的要求。

注意：new HashMap時(shí),，并未做數(shù)組初始化操作,，而是簡(jiǎn)單為loadFactor ，threshold賦值,；同時(shí)為了保證將數(shù)組保持在 2 的 n 次方,，會(huì)對(duì) capacity的值進(jìn)行處理，取大于capacity且最近的2 的 n 次方值作為數(shù)組大小,。

2,、計(jì)算具體數(shù)組的下標(biāo)：使用 key的 hash值對(duì)數(shù)組長(zhǎng)度進(jìn)行取模（源碼中是 hash & (length -1)，當(dāng)length是2^n 時(shí),，此時(shí)（length - 1） 的二進(jìn)制全是1,， hash & (length -1) 相當(dāng)于取 hash值的低 n位,， 結(jié)果和 hash mod length一樣的）。

3,、找到數(shù)組下標(biāo)后,，先進(jìn)行 key 判重（== || equals），如果沒(méi)有重復(fù),，則將新值放入鏈表的表頭,，如果有重復(fù)，直接用新值覆蓋舊值,。

4,、數(shù)組擴(kuò)容：如果當(dāng)前size >= threshold，那么就會(huì)觸發(fā)擴(kuò)容,；擴(kuò)容就是用一個(gè)新的大數(shù)組替換原來(lái)的小數(shù)組,，并將原來(lái)數(shù)組中的值遷移到新的數(shù)組中。

既然對(duì) key的判重依據(jù)是hash值和equals方法,，故必須對(duì)key進(jìn)行重寫(xiě)hashcode和equals方法,，因?yàn)槿绻恢貙?xiě)，將直接用Object的hashcode和equals方法,，而其必須是同一個(gè)對(duì)象才能滿足key相同,。

hashcode方法的一般規(guī)定：如果兩個(gè)對(duì)象能夠equals相等，那么他們的hashcode必須相等,。

所以,，重寫(xiě)了equals必須重寫(xiě)hashcode。

get 過(guò)程分析

java7 HashMap get源碼

相對(duì)于put 過(guò)程,，get 過(guò)程是非常簡(jiǎn)單的,。

1、根據(jù)key 計(jì)算 hash 值,。

2、找到相應(yīng)的數(shù)組下標(biāo)：hash & (length - 1),。

3,、遍歷該數(shù)組位置處的鏈表，直到找到相等（== || equals）的 key,。

整個(gè)ConcurrentHashMap 由一個(gè)個(gè) Segment 組成,，Segment 代表“部分” 或 “一段”的意思，所以很多地方都會(huì)將其描述為分段鎖,。

簡(jiǎn)單的理解,，ConcurrentHashMap 是一個(gè) Segment數(shù)組,，Segment 通過(guò)繼承 ReentrantLock來(lái)進(jìn)行加鎖，所以每次需要加鎖的操作鎖住的是一個(gè) Segment,，這樣只要保證每個(gè) Segment是線程安全的,，也就實(shí)現(xiàn)了全局的線程安全性。

Java7 ConcurrentHashMap 結(jié)構(gòu)

concurrencyLevel：并行級(jí)別,、并發(fā)數(shù),、Segment 數(shù)。默認(rèn)是16,，也就是說(shuō) ConcurrentHashMap 有16個(gè) Segment,，所以理論上，最多同時(shí)支持16個(gè)線程并發(fā)寫(xiě),。這個(gè)值可以在初始化的時(shí)候設(shè)置為其他值,，但是一旦初始化以后，它就不可以擴(kuò)容了,。

再具體到每個(gè) Segment內(nèi)部,，其實(shí)每個(gè) Segment 很像之前介紹的 HashMap，不過(guò)它要保證線程安全,，所以處理起來(lái)要麻煩些,。

初始化

initialCapacity：初始容量，這個(gè)值指的是整個(gè) ConcurrentHashMap的初始容量,，實(shí)際操作的時(shí)候需要平均分給每個(gè) Segment,。

loadFactor：負(fù)載因子，之前我們說(shuō)了,，Segment 數(shù)組不可以擴(kuò)容,，所以這個(gè)負(fù)載因子是給每個(gè) Segment 內(nèi)部使用的。

new ConcurrentHashMap()無(wú)參進(jìn)行初始化以后：

1,、Segment 數(shù)組長(zhǎng)度為16,，不可以擴(kuò)容。

2,、Sement[i]的默認(rèn)大小為2,，負(fù)載因子為0.75，得出初始閾值為1.5,，也就插入第一個(gè)元素不會(huì)觸發(fā)擴(kuò)容,，插入第二個(gè)進(jìn)行一次擴(kuò)容。

3,、初始化了 Segment[0],，其他位置還是null。

put 過(guò)程分析

第一層皮很簡(jiǎn)單,，根據(jù) hash值找到 Segment,，之后就是 Segment 內(nèi)部的 put 操作了,。

Segment 內(nèi)部是由 數(shù)組+鏈表 組成的。

put 源碼

初始化 Segment：ensureSement

ConcurrentHashMap 初始化的時(shí)候初始化了第一個(gè)分段 Segment[0],，對(duì)于其他分段來(lái)說(shuō),，在插入第一個(gè)值的時(shí)候進(jìn)行初始化。并且初始化其他的 Segment[k]時(shí),，需要當(dāng)前 Segment[0]處的數(shù)組長(zhǎng)度和負(fù)載因子,，故 Segment[0]需要在ConcurrentHashMap初始化的時(shí)候進(jìn)行初始化。

擴(kuò)容：rehash

重復(fù)一下,，Segment 數(shù)組不能擴(kuò)容,，擴(kuò)容的是 單個(gè)Segment內(nèi)部數(shù)組 HashEntry[]，擴(kuò)容后,，容量為原來(lái)的2倍,。

觸發(fā)擴(kuò)容的時(shí)機(jī)：put 的時(shí)候，如果判斷該值的插入會(huì)導(dǎo)致該 Segment內(nèi)部的元素個(gè)數(shù)超過(guò)閾值,，那么先進(jìn)行擴(kuò)容,，再插值。該方法不需要考慮并發(fā),，因?yàn)?put 操作,，是持有獨(dú)占鎖的。

get 過(guò)程分析

相對(duì)于 put 來(lái)說(shuō),，get 真的不要太簡(jiǎn)單,。

get 源碼

1、計(jì)算 hash值,，找到 Segment數(shù)組中的下標(biāo),。

2、再次根據(jù) hash 找到每個(gè) Segment內(nèi)部的 HashEntry[]數(shù)組的下標(biāo),。

3,、遍歷該數(shù)組位置處的鏈表，直到找到相等（== || equals）的 key,。

get 是不需要加鎖的：原因是get方法是將共享變量（table）定義為volatile,，讓被修飾的變量對(duì)多個(gè)線程可見(jiàn)(即其中一個(gè)線程對(duì)變量進(jìn)行了修改，會(huì)同步到主內(nèi)存,，其他線程也能獲取到最新值),，允許一寫(xiě)多讀的操作,。

根據(jù) Java7 HashMap 的介紹,，我們知道,，查找的時(shí)候，根據(jù) hash 值我們能夠快速定位到數(shù)組的具體下標(biāo),，但是之后的話,，需要順著鏈表一個(gè)個(gè)比較下去才能找到我們需要的，時(shí)間復(fù)雜度取決于鏈表的長(zhǎng)度,，為O(N),。

為了降低這部分的開(kāi)銷(xiāo)，在Java8 中,，當(dāng)鏈表中的元素超過(guò)8個(gè)以后,，會(huì)將鏈表轉(zhuǎn)換為紅黑樹(shù)，在這些位置進(jìn)行查找的時(shí)候可以降低時(shí)間復(fù)雜度為O(logN),。

Java8 HashMap 結(jié)構(gòu)

Java7 中使用 Entry來(lái)代表每個(gè) HashMap 中的數(shù)據(jù)節(jié)點(diǎn),，Java8 中使用 Node，基本沒(méi)有區(qū)別,，都是 key,，value，hash和 next 這四個(gè)屬性,，不過(guò),， Node 只能用于鏈表的情況，紅黑樹(shù)需要使用 TreeNode,。

put 過(guò)程分析

put 源碼

和Java7 稍微有點(diǎn)不一樣的是,，Java7 是先擴(kuò)容后插入新值的，Java8 先插入值再擴(kuò)容的,；Java7 （HashMap/ConcurrentHashMap） 是將數(shù)據(jù)插入到鏈表的表頭,，而 Java8 是將數(shù)據(jù)插入到鏈表的最后面。

get 過(guò)程分析

get 源碼

1,、計(jì)算 key 的 hash 值,，根據(jù) hash 值找到對(duì)應(yīng)數(shù)組下標(biāo)：hash & (length - 1)。

2,、判斷數(shù)組該位置第一個(gè)節(jié)點(diǎn)是否剛好是我們要找的（判key）,，如果不是，走第三步,。

3,、判斷該元素類(lèi)型是否是 TreeNode，如果是,，用紅黑樹(shù)的方法取數(shù)據(jù),，如果不是，走第四步,。

4,、遍歷鏈表,，直到找到相等（== || equals）的 key。

Java8 ConcurrentHashMap 結(jié)構(gòu)

結(jié)構(gòu)上和 Java8 的 HashMap 基本上一樣，不過(guò)它要保證安全性,，所以源碼上確實(shí)要復(fù)雜一些,。

初始化

初始化

這個(gè)初始化方法，通過(guò)提供初始容量,，計(jì)算 sizeCtl,，sizeCtl = [(1.5 * initialCapacity + 1，然后向上取最近的2的 n 次方)],。

put 過(guò)程分析

1,、獲取 key 的 hash值，找到數(shù)組下標(biāo),。

2,、如果數(shù)組為空，進(jìn)行數(shù)組初始化,。

3,、判斷該數(shù)組第一個(gè)節(jié)點(diǎn)是否有數(shù)據(jù)，如果沒(méi)有數(shù)據(jù),，則使用CAS操作將這個(gè)新值插入,，如果有數(shù)據(jù)，則進(jìn)入第四步,。

4,、對(duì)頭結(jié)點(diǎn)進(jìn)行加鎖(synchronized)，如果頭結(jié)點(diǎn)的 hash 值>=0,，說(shuō)明是鏈表,，遍歷鏈表，如果找到相等的key,，則進(jìn)行覆蓋,，如果沒(méi)有找到相等的key，則將新值放到鏈表的最后面,；如果 hash 值 <>

5,、插值完成之后，判斷鏈表元素是否達(dá)到臨界值（8）,，那么就會(huì)進(jìn)行紅黑樹(shù)轉(zhuǎn)換,。注意：當(dāng)數(shù)組長(zhǎng)度小于64時(shí)，即使達(dá)到臨界值也不會(huì)進(jìn)行紅黑樹(shù)轉(zhuǎn)換，而是進(jìn)行數(shù)組擴(kuò)容（Java8 HashMap沒(méi)有此限制,，直接判斷臨界值即可）。

初始化數(shù)組：initTable

初始化方法中的并發(fā)問(wèn)題是通過(guò)對(duì) sizeCtl 進(jìn)行一個(gè)CAS 操作來(lái)控制的,。

initTable

get 過(guò)程分析

get 源碼

1,、計(jì)算 hash值

2、根據(jù) hash 值找到數(shù)組對(duì)應(yīng)的位置：(n - 1) & hash

3.根據(jù)該位置處頭節(jié)點(diǎn)的性質(zhì)進(jìn)行查找：

1）如果該位置為 null,，那么直接返回 null 就可以了
2）如果該位置處的節(jié)點(diǎn)剛好就是我們需要的,，返回該節(jié)點(diǎn)的值即可
3）如果該位置節(jié)點(diǎn)的 hash 值小于 0，說(shuō)明正在擴(kuò)容,，或者是紅黑樹(shù),，后面調(diào)用 find 接口，程序會(huì)根據(jù)上下文執(zhí)行具體的方法,。
4）如果以上 3 條都不滿足,，那就是鏈表，進(jìn)行遍歷比對(duì)即可

LinkedHashMap 是默認(rèn)根據(jù)元素增加的先后順序進(jìn)行排序,，而 TreeMap(底層二叉樹(shù)) 則默認(rèn)根據(jù)元素的 Key 進(jìn)行自然排序(即從小到大),，也可以指定排序的比較器。

HashTable：線程安全的,，但是由于采用的是synchronized來(lái)保證線程安全,，效率非常低，因?yàn)楫?dāng)一個(gè)線程訪問(wèn)HashTable的同步方法時(shí),，其他線程訪問(wèn)會(huì)進(jìn)入阻塞或輪詢的狀態(tài),。

二叉樹(shù)：二叉樹(shù)規(guī)定了在每個(gè)節(jié)點(diǎn)下最多只能擁有兩個(gè)子節(jié)點(diǎn)，一左一右,。

二叉查找樹(shù)：二叉查找樹(shù)的左子樹(shù)中任意節(jié)點(diǎn)的值都小于右子樹(shù)中任意節(jié)點(diǎn)的值,。

平衡二叉樹(shù)：又稱為AVL樹(shù)，它要求左右子樹(shù)的高度差的絕對(duì)值不能大于1,，紅黑樹(shù)就是一種平衡二叉樹(shù),。