二、HashMap數據結構打開HashMap.java文件，找到以下代碼塊，這個就是HashMap存放數據的對象，可以看出它就是一個“鏈表”的數組。

/** * The table, initialized on first use, and resized as * necessary. When allocated, length is always a power of two. * (We also tolerate length zero in some Operations to allow * bootstrapping mechanics that are currently not needed.) */transient Node<K,V>[] table;再來看看Node<K,V>（鏈表）的定義，我將注釋直接寫在代碼上。
/** * Basic hash bin node, used for most entries.  (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) */static class Node<K,V> implements Map.Entry<K,V> {        final int hash;//hash(key)返回的值        final K key;//鍵        V value;//值        Node<K,V> next;//鏈表的關鍵，naxt中裝載著下一個鏈表        //類構造方法，初始化操作        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; }        //返回hashCode，使用異或算法        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;        }}作者：韋慶明鏈接：https://zhuanlan.zhihu.com/p/25266385來源：知乎著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。很多人可能不是很理解“鏈表”這個概念，我們可以想象一下一根鏈子的特性：
1、一個環套著另外1個圈，串成一條鏈。
2、一個環只能關聯到左右2個環，頭、尾部只能關聯1個。
而上面的代碼中，Node<K,V> next 字段中裝載著下一個鏈表。next 中的 next 又可以裝載著下下個鏈表，一環套一環，這就是鏈表的實現原理。
三、HashMap的存儲和讀取
1） 數組元素存儲規則HashMap是按什么規則存放到數組中的呢？
在JDK1.8之前貌似是按照 hash(key)%len（除余） 來獲取數組下標，并存放到此位置。JDK1.8之后，按照 (len-1) & hash（“與”運算） 來獲取數組下標，并存放到此位置，HashMap作者這樣做的思路沒有表述出來，是因為這個算法的能減少沖突？當然，不管是使用 hash(key)%len還是(len-1) & hash 來計算元素存放位置下標，都會存在一個問題，就是如果數組中這個位置存在數據了，怎么辦？這就是HashMap選擇使用數組+鏈表來實現的好處，如數組下標3的位置存在了數據，那么新插入的數據會存放在這個數組位置的鏈表的末端。注解：len=數組長度圖解，數組下標計算公式使用 hash(key)%len（除余） （講解時候用，比較好找規律）
到此我們大致明白HashMap的數據結構與存放規則了。接下來我們從代碼上一步步解讀它的具體實現。2） put 代碼解讀put() 方法代碼，注釋寫在代碼中。
/** * Associates the specified value with the specified key in this map. * If the map PReviously contained a mapping for the key, the old * value is replaced. * * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with <tt>key</tt>, or *         <tt>null</tt> if there was no mapping for <tt>key</tt>. *         (A <tt>null</tt> return can also indicate that the map *         previously associated <tt>null</tt> with <tt>key</tt>.) */public V put(K key, V value) {    //執行putVal方法，并返回相應的結果    //執行方法前，先執行hash()方法獲取hash    return putVal(hash(key), key, value, false, true);}hash() 方法代碼，注釋寫在代碼中。
/** * Computes key.hashCode() and spreads (XORs) higher bits of hash * to lower.  Because the table uses power-of-two masking, sets of * hashes that vary only in bits above the current mask will * always collide. (Among known examples are sets of Float keys * holding consecutive whole numbers in small tables.)  So we * apply a transform that spreads the impact of higher bits * downward. There is a tradeoff between speed, utility, and * quality of bit-spreading. Because many common sets of hashes * are already reasonably distributed (so don't benefit from * spreading), and because we use trees to handle large sets of * collisions in bins, we just XOR some shifted bits in the * cheapest possible way to reduce systematic lossage, as well as * to incorporate impact of the highest bits that would otherwise * never be used in index calculations because of table bounds. */static final int hash(Object key) {    int h;    //使用三目運算，判斷key=null則等于0，這就表示key=null值的都存放[0]位置。    //否則等于key.hashCode() ^(異或) (key.hashCode() >>>(右移) 16)后的值。    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}putVal() 方法代碼，put的邏輯都寫在此方法中，注釋寫在代碼中。吐槽一下JDK1.8 HashMap的作者，把參數賦值和 if 判斷放到一起，看著真累。
/** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {    //參數字段注釋：    //tab = 主數據集數組對象，p = 主數據集數組中某元素    //n = 主數據集數組長度，i = 新數據插入位置    Node<K,V>[] tab; Node<K,V> p; int n, i;    //判斷table等于null 或 table數組長度等于 0     if ((tab = table) == null || (n = tab.length) == 0)        //執行resize()方法，初始化table，給tab參數賦值，并返回長度給 n 參數        n = (tab = resize()).length;    //給 i 賦值為 n-1 &(與運算) hash 后的值，并將 i 位置的元素賦值給 p 參數    //最后判斷 p 是否等于null    if ((p = tab[i = (n - 1) & hash]) == null)                // p = null 表示數組中這個位置還沒有數據，那么直接插入到這個位置        tab[i] = newNode(hash, key, value, null);    // p != null，那么就說明數組的 i 位置已經有數據了，執行以下操作    else {        //參數字段注釋：e = 主數據集數組中某元素，k = 某元素中的key        Node<K,V> e; K k;        //條件標識名稱：JudgeExistence（后面可以引用）        //判斷規則：必須條件1：p.hash 等于 hash(傳入添加)         //條件2：p.key 等于 key(傳入添加)        //條件3：key(傳入添加) != null 與 key(傳入添加)值 等于 p.key值        //只要符合1+2 或 1+3條件，則判定這個key的數據已經存在        //判斷期間 k 賦值為 p.key        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))            //將 e 賦值為 p            e = p;        //判斷 p 是否為 TreeNode 類型        else if (p instanceof TreeNode)            //調用putTreeVal()方法，將返回值賦值 e             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);        else {            //執行無條件的 for 循環方法            for (int binCount = 0; ; ++binCount) {                //判斷 p.next == null，表示可以在鏈表中這個位置插入新數據                //并將 e 賦值 為 p.next                if ((e = p.next) == null) {                    //將新數據插入到鏈表的末端                    p.next = newNode(hash, key, value, null);                    //判斷循環次數 >= TREEIFY_THRESHOLD(8)-1                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                        //執行 treeifyBin() 方法                        treeifyBin(tab, hash);                    //將新數據插入到鏈表的末端后，停止循環                    break;                }                //判斷條件直接引用條件標識名稱：JudgeExistence                //判斷期間 k 賦值為 e.key                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    //找到相同key的數據，停止循環                    break;                //將 p 賦值為 e ，用于下一次循環判斷                p = e;            }        }        //判斷e 是否成功獲取到數據        if (e != null) { // existing mapping for key            V oldValue = e.value;            //判斷可修改value 標識參數 onlyIfAbsent 是否等于 false            //或 e.value 是否等于 null，只要符合一項條件就可以修改            if (!onlyIfAbsent || oldValue == null)                //覆蓋原value                e.value = value;            afterNodeaccess(e);            return oldValue;        }    }    //HashMap結構被修改的次數，此次數不包括相同key被覆蓋修改的次數    ++modCount;    //判斷 鍵值映射的數目 > （容量*負載因子）上次設置的最大容量    if (++size > threshold)        //重新設置容量（在原有基礎上*2）        //resize()有兩個主要功能，一是初始化table，二是將table容量*2        resize();    afterNodeInsertion(evict);    return null;}
總結 put 的工作流程：
檢查兩個key是否一致的條件：
A = （已經插入的Entity），B = （即將插入的Entity）必須條件1：A.hash 等于 B.hash條件2：A.key 等于 B.key條件3：B.key 不等于 null 與 B.key值.equals(A.key值)只要符合1+2 或 1+3條件，則判定這個key的數據已經存在
1、table數組等于 null 或 table數組長度等于 0 時，會為其執行初始化操作。
2、使用 (len-1) & hash（“與”運算）計算出數組下標后，檢查數組此下標位置是否存在數據，不存在則直接插入數據到該位置。
3、如果第 2 步操作檢查到數據已經存在，檢查即將插入的 key 在 HashMap 中已經存在后，會覆蓋此位置原數據的 value，key不會被覆蓋 。
4、如果第 3 步判斷不成立，那么判斷 此下標位置 是否為 TreeNode 類型，是則獲取putVal版本樹中的數據，并覆蓋此位置原數據的 value，key不會被覆蓋 。
5、以上判斷都不成立，那么循環數組中此下標位置的鏈表。
5-1、循環鏈表，檢查到 next 值等于 null ，則將數據插入到此位置。最先加入的數據在鏈頭，新加入的數據在鏈尾。
5-2、循環鏈表，檢查到即將插入的 key 在鏈表中已經存在后，會覆蓋此位置原數據的 value，key不會被覆蓋 。
6、判斷 鍵值映射的數目 > （容量*負載因子）上次設置的最大容量值的時候，重新設置容量（在原有基礎上*2）。（注：這一步只在數據插入操作時候執行，覆蓋操作時候不執行）
3） get 代碼解讀get() 方法代碼，注釋寫在代碼中。
/** * Returns the value to which the specified key is mapped, * or {@code null} if this map contains no mapping for the key. * * <p>More formally, if this map contains a mapping from a key * {@code k} to a value {@code v} such that {@code (key==null ? k==null : * key.equals(k))}, then this method returns {@code v}; otherwise * it returns {@code null}.  (There can be at most one such mapping.) * * <p>A return value of {@code null} does not <i>necessarily</i> * indicate that the map contains no mapping for the key; it's also * possible that the map explicitly maps the key to {@code null}. * The {@link #containsKey containsKey} operation may be used to * distinguish these two cases. * * @see #put(Object, Object) */public V get(Object key) {    Node<K,V> e;    //e = getNode(hash(key), key)    return (e = getNode(hash(key), key)) == null ? null : e.value;}getNode() 方法代碼，get邏輯代碼寫在此方法內，注釋寫在代碼中。
/** * Implements Map.get and related methods * * @param hash hash for key * @param key the key * @return the node, or null if none */final Node<K,V> getNode(int hash, Object key) {    //參數字段注釋：    //tab = 主數據集數組對象，first,e = 主數據集數組中某元素    //n = 主數據集數組長度，k = tab[x].key    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;    //判斷table不等于null 與 tab.length大于 0 與     //tab[(len-1) & hash] 此下標位置的數據不等于null    //判斷期間，tab賦值為table，n 賦值為tab.length，first 賦值為tab[x]    if ((tab = table) != null && (n = tab.length) > 0 &&        (first = tab[(n - 1) & hash]) != null) {        //條件標識名稱：JudgeExistence（后面可以引用）        //判斷必要條件1：first.hash（上一步獲取到的） 等于 hash（傳入的）        //條件2：first.key 等于 key（傳入的）        //條件3：key（傳入的） 不等于 null 與 key值（傳入的）等于 first.key值        //只要符合1+2 或 1+3條件，則判定這個key的數據存在        //判斷期間 k 賦值為 first.key        if (first.hash == hash && // always check first node            ((k = first.key) == key || (key != null && key.equals(k))))            //返回Node<K,V>數據            return first;        //上個判斷不成立，則從鏈表中找這個數據        //判斷下一個鏈表是否存在        //判斷期間 e 賦值為 first.next        if ((e = first.next) != null) {            //判斷first是否等于TreeNode類型            if (first instanceof TreeNode)                //是則從根節點種獲取到這條數據，并返回                return ((TreeNode<K,V>)first).getTreeNode(hash, key);            //使用do... while循環查找鏈表，直到找到數據或循環到鏈表末端            do {                //判斷條件直接引用條件標識名稱：JudgeExistence                //判斷期間 k 賦值為 e.key                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    //返回Node<K,V>數據                    return e;            } while ((e = e.next) != null);        }    }    return null;}
總結 get() 的工作流程：
相對于put ，get就要簡單很多。
檢查兩個key是否一致的條件：
A = （已經插入的Entity），B = （即將插入的Entity）必須條件1：A.hash 等于 B.hash條件2：A.key 等于 B.key條件3：B.key 不等于 null 與 B.key值.equals(A.key值)只要符合1+2 或 1+3條件，則判定這個key的數據已經存在
它首先使用 (len-1) & hash 算法獲取數組的下標，并使用 key 對比第一個鏈表的數據，如果匹配，返回該鏈表的數據。否則循環該數組下標內的所有鏈表，直至找到匹配的數據。
如果找不到匹配的數據，返回null 。
HashMap工作原理總結：
1、HashMap是鏈表+數組的結合體，它的核心對象就是一個鏈表的數組。
2、HashMap可以存儲 null 的鍵值，鍵=null的時候會默認存放在 數組[0] 位置。
3、HashMap在JDK1.8后使用的數組下標算法為： (len-1) & hash（與運算）。
4、HashMap判斷是否存在重復 key 的核心條件代碼是：
if (e.hash == hash &&      ((k = e.key) == key || (key != null && key.equals(k))))
5、HashMap在出現重復 hash 值但 key 不同的時候，會將新數據插入到該數組下標中鏈表的末端。最先加入的數據在鏈頭，新加入的數據在鏈尾。
6、HashMap在插入數據的時候，如果新數據的 key 已經存在，那么新數據將會覆蓋原數據的 value 值，key不會被覆蓋。
HashMap就講到這里了，有時間再研究一下 resize() 方法吧。