public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    // 具體實現，省略......
}

// 添加鍵值對
public V put(K key, V value) { /* ... */ }
// 空間不足時，進行擴容的函數
final Node<K,V>[] resize() { /* ... */ }

/**
 * 默認初始容量-必須是2的冪。
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
 * 最大容量，如果有參數的構造函數隱式指定了更高的值，則使用。必須是2的冪且要小于等于1<<30。
 */
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
 * 構造函數中未指定時使用的負載因子。
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
 * bin(指table(HashMap中真正存儲數據的變量，下面有定義)中的某一項)中使用紅黑樹而不是鏈表的閾值。
 * 將元素添加到至少有這么多節(jié)點的bin時，容器將可能轉換為樹。
 * 該值必須大于2，并且至少應為8，以滿足在紅黑樹中移除元素后轉換為鏈表的要求。
 */
static final int TREEIFY_THRESHOLD = 8;
/**
 * 在resize操作時樹退化成鏈表的閾值。應小于TREEIFY_THRESHOLD，且最多6，以去匹配刪除元素時的收縮檢測。
 */
static final int UNTREEIFY_THRESHOLD = 6;
/**
 * 可將bin轉化為紅黑樹的最小表容量（否則(即table.length<該值)，如果bin中的節(jié)點太多，則會調整table的大?。?。
 * 應至少為4 * TREEIFY_THRESHOLD，以避免調整大小和樹化閾值之間的沖突。
 */
static final int MIN_TREEIFY_CAPACITY = 64;
/* ---------------- Fields -------------- */
/**
 * table，在第一次使用時初始化(懶加載)，并根據需要調整大小。
 * 分配時，長度總是2的冪（在某些操作中，我們也允許長度為零，以允許當前不需要的引導機制）
 */
transient Node<K,V>[] table;
/**
 * 保留緩存的entrySet()。請注意，AbstractMap字段用于keySet()和values()。
 */
transient Set<Map.Entry<K,V>> entrySet;
/**
 * 此映射中包含的鍵值映射數。
 */
transient int size;
/**
 * 此哈希映射在結構上被修改的次數。
 * 結構修改是指那些改變HashMap中映射的數量或以其他方式修改其內部結構的修改（例如，rehash）。
 * 此字段用于使HashMap的集合視圖上的迭代器快速失敗。（參見ConcurrentModificationException）。
 */
transient int modCount;
/**
 * 要調整大小的下一個大小值(capacity * load factor)。
 */
// (序列化后javadoc描述為true。此外，如果table數組尚未被分配，
//  則此字段保留初始數組容量，或零表示DEFAULT_INITIAL_CAPACITY)
int threshold;
/**
 * 哈希表的加載因子。
 */
final float loadFactor;

/**
 * 如果我們傳入的初始容量(記為a)不是2的指數次冪，會將變量threshold改成大于該數a且最接近這個數a的2的指數次冪。
 * 比如：Map<String, Double> t = new HashMap<>(13);
 *     執(zhí)行上面這句話后，threshold會被賦值為16(tableSizeFor()函數)，因為懶加載，此時不會實例化table；
 *     之后put數據時會實例化table(長度為16)，并將threshold賦值為12。
 *
 * 為什么數組table的長度一定要是2的冪次呢?
 * (1) 為了讓位運算 (n-1)&hash 達到取模（hash%n）的目的，加快運算速度;
 * (2) 更重要的一點是：要保證定位出來的值是在數組的長度之內的，不能超出數組長度；
 * 	   并且減少哈希碰撞，讓每個位都可能被取到，例如：
 * 		正例：(16-1) & hash
 * 		二進制的15：  0000 0000 0000 1111
 * 		hash(隨機)   1101 0111 1011 0000
 * 		hash(隨機)   1101 0111 1011 1111
 * 		結果         0000 0000 0000 0001 ~ 0000 0000 0000 1111
 * 		即得出的索引下標只能在0~15之間，保證了所有索引都在數組長度的范圍內而不會越界
 * 		并且由于2的指數次冪-1都是...1111的形式的，即最后一位是1
 * 		這樣，由于hash是隨機的，進行與運算后每一位都是能取到的
 * 		========================================================================
 * 		反例：(7-1) & hash
 * 		二進制6： 0000 0000 0000 0110
 * 		hash     1011 1001 0101 0000
 * 		hash     1001 0001 0000 1111
 * 		結果      0000 0000 0000 0000 ~ 0000 0000 0000 0110
 * 		即得出的索引范圍在0~6，雖然不會越界，但最后一位是0
 * 		即現在無論hash為何值，0001，0011，0101這幾個值是不可能取到的
 * 		這就加劇了hash碰撞，并且浪費了大量數組空間，顯然是我們不想看到的
 * (3) 讓resize()過程中不需要重新調用哈希函數計算哈希值，加快運行速度
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
 * 最大容量，如果有參數的構造函數隱式指定了更高的值，則使用。必須是2的冪且要小于等于1<<30。
 */
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
 * 默認的加載因子仍是0.75
 *
 * 為什么默認加載因子設為0.75？
 * 	  (1) 當加載因子比較大的時候：節(jié)省空間資源，耗費時間資源(鏈表查詢比較慢)
 *    (2) 當加載因子比較小的時候：節(jié)省時間資源，耗費空間資源
 *    綜合來看，0.75效果最好(可以認為這是JDK源碼工程師測試得到最好結果)
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
 * 樹閾值為8, 如果鏈表長度大于或等于8轉成紅黑樹
 *
 * 為什么樹閾值定為8?
 *    當put進來一個元素，通過hash算法，然后最后定位到同一個桶（鏈表）的概率p會隨著鏈表的長度k的增加而減少。
 * 	  根據jdk源碼注釋，這里p服從泊松分布：p = (exp(-0.5) * pow(0.5, k) / factorial(k))
 * 	  當這個鏈表長度為8的時候，這個概率幾乎接近于0(為0.00000006)，所以我們才會將鏈表轉紅黑樹的臨界值定為8
 *    如下圖
 */
