HashMap沒有直接提供putVal接口給使用者調用，而實提供put接口，而他通過putVal來實作插入元素。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
*
* @param hash 指定參數key的哈希值
* @param key 指定參數key
* @param value 指定參數value
* @param onlyIfAbsent 如果為true，即使指定參數key在map中已經存在，也不會替換value
* @param evict 如果為false，數組table在建立模式中
* @return 如果value被替換，則傳回舊的value，否則傳回null。當然，可能key對應的value就是null。
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 參數解析：onlyIfAbsent表示，如果為true，那麼将不會替換已有的值，否則替換
// evict：該參數用于LinkedHashMap，這裡沒有其他作用（空實作）
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab是該方法中内部數組引用，p是數組中首節點，n是内部數組長度，i是key對應的索引下标
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 第一次put的時候，table未初始化，也就是tab為空，需要擴容
if ((tab = table) == null || (n = tab.length) == 0)
// 這裡實作擴容，具體邏輯稍後分析
n = (tab = resize()).length;
// 擷取指定key的對應下标的首節點并指派給p，如果首節點為null，那麼建立一個新的Node節點作為首節點
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// p此時指向的是不為null的首節點，将p指派給e
// 如果首節點的key和要存入的key相同，那麼直接覆寫value的值（在下一個if中執行的）
e = p;
else if (p instanceof TreeNode)
// 如果首節點是紅黑樹的，将鍵值對插添加到紅黑樹，該方法後續分析
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 能走到這裡，說明首節點和新put的的這個節點的key不一樣，且該Node節點不是TreeNode類型
// 開始需要周遊連結清單，如果連結清單中存在該鍵值對，直接覆寫value。
// 如果不存在，則在末端插入鍵值對。然後判斷連結清單長度是否大于等于8（其實就是周遊次數 + 1），
// 嘗試轉換成紅黑樹。注意此處使用“嘗試”，因為在treeifyBin方法中還會判斷
// 目前哈希表長度是否到達64，如果達到，轉換為紅黑樹，否則會放棄次此轉換，優先擴充數組容量。
for (int binCount = 0; ; ++binCount) {
// 當binCount = 0時，也就是第一次if判斷，此時p就是首節點，p.next就是第二個節點
// 其他情況及時連結清單中其他節點，當e == null的時候，也就是到達了連結清單的結尾
if ((e = p.next) == null) {
// 建立一個Node并作為連結清單的最後一個節點
p.next = newNode(hash, key, value, null);
// 判斷周遊次數是否>=7（首節點未周遊，直接從第二個節點開始周遊的，當次數為7時，說明連結清單長度為8）
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// “嘗試”将連結清單轉換為紅黑樹，内部還會判斷哈希表長度，不一定轉換成功，也許是擴容
treeifyBin(tab, hash);
break;
}
// 隻要沒走到上面那個if裡面，說明連結清單沒有周遊結束，如果在連結清單中間發現有key一樣的，那麼就直接将舊值替換成新值
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 将正在周遊的節點指派給p，友善能周遊下一個節點
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;
}
//連結清單轉化為紅黑樹的方法
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 在這裡判斷是否滿足擴容條件，如果滿足就擴容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 到這裡開始周遊連結清單
TreeNode<K,V> hd = null, tl = null;
do {
// 将連結清單中的節點Node類型轉換成為TreeNode
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
// TreeNode連結清單轉換成為紅黑樹
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
} 
在JDK8之後引入了紅黑樹，當哈希表的桶中連結清單元素超過8個的時候（此時哈希表長度不小于64），會自動轉換成紅黑樹。若桶中元素小于等于6時，樹結構還原成連結清單形式。
紅黑樹的平均查找長度是log(n)，長度為8，查找長度為log(8)=3，連結清單的平均查長度為n/2，當長度為8時，平均查找長度為8/2=4，這才有轉換成樹的必要；連結清單長度如果是小于等于6，6/2=3，雖然速度也很快的，但是轉化為樹結構和生成樹的時間并不會太短。以6和8來作為平衡點是因為，中間有個內插補點7可以防止連結清單和樹之間頻繁的轉換。
假設，如果設計成連結清單個數超過8則連結清單轉換成樹結構，連結清單個數小于8則樹結構轉換成連結清單，如果一個HashMap不停的插入、删除元素，連結清單個數在8左右徘徊，就會頻繁的發生樹轉連結清單、連結清單轉樹，效率會很低。概括起來就是：連結清單：如果元素小于8個，查詢成本高，新增成本低，紅黑樹：如果元素大于8個，查詢成本低，新增成本高。