//序列化版本號，在序列化和反序列化的時候使用
   private static final long serialVersionUID = 362498820763181265L;
  //集合初始容量為16，   
  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
   //最大容量 table數(shù)組存放元素的最大數(shù)量  
   static final int MAXIMUM_CAPACITY = 1 << 30;
    //負載因子默認為0.75   負載因子= 表中的元素個數(shù)/散列表的長度，達到0.75擴容  
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    //鏈表轉(zhuǎn)成樹的閾值，鏈表中的元素個數(shù)大于8，變?yōu)榧t黑樹和MIN_TREEIFY_CAPACITY一起決定的
    static final int TREEIFY_THRESHOLD = 8;
     //樹轉(zhuǎn)換成鏈表的閾值    樹中的元素小于6，轉(zhuǎn)換為鏈表
     static final int UNTREEIFY_THRESHOLD = 6;
    //最小轉(zhuǎn)成樹的容量，當(dāng)數(shù)組長度達到64轉(zhuǎn)換為紅黑樹----和TREEIFY_THRESHOLD一起決定的
    static final int MIN_TREEIFY_CAPACITY = 64;

   //存放元素的數(shù)組 
    transient Node<K,V>[] table;
    //存放Entry類型的元素集合  
    transient Set<Map.Entry<K,V>> entrySet;
   //哈希表中元素的個數(shù)
    transient int size;
    //每次擴容和更改map結(jié)構(gòu)的計數(shù)器
    transient int modCount;
   //擴容的閾值，當(dāng)實際大小為(16 * 0.75 = 12) 閾值時開始擴容 
    int threshold;
   //哈希表自己的負載因子
    final float loadFactor;

//指定容量大小的構(gòu)造函數(shù)
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/*
	 指定“容量大小”和“加載因子”的構(gòu)造函數(shù)
	 initialCapacity: 指定的容量
	 loadFactor:指定的加載因子
*/
public HashMap(int initialCapacity, float loadFactor) {
    //判斷初始化容量initialCapacity是否小于0
    if (initialCapacity < 0)
        //如果小于0，則拋出非法的參數(shù)異常IllegalArgumentException
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    //判斷初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY-》2的30次冪
    if (initialCapacity > MAXIMUM_CAPACITY)
        //如果超過MAXIMUM_CAPACITY，會將MAXIMUM_CAPACITY賦值給initialCapacity
        initialCapacity = MAXIMUM_CAPACITY;
    //判斷負載因子loadFactor是否小于等于0或者是否是一個非數(shù)值
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        //如果滿足上述其中之一，則拋出非法的參數(shù)異常IllegalArgumentException
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    //將指定的加載因子賦值給HashMap成員變量的負載因子loadFactor
    this.loadFactor = loadFactor;
    /*
    		tableSizeFor(initialCapacity) 判斷指定的初始化容量是否是2的n次冪，如果不是那么會變?yōu)楸戎付ǔ跏蓟萘看蟮淖钚〉?的n次冪。
    		但是注意，在tableSizeFor方法體內(nèi)部將計算后的數(shù)據(jù)返回給調(diào)用這里了，并且直接賦值給threshold邊界值了。有些人會覺得這里是一個bug,應(yīng)該這樣書寫：
    		this.threshold = tableSizeFor(initialCapacity) *this.loadFactor;
    		這樣才符合threshold的意思（當(dāng)HashMap的size到達threshold這個閾值時會擴容）。
			但是，請注意，在jdk8以后的構(gòu)造方法中，并沒有對table這個成員變量進行初始化，table的初始化被推遲到了put方法中，在put方法中會對threshold重新計算
    	*/
    this.threshold = tableSizeFor(initialCapacity);
}
//無參構(gòu)造
 public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