static final int TREEIFY_THRESHOLD = 8;
/**
 * 樹退化閾值為6，如果紅黑樹節(jié)點個數小于或等于6轉成鏈表
 *
 * 為什么樹退化閾值為6，而不是8?
 *    目的是為了防止復雜度震蕩。
 *    例如當前bin中有7個元素，此時不斷進行如下操作：添加一個元素后然后刪除(假設該元素也進入該bin中)
 *    則會出現不斷將鏈表變?yōu)榧t黑樹，然后紅黑樹變?yōu)殒湵淼牟僮?，復雜度飆升，產生震蕩。
 *    這是算法中常用的一種技巧，一種Lazy的技巧。同樣HashMap在創(chuàng)建的時候也采用了這種技巧，即懶加載。
 */
static final int UNTREEIFY_THRESHOLD = 6;
/**
 * 最小樹形化容量閾值64：即 當哈希表中的容量 >= 該值時，才允許樹形化鏈表 （即將鏈表轉換成紅黑樹）
 * 否則，若桶內元素太多時，則直接擴容，而不是樹形化。
 * 目的是為了避免進行擴容、樹形化選擇的沖突，這個值不能小于 4 * TREEIFY_THRESHOLD
 */
static final int MIN_TREEIFY_CAPACITY = 64;

/**
 * 基本哈希bin節(jié)點，用于大多數條目。(請參見下面的TreeNode子類，并在LinkedHashMap中查看其Entry子類。)
 */
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

/**
 * 將指定值(value)與此映射中的指定鍵(key)相關聯。如果映射以前包含鍵(key)的映射，則舊的值(value)被替換
 *
 * @param key 與指定值關聯的鍵
 * @param value 要與指定鍵關聯的值
 * @return 與鍵關聯的上一個值，如果鍵沒有映射，則為null。（null返回也可以表示映射以前與null鍵關聯。）
 */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

/**
 * 計算關鍵字.hashCode（）并將散列的高位（異或）擴散到低位。
 * 由于table使用的掩碼是2的冪次，因此僅在當前掩碼上方的位上變化的哈希集將始終發(fā)生沖突。
 * (在已知的例子中有一組在小表格中保持連續(xù)整數的浮點鍵。)
 * 因此我們應用了一種向下擴展高位影響的變換。在速度、實用性和位擴展質量之間存在一種折衷。
 * 因為許多常見的散列集已經被合理地分布（所以不能從傳播中受益），
 * 而且因為我們使用紅黑樹來處理容器中的大量沖突，所以我們只是以最便宜的方式對一些移位的位進行異或，
 * 以減少系統損失，以及合并最高位的影響，否則由于table邊界，這些最高位將永遠不會用于索引計算。
 */
