一、HashMap構造器
HashMap總共給我們提供了三個構造器來建立HashMap物件。
1。無參建構函式
public HashMap
：使用無參建構函式建立的hashmap物件，其預設容量為16，預設的負載因子為0。75。
2。有參建構函式
public HashMap（int initialCapacity，float loadFactor）
：使用該建構函式，我們可以指定hashmap的初始化容量和負載因子，但是在hashmap底層不一定會初始化成我們傳入的容量，而是會初始化成大於等於傳入值的最小的2的冪次方，比如我們傳入的是17，那麼hashmap會初始化成
32（2^5）
。那麼hashmap是如何高效計算大於等於一個數的最小2的冪次方數的呢，原始碼如下：
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；
}
它的設計可以說很巧妙，其基本思想是如果一個二進位制數低位全是1，那麼這個數+1則肯定是一個2的冪次方數。舉個例子看一下：
可以看到，它的計算過程是：首先將我們指定的那個數cap減1（減1的原因是，如果cap正好是一個2的冪次方數，也可以正確計算），然後對cap-1分別無符號右移1位、2位，4位、8位、16位（加起來正好是31位），並且每次移位後都與上一個數做按位或運算，透過這樣的運算，會使得最終的結果低位都是1。那麼最終對結果加1，就會得到一個2的冪次方數。
3。另一個有參建構函式就是有參建構函式
public HashMap（int initialCapacity）
，該建構函式和上一個建構函式唯一不同之處就是不能指定負載因子。
二、HashMap插入機制
1.插入方法原始碼
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） {
Node
// 初始化桶陣列 table， table 被延遲到插入新資料時再進行初始化
if （（tab = table） == || （n = tab。length） == 0）
n = （tab = resize）。length；
// 如果桶中不包含鍵值對節點引用，說明當前陣列下標下不存在任何資料，則將新鍵值對節點的引用存入桶中即可
if （（p = tab［i = （n - 1） & hash］） == ）
tab［i］ = newNode（hash， key， value， ）；
else {
Node
//如果hash相等，並且equals方法返回true，這說明key相同，此時直接替換value即可，並且返回原值
if （p。hash == hash &&
（（k = p。key） == key || （key ！= && key。equals（k））））
e = p；
//如果第一個節點是樹節點，則呼叫putTreeVal方法，將當前值放入紅黑樹中
else if （p instanceof TreeNode）
e = （（TreeNode
else {
//如果第一個節點不是樹節點，則說明還是連結串列節點，則開始遍歷連結串列，將值儲存到連結串列合適的位置
for （int binCount = 0； ； ++binCount） {
//如果遍歷到了連結末尾，則建立連結串列節點，將資料儲存到連結串列結尾
if （（e = p。next） == ） {
p。next = newNode（hash， key， value， ）；
//判斷連結串列中節點樹是否超多了閾值8，如果超過了則將連結串列轉換為紅黑樹（當然不一定會轉換，treeifyBin方法中還有判斷）
if （binCount >= TREEIFY_THRESHOLD - 1） // -1 for 1st
treeifyBin（tab， hash）；
break；
}
//如果在連結串列中找到，完全相同的key，則直接替換value
if （e。hash == hash &&
（（k = e。key） == key || （key ！= && key。equals（k））））
break；
p = e；
}
}
//e！=說明只是遍歷到中間就break了，該種情況就是在連結串列中找到了完全相等的key，該if塊中就是對value的替換操作
if （e ！= ） { // existing mapping for key
V oldValue = e。value；
if （！onlyIfAbsent || oldValue == ）
e。value = value；
afterNodeAccess（e）；
return oldValue；
}
}
++modCount；
//加入value之後，更新size，如果超過閾值，則進行擴容
if （++size > threshold）
resize；
afterNodeInsertion（evict）；
return ；
}
2.插入流程圖
（1）在put一個k-v時，首先呼叫hash方法來計算key的hashcode，而在hashmap中並不是簡單的呼叫key的hashcode求出一個雜湊碼，還用到了擾動函式來降低雜湊衝突。原始碼如下：
static
final
int
hash
（Object key） {
int h；
return （key == ） ？ 0 ： （h = key。hashCode） ^ （h >>> 16）；
}
從原始碼中可以看到，最終的雜湊值是將原雜湊碼和原雜湊碼右移16位得到的值進行異或運算的結果。16正好是32的一半，因此hashmap是將hashcode的高位移動到了低位，再透過異或運算將高位散播的低位，從而降低雜湊衝突。
至於為什麼能夠降低衝突呢，我們可以看看作者對hash方法的註釋：
Computes key。hashCode and spreads （XORs） higher bits of hash to lower。
Because the table uses power-of-two masking，
sets of hashes that vary only in bits above the current mask will always collide。
（Among known examples are sets of Float keys holding consecutive whole numbers in small tables。）
So we apply a transform that spreads the impact of higher bits downward。 There is a tradeoff between speed，
utility， and quality of bit-spreading。
Because many common sets of hashes are already reasonably distributed （so don’t benefit from spreading），
and because we use trees to handle large sets of collisions in bins，
we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage，
as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds。
從註釋中我們可以得出，作者進行高位向低位散播的原因是：由於hashmap在計算bucket下標時，計算方法為hash&n-1，n是一個2的冪次方數，因此hash&n-1正好取出了hash的低位，比如n是16，那麼hash&n-1取出的是hash的低四位，那麼如果多個hash的低四位正好完全相等，這就導致了always collide（衝突），即使hash不同。因此將高位向低位散播，讓高位也參與到計算中，從而降低衝突，讓資料儲存的更加雜湊。
（2）在計算出hash之後之後，呼叫putVal方法進行key-value的儲存操作。在putVal方法中首先需要判斷table是否被初始化了（因為hashmap是延遲初始化的，並不會在建立物件的時候初始化table），如果table還沒有初始化，則透過resize方法進行擴容。
if （（tab = table） == || （n = tab。length） == 0）
n = （tab = resize）。length；
（3）透過（n-1）&hash計算出當前key所在的bucket下標，如果當前table中當前下標中還沒有儲存資料，則建立一個連結串列節點直接將當前k-v儲存在該下標的位置。
if （（p = tab［i = （n - 1） & hash］） == ）
tab［i］ = newNode（hash， key， value， ）；
（4）如果table下標處已經存在資料，則首先判斷當前key是否和下標處儲存的key完全相等，如果相等則直接替換value，並將原有value返回，否則繼續遍歷連結串列或者儲存到紅黑樹。
if （p。hash == hash &&（（k = p。key） == key || （key ！= && key。equals（k））））
e = p；
（5）當前下標處的節點是樹節點，則直接儲存到紅黑樹中
else if （p instanceof TreeNode）
e = （（TreeNode
（6）如果不是紅黑樹，則遍歷連結串列，如果在遍歷連結串列的過程中，找到相等的key，則替換value，如果沒有相等的key，就將節點儲存到連結串列尾部（jdk8中採用的是尾插法），並檢查當前連結串列中的節點樹是否超過了閾值8，如果超過了8，則透過呼叫treeifyBin方法將連結串列轉化為紅黑樹。
for （int binCount = 0； ； ++binCount） {
if （（e = p。next） == ） {
p。next = newNode（hash， key， value， ）；
if （binCount >= TREEIFY_THRESHOLD - 1） // -1 for 1st
treeifyBin（tab， hash）；
break；
}
if （e。hash == hash &&
（（k = e。key） == key || （key ！= && key。equals（k））））
break；
p = e；
}
（7）將資料儲存完成之後，需要判斷當前hashmap的大小是否超過擴容閾值
Cap*load_fact
，如果大於閾值，則呼叫
resize
方法進行擴容。
f （++size > threshold）
resize；
HashMap在擴容後的容量為原容量的2倍，起基本機制是建立一個2倍容量的table，然後將資料轉存到新的散列表中，並返回新的散列表。和jdk1。7中不同的是，jdk1。8中多轉存進行了最佳化，可以不再需要重新計算bucket下標，其實現原始碼如下：
從原始碼中我們可以看出，如果一個key hash和原容量oldCap按位與運算結果為0，則擴容前的bucket下標和擴容後的bucket下標相等，否則擴容後的bucket下標是原下標加上oldCap。
使用的基本原理總結如下：
1、如果一個數m和一個2的冪次方數n進行按位與運算不等於0，則有：
m&（n2-1）=m&（n-1）+n
理解：一個2的冪次方數n，在二進位制中只有一位為1（假設第k位是1），其他位均為0，那個如果一個數m和n進行按位與運算結果為0的話，則說明m的二進位制第k位肯定為0，那麼m的前n位和前n-1位所表示的值肯定是相等的。
2、如果一個數m和一個2的冪次方數n進行按位與運算等於0，則有：
m&（n2-1）=m&（n-1）
理解：一個2的冪次方數n，在二進位制中只有一位為1（假設第k位是1），其他位均為0，那個如果一個數m和n進行按位與運算結果不為0的話，則說明m的二進位制第k位肯定為1，那麼m的前n位和前n-1位所表示的值的差恰好是第k位上的1所表示的數，二這個數正好是n。另外，
原理圖：
（感謝閱讀，希望對你所有幫助）
-END-
如果看到這裡，說明你喜歡這篇文章，請 轉發
