Hashmap資料結構
hashMap是一種基于數組和連結清單（或紅黑樹）的資料結構，它可以通過一個哈希函數将鍵映射到數組的一個位置，并在該位置存儲一個鍵值對的節點。hashMap的put方法主要是計算鍵的哈希值和索引，然後在相應的位置插入或更新節點，如果節點數超過門檻值，就會進行擴容或樹化。hashMap的get方法主要是根據鍵的哈希值和索引，找到對應的位置，然後周遊連結清單或紅黑樹，傳回比對的值。
Node和TreeNode節點
如果是連結清單的Map用Node節點，如果是紅黑樹Map用TreeNode節點。
put源碼
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
put方法通過hash函數計算key對應的哈希值，hash函數源碼如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這裡可以看出HashMap是允許key為null，當是null的時候key就是0。
不為null利用hash異或公式得到一個散列的值。hashCode能懂，就是求key的hash值，為什麼要異或？
具體來說，h = key.hashCode()是将鍵的hashCode()方法傳回的整數值賦給h，h >>> 16是将h無符号右移16位，也就是将高16位移到低16位，高位補0。^是異或運算符，它對兩個操作數的每一位進行邏輯運算，相同為0，不同為1。是以，h ^ (h >>> 16)就是将h的高16位和低16位按位異或，得到一個新的整數值。
對于^運算
- 0 ^ 0 = 0
- 1 ^ 0 = 1
- 0 ^ 1 = 1
- 1 ^ 1 = 0
對于“|”，或運算：
- 0 | 0 = 0
- 0 | 1 = 1
- 1 | 0 = 1
- 1 | 1 = 1
對于"&"，與運算：
- 0 & 0 = 0
- 0 & 1 = 0
- 1 & 0 = 0
- 1 & 1 = 1
為什麼要無符号右移16位
假如一個key是：
11100000 00000000 00000000 00000000
數組長度是8:
00000000 00000000 00000000 00001000
那麼再運算下坐标的時候i = (n - 1) & hash，如果不把高位拿到後邊産生如下結果
11100000 00000000 00000000 00000000
00000000 00000000 00000000 00000111
就會導緻永遠都是7
為了防止高位有值，低位沒有值，是以會将
這樣做的好處是，如果鍵的hashCode()方法傳回的值隻在高16位或低16位有差異，那麼經過這個表達式後，這種差異就會傳播到低16位，進而增加了低16位的随機性和均勻性。這對于hashMap來說很重要，因為它在計算鍵在數組中的索引時，隻用到了低n位（n是數組長度的二進制位數），如果低n位相同，就會導緻哈希沖突。通過這個表達式，可以讓低n位更加分散，進而提高hashMap的性能，提高離散性。
舉個例子：
int a = 2182082319;
a的二進制表示形式是（32位）：
10000010 ， 00001111 ，11101111 ， 00001111
然後，我們無符号右移16位：
00000000 ，00000000，10000010 ， 00001111
最後，我們做異或操作：
10000010 ， 00001111 ，01101101 ， 00001111
是以，這個過程的确可以提高低16位的随機性和均勻性，減少哈希沖突，并提高HashMap的性能。
putVal插入元素
得到key對應的哈希值後，再調用putVal(hash(key), key, value, false, true)方法插入元素：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果數組(哈希表)為null或者長度為0，則進行數組初始化操作
if ((tab = table) == null || (n = tab.length) == 0)
//resize()用于調整hash表的大小，也就是調整table[]的大小。
n = (tab = resize()).length;
// 根據key的哈希值計算出資料插入數組的下标位置，公式為(n-1)&hash
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果該下标位置還沒有元素，則直接建立Node對象，并插入
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果目标位置key已經存在，則直接覆寫
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果目标位置key不存在，并且節點為紅黑樹，則插入紅黑樹中
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 否則為連結清單結構，周遊連結清單，尾部插入
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 如果連結清單長度大于等于TREEIFY_THRESHOLD 8，則考慮轉換為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 轉換為紅黑樹操作，内部還會判斷數組長度是否小于MIN_TREEIFY_CAPACITY，如果是的話不轉換
treeifyBin(tab, hash);
break;
}
// 如果連結清單中已經存在該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;
// 當鍵值對個數大于等于擴容門檻值的時候，進行擴容操作
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
以上代碼解釋:
1、如果table[]數組為空，則進行resize()，進行調整哈希表table[]的大小。
2、求出下坐标并且判斷再table[]是否有值。沒有值直接将自己的節點封裝成Node指派進去。
i = (n - 1) & hash這裡用到了且，求出來的值一定是小于等于n - 1的
3、如果table[]下坐标有值。
3.1、如果key相同，則将value替換。
3.2、判斷節點是不是TreeNode，如果是treeNode，調用紅黑樹的插入。
紅黑樹是一種自平衡的二叉搜尋樹，它有以下五個性質：
每個節點是紅色或黑色的。
根節點是黑色的。
所有的葉子節點（空節點）是黑色的。
如果一個節點是紅色的，那麼它的兩個子節點都是黑色的。
從任意一個節點到其後代葉子節點的每條路徑都包含相同數目的黑色節點。
在紅黑樹中插入一個新節點時，需要遵循以下規則：
如果樹為空，那麼插入新節點作為根節點，并将其顔色設為黑色。
如果樹不為空，那麼插入新節點作為一個葉子節點，并将其顔色設為紅色。
如果新節點的父節點是黑色的，那麼不需要做任何改變。
如果新節點的父節點是紅色的，那麼需要根據新節點的叔叔節點（父節點的兄弟節點）的顔色進行不同的操作：
如果叔叔節點是紅色的，那麼将父節點和叔叔節點的顔色設為黑色，将祖父節點（父節點的父節點）的顔色設為紅色，并将新節點指向祖父節點，重複步驟3和4。
如果叔叔節點是黑色或空的，那麼根據新節點、父節點和祖父節點之間的位置關系，有四種情況：
左左情況：父節點是祖父節點的左子節點，新節點是父節點的左子節點。這時需要對祖父節點進行右旋，并交換父節點和祖父節點的顔色。
左右情況：父節點是祖父節點的左子節點，新節點是父節點的右子節點。這時需要對父節點進行左旋，然後轉化為左左情況。
右右情況：父節點是祖父節點的右子節點，新節點是父節點的右子節點。這時需要對祖父節點進行左旋，并交換父節點和祖父節點的顔色。
右左情況：父節點是祖父節點的右子節點，新節點是父節點的左子節點。這時需要對父節 點進行右旋，然後轉化為右右情況。
其實隻要記住是一個自平衡二叉樹，之前看左神說的，為什麼要寫紅黑樹而不寫二叉平衡樹，可能的原因是裝 .，看的高深一點，沒别的了，你寫個平衡樹二叉樹不好嗎，寫這麼複雜，看吧最後這部分源碼的改。笑死了哈哈哈。
3.3、如果不是樹節點，則循環連結清單，從頭開始循環，如果查過8，則将連結清單轉換為紅黑樹，如果每有超過則節點指派到最後。這裡會有個問題，因為再插入的時候不是原子操作。如果這個時候有另外一個線程把連結清單改成二叉樹，那麼這個節點可能就找不到了。
擴容
再put的最後：
if (++size > threshold)
resize();
- size：這個成員變量表示 HashMap 目前已存儲的鍵值對的數量。這裡size是map裡邊的數量，由于不是原子，是以，有可能mapi邊的值大于size。
- threshold：這個成員變量表示 HashMap 的門檻值，當 HashMap 中存儲的鍵值對數量超過這個門檻值時，HashMap 會自動增大容量（即進行 rehashing）。預設情況下，threshold 是 HashMap 容量數組的長度的 0.75 倍（因為 HashMap 的加載因子預設為 0.75），你可以在 HashMap 的構造函數中指定其它的加載因子。
當你調用 put 方法添加鍵值對時，size 會增加。如果 size 超過了 threshold，則調用 resize 方法來擴容和重新哈希 HashMap。這個過程是在 HashMap 的内部自動完成的，你不需要手動給 size 和 threshold 指派。
為了避免頻繁擴容，再初始化hashMap的時候設定好hashMsp的容量。
為什麼擴容是2的倍數
舉個例子來看，有兩個key分别是：
00000000 ， 00000000，00000000， 00001101
00000000 ， 00000000，00000000， 01001101
數組的長度是8然後-1是：
00000000 ， 00000000，00000000， 00000111
再數組*2-1也就是擴容完之後：
00000000 ， 00000000，00000000， 00001111
運算有可能仍然是原來index，變化不大。如果擴容乘以3之後-1
00000000, 00000000, 00000000, 00010111
這中間有個0，10111，對比原來的1111，如果每次擴容的時候，&運算變化很大的情況就導緻，原來的node一直在數組中換下坐标。
為什麼是擴容因子是0.75倍？
HashMap的查找效率依賴于哈希沖突的程度。如果哈希沖突太多，每個桶(bucket)裡的元素就會增多，這樣查找時就需要周遊更多的元素。在極端情況下，如果所有的元素都在同一個桶裡，那麼HashMap就退化成了連結清單，查找效率會顯著下降。
加載因子較低意味着HashMap會更早地進行擴容，這會使得元素更分散，減少哈希沖突，提高查找效率。但是過低的加載因子會導緻記憶體浪費，因為很多桶都是空的。
加載因子的選擇涉及到時間和空間效率的權衡：
- 如果加載因子太高，例如1.0或接近1.0，那麼HashMap中的哈希沖突會更頻繁，這會導緻查找效率下降，因為需要經常周遊連結清單（或者在Java 8中可能是紅黑樹）。
- 如果加載因子太低，例如0.1或更低，那麼雖然哈希沖突會減少，查找效率提高，但是HashMap占用的記憶體空間會大幅度增加，因為很多槽位(bucket)都是空的。
是以，我們需要在空間和時間之間找到一個平衡點。經過實驗和實踐，0.75是被發現的一個不錯的折中方案，它在空間和時間效率之間取得了一個較好的平衡。這也是為什麼Java中的HashMap預設加載因子是0.75。
擴容的為什麼要尾插法？
擴容會把原來的hashMap數組擴容到原來的兩倍，并且裡邊所有的node都需要重新插入一次。重新插入不會轉換成為紅黑樹，隻有再put的時候會去判斷。
舉個例子來解釋：有兩個線程分别是t1、t2。兩個節點分别是n1、n2。其中n1->n2。
擴容後，會将原來的桶的連結清單循環插入新的連結清單。一定要注意是循環，中止條件是next不為null。
線程1執行，将n1放入到新數組中。
線程2執行，将n1放到新數組中。
線程1執行，将n1的next指向null，并将n2插入數組的頭不，n2next指向n1。
好了産生循環了，n2->1
線程2執行，去拿n2的時候，這時候n2已經指向了n1，産生了循環，它next永遠不是null，是以線程2的循環不會停止。
尾插法不會導緻死循環，主要是因為當使用尾插法時，新節點總是被插入到連結清單的尾部。是以不會出現一個節點的next指向自己之前的節點，即不會形成一個環。