public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    // 具體實(shí)現(xiàn)，省略......
}

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

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

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

/**
 * 基本哈希bin節(jié)點(diǎn)，用于大多數(shù)條目。(請(qǐng)參見(jiàn)下面的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)相關(guān)聯(lián)。如果映射以前包含鍵(key)的映射，則舊的值(value)被替換
 *
 * @param key 與指定值關(guān)聯(lián)的鍵
 * @param value 要與指定鍵關(guān)聯(lián)的值
 * @return 與鍵關(guān)聯(lián)的上一個(gè)值，如果鍵沒(méi)有映射，則為null。（null返回也可以表示映射以前與null鍵關(guān)聯(lián)。）
 */
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

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

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

/**
 * 初始化 或 加倍table。
 * 如果為空，則根據(jù)字段threshold中的值初始化table大小。
 * 否則，因?yàn)槲覀兪褂玫氖潜对?，所以每個(gè)bin中的元素要么留在同一索引中，要么在新表中以二次冪偏移量移動(dòng)。
 *
 * @return the table
 */
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 1.如果創(chuàng)建HashMap時(shí)調(diào)用的是有參函數(shù)，第一次put時(shí)調(diào)用該函數(shù)時(shí)threshold不為0
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {  
        // 2.1 說(shuō)明空間不足，需要擴(kuò)增
        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 有參函數(shù)，第一次put進(jìn)入這個(gè)分支
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // 2.3 無(wú)參函數(shù)，第一次put進(jìn)入這個(gè)分支
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 3.有參函數(shù)，第一次put這個(gè)判斷成立；否則不成立
    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用于存放數(shù)據(jù)，有兩種情況
    //   (1) 懶加載，第一次put會(huì)初始化table (2) 倍增
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // 5.將新創(chuàng)建的數(shù)組newTab的引用賦值給字段table
    table = newTab;
    // 6.1 oldTab如果為null，說(shuō)明是第一次put進(jìn)入的該函數(shù)，該函數(shù)作用是給table初始化
    if (oldTab != null) {  
        // 6.2 說(shuō)明需要將oldTab中的數(shù)據(jù)遷移到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 說(shuō)明這個(gè)bin中只有一個(gè)數(shù)據(jù)，直接移入新數(shù)組中即可
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 7.2 說(shuō)明這個(gè)bin是紅黑樹(shù)的根節(jié)點(diǎn)，......(不是重點(diǎn)，略過(guò))
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // 7.3 說(shuō)明這個(gè)bin是鏈表的頭結(jié)點(diǎn)，需要將高位和低位斷開(kāi)
                    //     將一個(gè)鏈表分為兩組，縮短了鏈表，提高了性能
                    /*
                     * 假設(shè) oldCap=16，鏈表中存在兩個(gè)哈希值，hash1=0b0 1010，hash2=0b1 1010
                     * 此時(shí)的j=0b1010，這兩個(gè)值最關(guān)鍵之處在于最高位值不同，將會(huì)被分到低位和高位兩個(gè)索引處
                     * 				  hash1			hash2
                     * hash值：       0 1010	   1 1010
                     * oldCap(16)    1 0000		   1 0000
                     * 				 0 0000		   1 0000
                     * hash1對(duì)應(yīng)的節(jié)點(diǎn)將會(huì)被放入newTab[j]中，hash2對(duì)應(yīng)的節(jié)點(diǎn)將會(huì)被放入newTab[j+oldCap]中
                     * ‘與'運(yùn)算的結(jié)果，只可能有兩種值：0 或者 16
                     * 也就是說(shuō)當(dāng)前節(jié)點(diǎn)用當(dāng)前節(jié)點(diǎn)的hash值和舊數(shù)組的長(zhǎng)度（16）做'與'運(yùn)算的結(jié)果只可能是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é)點(diǎn)的next值為空（先將高位和低位斷開(kāi)）
                        newTab[j] = loHead;  // 將低位的頭部賦給新數(shù)組的某個(gè)值，也就是將高位的所有節(jié)點(diǎn)移動(dòng)過(guò)去
                    }
                    if (hiTail != null) {
                        hiTail.next = null;  // 把高位的尾部節(jié)點(diǎn)的next值為空
                        // 再將高位的頭部放到新數(shù)組的j + oldCap索引處（當(dāng)前索引+舊數(shù)組的長(zhǎng)度）
                        // 比如說(shuō)現(xiàn)在的索引是3，再加上數(shù)組長(zhǎng)度16，最后就是將高位放到新數(shù)組的索引為19的地方去
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}