HashMap：源代碼（構造方法、put、resize、get、remove、replace）

1、常量

（1）預設table大小，1左移四位變為8

（2）table最大長度

（3）預設負載因子大小：

（4）樹化門檻值

（5）樹降級成為連結清單門檻值

（6）哈希表的元素達到64且連結清單的長度達到8之後就更新為樹

（7）散清單（哈希表）

（8）目前哈希表元素個數：

（9）目前哈希表修改次數

（10）擴容門檻值：當哈希表的元素超過門檻值的時候，觸發擴容

（11）負載因子

2、構造方法

（1）構造方法：

initialCapacity必須是大于零的，最大值是MAXIMUM_CAPACITY，loadFactor也必須是大于零的，這些代碼就是一些校驗

傳回一個大于或等于目前值cap的一個數字，并且這個數字一定是2的次方數。

cap=10

n=10-1=9（如果不減一的話會變成它的二倍）

1001 | 0100(右移一位) = 1101

1101 | 0011（右移兩位）=1111

1111 | 0000（右移四位）=1111

.... ...

... ...

return 15+1=16（加1後，進一位，後面的幾位都變成零）

3、put方法

（1）是一個套娃的方法：調用putVal方法：

hash方法：hashCode經過擾動之後得到一個哈希值，哈希值與表的長度進行運算得到在哈希表中的位置，這個擾動函數就是hash函數。

擾動函數：讓key的哈希值的高十六位也參與路由運算

（2）hash方法

首先調用hashCode方法擷取鍵的哈希值，然後對其進行高位運算，将h右移16位與原來的h的低16位異或運算

如果key為空，哈希值就為零，不為空的話，就讓h和h右移16位相異或，目的是讓key的哈希值的高十六位也參與運算：

異或之後相當于将h的高十六位與低十六位相與，如果hashtable不是很大的情況下（16），可以讓高十六位參與進來

哈希沖突不可避免，隻能盡量減少哈希沖突 ，如果鍵是自定義類型的話要重寫hash算法，但是一般都用字元串來做鍵

好的雜湊演算法：

效率高，長文本也能高效地計算出hash值

hash值不能逆推原文

兩次輸入隻要有一點不同就要保證hash值是不同的

要盡可能保證分散，在table的slot大部分都處于空閑狀态的時候要盡可能降低哈希沖突

（3）putVal方法

如果存在key和目前key相同的話，就不再插入了

 寫資料分為四種情況（但是計算哈希的方式是一樣的）

slot==null

直接使用slot即可：将put方法傳遞進來的key和value包裝成一個node對象放到slot中即可

slot！=null并且他引用的node還沒有鍊化

對比一下目前的key與node對象的key是否相等，相等的話就會進行replace操作，否則的話就是哈希沖突在slot的node後面追加node就可以了，采用的是尾插法（1.8，1.7是頭插法）

slot内的node已經鍊化

疊代查詢node，對比目前key是否與連結清單上的key一緻，相等的話就會進行replace操作，否則的話就繼續疊代到尾結點也沒有比對到完全一緻的node就把資料包裝成node追加到連結清單尾部。再檢查目前連結清單的長度有沒有達到樹化的門檻值，達到的話就調用樹化方法，

沖突很嚴重的情況下，已經鍊化為紅黑樹

找到他的父節點的流程：

一直向下探測，直到查詢到左子樹或右子樹為null的情況，說明沒有查找到node的key與目前的key一緻的TreeNode，此時就是插入父節點所在，然後将目前結點插入到父節點的左子樹或右子樹

探測的過程中TreeNode與目前結點的key完全一緻，要進行一次replace操作（直接替換TreeNode的value字段）

4、resize方法

如果元素較多且數組較小的話就會造成連結清單的鍊化嚴重，查找的效率較低

（1）源碼

資料量字段已經達到擴容門檻值，會判斷目前需要插入的字段位置是否為null，不為null才會擴容

采用右移一位增加二倍的方式，并且位運算對CPU來說比較簡潔，效率高

老數組的資料遷移：

slot存儲的是null，不用處理

存儲的是node，node無鍊化，當slot中存儲的node結點next是null的時候，沒有發生哈希沖突直接遷移就好了，根據新表的TableSize計算出它在新表的位置

存儲的是鍊化的node，node節點的next不為null，說明發生了哈希沖突，需要将目前slot中儲存的連結清單拆成兩個連結清單（低位鍊和高位鍊）

存儲的是一個紅黑樹的根結點TreeNode對象 

5、get方法

（1）get方法：

（2）getNode方法：

　　通過<code>hash()</code>函數得到對應<code>bucket</code>的下标，然後依次周遊沖突連結清單，通過<code>key.equals(k)</code>方法來判斷是否是要找的那個<code>entry</code>。

6、remove方法

（1）remove方法：

（2）removeNode方法：

7、repalce方法

每個人都會有一段異常艱難的時光 。 生活的壓力 ， 工作的失意 ， 學業的壓力。 愛的惶惶不可終日。 挺過來的 ，人生就會豁然開朗。 挺不過來的 ，時間也會教你 ，怎麼與它們握手言和 ，是以不必害怕的。 ——楊绛