//返回比指定初始容量大的最小的2的n次方
  static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    //transient Node<K,V>[] table; 表示存儲Map集合中元素的數(shù)組。
    Node<K,V>[] tab;
    Node<K,V> p; 
    //n代表數(shù)組的長度
    int n, i;
    // ① 將table賦值給tab,并判斷是否為null，第一次賦值時肯定為null
    // ② 將tab.length賦值給n，并判斷是否為0
    if ((tab = table) == null || (n = tab.length) == 0)
        //③ 由于數(shù)組為tab==null，對數(shù)組進行初始化，并將初始化后的數(shù)組長度賦值給n
        //④ 執(zhí)行n = (tab = resize()).length，數(shù)組tab每個空間都是null
        n = (tab = resize()).length;
    // ① i = (n - 1) & hash 表示計算數(shù)組的索引賦值給i，即確定元素存放在哪個桶中
    // ② p = tab[i = (n - 1) & hash] 將計算出的數(shù)組索引對應(yīng)的數(shù)據(jù)賦值給節(jié)點p
    // ③ 判斷p是否為null，即當(dāng)前桶沒有哈希沖突，則直接把鍵值對插入空間位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        // ④ 根據(jù)鍵值對創(chuàng)建新的節(jié)點放入該位置的桶中
        // p表示tab[i]，即 newNode(hash, key, value, null)方法返回的Node對象。
        tab[i] = newNode(hash, key, value, null);
    else {
        // ① 執(zhí)行else說明p=tab[i]不等于null，表示這個位置已經(jīng)有值了，
        Node<K,V> e; K k;
        // ② p.hash == hash：比較桶中元素的hash值和新添加元素key的hash值是否相等
        // ③ (k = p.key) == key：比較兩個key的地址值是否相等
        // ④ (key != null && key.equals(k))：能夠執(zhí)行到這里說明兩個key的地址值不相等，
 //那么先判斷后添加的key是否等于null，如果不等于null再調(diào)用equals方法判斷兩個key的內(nèi)容是否相等
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            	// 兩個元素哈希值相等，并且key的值也相等，將舊的元素整體對象賦值給e，用e來記錄
                e = p;
        // hash值不相等或者key不相等；判斷p是否為紅黑樹結(jié)點
        else if (p instanceof TreeNode)
            // 放入樹中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // hash值不相等或者key不相等，說明是鏈表節(jié)點
        else {
            // 如果hash(key)不相同，說明是計算的桶下標(biāo)相同，key也不相同，說明直接插在鏈表最后
            for (int binCount = 0; ; ++binCount) {
                // ① e = p.next 獲取p的下一個元素賦值給e
                // ② 判斷p.next是否等于null，等于null，說明p沒有下一個元素
                // ③ 到達了鏈表的尾部，還沒有找到重復(fù)的key,說明HashMap沒有包含該鍵，將該鍵值對插入鏈表中
                if ((e = p.next) == null) {
                    //④ 創(chuàng)建一個新的節(jié)點插入到尾部
                    p.next = newNode(hash, key, value, null);
                    //① 節(jié)點添加完成之后判斷此時節(jié)點個數(shù)是否大于臨界值8，如果大于則將鏈表轉(zhuǎn)換為紅黑樹
                    //② binCount從0開始計數(shù)，TREEIFY_THRESHOLD - 1=7
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //轉(zhuǎn)換為紅黑樹
                        treeifyBin(tab, hash);
                    break;
                }
                // ① e = p.next 不是null，不是最后一個元素。
                // ②繼續(xù)判斷鏈表中結(jié)點的key值與插入的元素的key值是否相等
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循環(huán)
                    //要添加的元素和鏈表中的存在的元素的key相等了，則跳出for循環(huán)。
                    //不用再繼續(xù)比較了，直接執(zhí)行下面的if語句去替換去 if (e != null) 
                    break;
                //說明新添加的元素和當(dāng)前節(jié)點不相等，繼續(xù)查找下一個節(jié)點。
                // 用于遍歷桶中的鏈表，與前面的e = p.next組合，可以遍歷鏈表
                p = e;
            }
        }
        /*
        	表示在桶中找到key值、hash值與插入元素相等的結(jié)點
        	也就是說通過上面的操作找到了重復(fù)的鍵，所以這里就是把該鍵的值變?yōu)樾碌闹?，并返回舊值
        	這里完成了put方法的修改功能
        */
        if (e != null) { 
            // 記錄e的value
            V oldValue = e.value;
            // onlyIfAbsent為false或者舊值為null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替換舊值:e.value 表示舊值  value表示新值 
                e.value = value;
            // 訪問后回調(diào)
            afterNodeAccess(e);
            // 返回舊值
            return oldValue;
        }
    }
    //修改記錄次數(shù)
    ++modCount;
    // 判斷實際大小是否大于threshold閾值，如果超過則擴容
    if (++size > threshold)
        resize();
    // 插入后回調(diào)
    afterNodeInsertion(evict);
    return null;
} 

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    	// n表示數(shù)組初始化的長度是16 
    	// 數(shù)組的長度必須為2的n次方，這樣能夠讓hash(key)更加均勻的分布在桶下標(biāo)中，減少hash沖突
    	// 使用 & 運算是為了提高效率
        if ((p = tab[i = (n - 1) & hash]) == null)
}

