前言

HashMap的主幹是一個數組，假設我們有3個鍵值對dnf:1，cf:2，lol:3，每次放的時候會根據hash函數來確定這個鍵值對應該放在數組的哪個位置，即index = hash(key)

1 = hash(dnf)，我們將鍵值對放在數組下標為1的位置

3 = hash(cf)

1 = hash(lol)，這時發現數組下標為1的位置已經有值了，我們就可以用鏈表的形式將這個鍵值對放到dnf鍵值對的下面

1.7 HashMap採用的是頭插法，所以lol:3在數組為1的位置，dnf:1以鏈表的形式跟在lol：3的下面

在獲取key為lol的鍵值對時，1=hash(lol)，得到這個鍵值對在數組下標為1的位置，lol和dnf不相等，和下一個元素比較，相等返回

源碼

基於jdk1.7.0_80，1.8和1.7相比 差不多，1.8只是多了一個新特性，當鏈表的長度>=8的時候，鏈表轉換為紅黑樹提高查詢的效率，1.7解讀起來更容易

各種默認參數不再細說，這裡說一下threshold和loadFactor，

threshold = capacity * load factor，即擴容的閥值=容量*負載因子，

比如HashMap的容量為16，負載因子為0.75，則閥值為16*0.75=12，

當HashMap中放入12個元素時（size=12），就會進行擴容

1.負載因子越小，容易擴容，浪費空間，但查找效率高

2.負載因子越大，不易擴容，對空間的利用更加充分，查找效率低（鏈表拉長）

上述中的鍵值對是存放在一個靜態的內部類中，即數組中存放的元素

構造函數只做2件事，初始化數組大小和負載因子，要麼自己指定，有麼用默認值，可能有人會說threshold是擴容閥值不是數組的長度啊，我們一會細說，（代碼省去一部分校驗內容）

put操作

這裡面試一般會問到為什麼HashMap不能存放2個key相等的元素，因為放置key相等的元素時，新值會替換舊值，並且返回舊值

這裡我們分析inflateTable，putForNullKey，addEntry方法，hash方法不進行分析，indexFor方法最後進行分析

傳入的參數是構造函數初始化的threshold，將數組的長度變為>=size，並且是2的倍數的長度，這樣即使初始化數組長度不是2的倍數，也會在第一次放值時變為2的倍數，並且對threshold重新設值

若key為null，則將值放在table[0]這個鏈上，這樣key為null的時候直接從table[0]處取值即可

這裡需要注意一下擴容的時機和擴容的大小，以後會和Hashtable，ConcurrentHashMap進行比較

將新增加的元素放到鏈表的第一位，並且將其他元素跟在第一個元素後面，即頭插法

get方法

從table[0]初獲取key為null的值

key不為null時

HashMap的大小為什麼是2的倍數

h是hashcode，length時數組長度，下面這個方法是根據hashcode求出對象在數組中放置的位置

h & (length - 1) 等價於 h % length，我們假設數組的長度為15和16，hashcide為8和9

可以看出數組長度為15的時候，hash碼為8和9的元素被放到數組中的同一個位置形成鏈表，鍵低了查詢效率，當hahs碼和15-1(1110)進行&時，最後一位永遠是0，這樣0001，0011，0101，1001，1011，0111，1101這些位置永遠不會被放置元素，這樣會導致1.空間浪費大，2.增加了碰撞的機率，減慢查詢的效率。當數組長度為2的n次方時，2的n次方−1的所有位都是1，如8-1=7即111，那麼進行低位&運算時，值總與原來的hash值相同，降低了碰撞的概率

"

前言

HashMap的主幹是一個數組，假設我們有3個鍵值對dnf:1，cf:2，lol:3，每次放的時候會根據hash函數來確定這個鍵值對應該放在數組的哪個位置，即index = hash(key)

1 = hash(dnf)，我們將鍵值對放在數組下標為1的位置

3 = hash(cf)

1 = hash(lol)，這時發現數組下標為1的位置已經有值了，我們就可以用鏈表的形式將這個鍵值對放到dnf鍵值對的下面

1.7 HashMap採用的是頭插法，所以lol:3在數組為1的位置，dnf:1以鏈表的形式跟在lol：3的下面

在獲取key為lol的鍵值對時，1=hash(lol)，得到這個鍵值對在數組下標為1的位置，lol和dnf不相等，和下一個元素比較，相等返回

源碼

基於jdk1.7.0_80，1.8和1.7相比 差不多，1.8只是多了一個新特性，當鏈表的長度>=8的時候，鏈表轉換為紅黑樹提高查詢的效率，1.7解讀起來更容易

各種默認參數不再細說，這裡說一下threshold和loadFactor，

threshold = capacity * load factor，即擴容的閥值=容量*負載因子，

比如HashMap的容量為16，負載因子為0.75，則閥值為16*0.75=12，

當HashMap中放入12個元素時（size=12），就會進行擴容

1.負載因子越小，容易擴容，浪費空間，但查找效率高

2.負載因子越大，不易擴容，對空間的利用更加充分，查找效率低（鏈表拉長）

上述中的鍵值對是存放在一個靜態的內部類中，即數組中存放的元素

構造函數只做2件事，初始化數組大小和負載因子，要麼自己指定，有麼用默認值，可能有人會說threshold是擴容閥值不是數組的長度啊，我們一會細說，（代碼省去一部分校驗內容）

put操作

這裡面試一般會問到為什麼HashMap不能存放2個key相等的元素，因為放置key相等的元素時，新值會替換舊值，並且返回舊值

這裡我們分析inflateTable，putForNullKey，addEntry方法，hash方法不進行分析，indexFor方法最後進行分析

傳入的參數是構造函數初始化的threshold，將數組的長度變為>=size，並且是2的倍數的長度，這樣即使初始化數組長度不是2的倍數，也會在第一次放值時變為2的倍數，並且對threshold重新設值

若key為null，則將值放在table[0]這個鏈上，這樣key為null的時候直接從table[0]處取值即可

這裡需要注意一下擴容的時機和擴容的大小，以後會和Hashtable，ConcurrentHashMap進行比較

將新增加的元素放到鏈表的第一位，並且將其他元素跟在第一個元素後面，即頭插法

get方法

從table[0]初獲取key為null的值

key不為null時

HashMap的大小為什麼是2的倍數

h是hashcode，length時數組長度，下面這個方法是根據hashcode求出對象在數組中放置的位置

h & (length - 1) 等價於 h % length，我們假設數組的長度為15和16，hashcide為8和9

可以看出數組長度為15的時候，hash碼為8和9的元素被放到數組中的同一個位置形成鏈表，鍵低了查詢效率，當hahs碼和15-1(1110)進行&時，最後一位永遠是0，這樣0001，0011，0101，1001，1011，0111，1101這些位置永遠不會被放置元素，這樣會導致1.空間浪費大，2.增加了碰撞的機率，減慢查詢的效率。當數組長度為2的n次方時，2的n次方−1的所有位都是1，如8-1=7即111，那麼進行低位&運算時，值總與原來的hash值相同，降低了碰撞的概率

"