static final int hash(Object key) {
    int h;
    // 為什么要這么做? 目的：降低hash沖突的幾率的同時保證計算哈希值的速度
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

/**
 * 實現Map.put和相關方法。
 *
 * @param hash 鍵的哈希值
 * @param key 鍵
 * @param value 要放置的值
 * @param onlyIfAbsent 如果為true，則不更改現有值(value)
 * @param evict 如果為false，則table處于創(chuàng)建模式。
 * @return 上一個值，如果沒有則為null
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 1. 如果當前table為空，新建table
    //    如果是空參構造器，默認table長度為16；
    //    如果指定大小，則table的長度為threshold(這個值已經被tableSizeFor()函數變?yōu)?的冪)
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2. 獲取當前key對應的節(jié)點
    // 	  n-1 相當于掩碼，因為 n 是 2 的次冪，所以 n-1 二進制最低位有 k 個1(其中k=log2(n))
    //    (n-1)&hash 是待添加元素應該存放的位置（有沖突的話使用鏈地址法解決）
    //    (n-1)&hash 相當于 hash%n（在n是2的冪次的情況下）
    //    例如 n=4, hash=10 : (n-1)&hash = 0011&1010 =2, 10%4=2
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 3. 如果位置tab[(n-1)&hash]不存在節(jié)點，則新建節(jié)點
        tab[i] = newNode(hash, key, value, null);
    else {
        // 4. 位置tab[(n-1)&hash]存在節(jié)點，采用鏈地址法解決沖突
        Node<K,V> e; K k;
        // 5. key的hash相同 || key的引用相同或者key equals，則覆蓋原本的鍵值對中的值
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 6. 如果當前節(jié)點(上面提到的bin)是一個紅黑樹節(jié)點(樹根)，則將節(jié)點添加到紅黑樹中
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 7. bin不是紅黑樹節(jié)點，也不是相同節(jié)點，則表示為bin為鏈表的頭結點
        else {
            // 8. 找到鏈表中最后的那個節(jié)點
            //    尾插法。不能采用頭插法，因為要比較插入的鍵(key)是否已經存在，存在則替換，否則插入
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 9. 如果鏈表長度(包含當前還未插入的節(jié)點)大于或等于8轉成紅黑樹
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 10.如果鏈表中有相同的節(jié)點，則覆蓋
                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;
            // 是否替換掉value值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 記錄修改次數
    ++modCount;
    // 是否超過容量，超過需要擴容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

/**
 * 初始化 或 加倍table。
 * 如果為空，則根據字段threshold中的值初始化table大小。
 * 否則，因為我們使用的是倍增，所以每個bin中的元素要么留在同一索引中，要么在新表中以二次冪偏移量移動。
 *
 * @return the table
 */
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 1.如果創(chuàng)建HashMap時調用的是有參函數，第一次put時調用該函數時threshold不為0
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {  
        // 2.1 說明空間不足，需要擴增
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    } else if (oldThr > 0) // initial capacity was placed in threshold
        // 2.2 有參函數，第一次put進入這個分支
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // 2.3 無參函數，第一次put進入這個分支
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 3.有參函數，第一次put這個判斷成立；否則不成立
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    // 4.創(chuàng)建新的table用于存放數據，有兩種情況
    //   (1) 懶加載，第一次put會初始化table (2) 倍增
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // 5.將新創(chuàng)建的數組newTab的引用賦值給字段table
    table = newTab;
    // 6.1 oldTab如果為null，說明是第一次put進入的該函數，該函數作用是給table初始化
    if (oldTab != null) {  
        // 6.2 說明需要將oldTab中的數據遷移到newTab中
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    // 7.1 說明這個bin中只有一個數據，直接移入新數組中即可
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 7.2 說明這個bin是紅黑樹的根節(jié)點，......(不是重點，略過)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // 7.3 說明這個bin是鏈表的頭結點，需要將高位和低位斷開
                    //     將一個鏈表分為兩組，縮短了鏈表，提高了性能
                    /*
                     * 假設 oldCap=16，鏈表中存在兩個哈希值，hash1=0b0 1010，hash2=0b1 1010
                     * 此時的j=0b1010，這兩個值最關鍵之處在于最高位值不同，將會被分到低位和高位兩個索引處
                     * 				  hash1			hash2
                     * hash值：       0 1010	   1 1010
                     * oldCap(16)    1 0000		   1 0000
                     * 				 0 0000		   1 0000
                     * hash1對應的節(jié)點將會被放入newTab[j]中，hash2對應的節(jié)點將會被放入newTab[j+oldCap]中
                     * ‘與'運算的結果，只可能有兩種值：0 或者 16
                     * 也就是說當前節(jié)點用當前節(jié)點的hash值和舊數組的長度（16）做'與'運算的結果只可能是0或16
                     */
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {  // 如果是0，則使用低位的指針
                            if (loTail == null) loHead = e;
                            else loTail.next = e;  // 尾插法
                            loTail = e;
                        }
                        else {  // 如果是16，則使用高位的指針
                            if (hiTail == null) hiHead = e;
                            else hiTail.next = e;  // 尾插法
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;  // 把低位的尾部節(jié)點的next值為空（先將高位和低位斷開）
                        newTab[j] = loHead;  // 將低位的頭部賦給新數組的某個值，也就是將高位的所有節(jié)點移動過去
                    }
                    if (hiTail != null) {
                        hiTail.next = null;  // 把高位的尾部節(jié)點的next值為空
                        // 再將高位的頭部放到新數組的j + oldCap索引處（當前索引+舊數組的長度）
                        // 比如說現在的索引是3，再加上數組長度16，最后就是將高位放到新數組的索引為19的地方去
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}