final Node<K,V>[] resize() {
    //得到當(dāng)前數(shù)組
    Node<K,V>[] oldTab = table;
    //如果當(dāng)前數(shù)組等于null長度返回0，否則返回當(dāng)前數(shù)組的長度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //舊閾值點 默認是12(16*0.75)
    int oldThr = threshold;
    int newCap, newThr = 0;
   //第一次的數(shù)組容量都是0肯定
    // ① 數(shù)組容量>0
    if (oldCap > 0) {
        // ① 超過最大值就不再擴充了，就只好隨你碰撞去吧
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // ② 沒超過最大值，數(shù)組容量就擴充為原來的2倍，newCap = 16*2=32
        else if((newCap = oldCap << 1)< MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            //閾值擴大一倍， 默認原來是12 乘以2之后變?yōu)?4
            newThr = oldThr << 1; 
    }
    //② 舊閾值點大于0 直接賦值
    else if (oldThr > 0) 
        newCap = oldThr;
    //③ 直接使用默認值
    else {
        newCap = DEFAULT_INITIAL_CAPACITY;//16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // ① 如果新的容量為0
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // ② 新的閾值threshold = 24
    threshold = newThr;
    // ③ 創(chuàng)建新的哈希表，數(shù)組大小為newCap=32
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // ④ 判斷舊數(shù)組不等于空，遍歷舊的哈希表 ,重新計算桶里元素的新位置,把每個bucket都移動到新的buckets中
    if (oldTab != null) {
        // 把每個bucket都移動到新的buckets中
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            //取出桶中的元素賦值給e
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //① 如果沒有下一個節(jié)點，說明不是鏈表，當(dāng)前桶上只有一個鍵值對，直接插入
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                //② 判斷是否是紅黑樹節(jié)點
                else if (e instanceof TreeNode)
                    //說明是紅黑樹來處理沖突的，則調(diào)用相關(guān)方法把樹分開
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                //③ 說明是鏈表節(jié)點
                else {
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    //遍歷鏈表計算節(jié)點要插入新數(shù)組的位置
                    do {
                        //原索引
                        next = e.next;
                     	//① e這個節(jié)點在resize之后不需要移動位置 
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        //② 否則e這個節(jié)點要插入的位置為：原索引+oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到bucket里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到bucket里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //① 如果數(shù)組為空，或者數(shù)組的長度小于64，就先擴容，而不是將節(jié)點轉(zhuǎn)為紅黑樹
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    //②  執(zhí)行到這里說明哈希表中的數(shù)組長度大于閾值64，開始進行樹形化
    // 將數(shù)組中的元素取出賦值給e,e是哈希表中指定位置桶里的鏈表節(jié)點，從第一個開始
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        ///hd：紅黑樹的頭結(jié)點   tl :紅黑樹的尾結(jié)點
        TreeNode<K,V> hd = null, tl = null;
        do {
            //新創(chuàng)建一個樹的節(jié)點，內(nèi)容和當(dāng)前鏈表節(jié)點e一致
            TreeNode<K,V> p = replacementTreeNode(e, null);
            //將新創(chuàng)鍵的p節(jié)點賦值給紅黑樹的頭結(jié)點
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        //讓桶中的第一個元素即數(shù)組中的元素指向新建的紅黑樹的節(jié)點，以后這個桶里的元素就是紅黑樹,而不是鏈表數(shù)據(jù)結(jié)構(gòu)了
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {
        //判斷數(shù)組中的第一個節(jié)點的hash、key的地址、key的內(nèi)容是否和要查找的key相同，如果相同返回即可
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //如果數(shù)組中節(jié)點還指向了下一個節(jié)點
        if ((e = first.next) != null) {
            //如果是紅黑樹，調(diào)用紅黑樹的getTreeNode()方法
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            //如果是鏈表，遍歷鏈表，查找與key相同的鍵對應(yīng)的節(jié)點，找到只有返回當(dāng)前節(jié)點
            do {
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}