查询已有链表的hashmap_面试官再问你 HashMap 底层原理，就把这篇文章甩给他看...
前言
HashMap 源碼和底層原理在現在面試中是必問的。因此，我們非常有必要搞清楚它的底層實現和思想，才能在面試中對答如流，跟面試官大戰三百回合。文章較長，介紹了很多原理性的問題，希望對你有所幫助~
目錄
本篇文章主要包括以下內容：
- HashMap 的存儲結構
- 常用變量說明，如加載因子等
- HashMap 的四個構造函數
- tableSizeFor()方法及作用
- put()方法詳解
- hash()方法，以及避免哈希碰撞的原理
- resize()擴容機制及原理
- get()方法
- 為什么HashMap鏈表會形成死循環，JDK1.8做了哪些優化
正文
說明：本篇主要以JDK1.8的源碼來分析，順帶講下和JDK1.7的一些區別。
HashMap存儲結構
這里需要區分一下，JDK1.7和 JDK1.8之后的 HashMap 存儲結構。在JDK1.7及之前，是用數組加鏈表的方式存儲的。
但是，眾所周知，當鏈表的長度特別長的時候，查詢效率將直線下降，查詢的時間復雜度為 O(n)。因此，JDK1.8 把它設計為達到一個特定的閾值之后，就將鏈表轉化為紅黑樹。
這里簡單說下紅黑樹的特點：
由于紅黑樹，是一個自平衡的二叉搜索樹，因此可以使查詢的時間復雜度降為O(logn)。（紅黑樹不是本文重點，不了解的童鞋可自行查閱相關資料哈）
HashMap 結構示意圖：
常用的變量
在 HashMap源碼中，比較重要的常用變量，主要有以下這些。還有兩個內部類來表示普通鏈表的節點和紅黑樹節點。
//默認的初始化容量為16，必須是2的n次冪 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16//最大容量為 2^30 static final int MAXIMUM_CAPACITY = 1 << 30;//默認的加載因子0.75，乘以數組容量得到的值，用來表示元素個數達到多少時，需要擴容。 //為什么設置 0.75 這個值呢，簡單來說就是時間和空間的權衡。 //若小于0.75如0.5，則數組長度達到一半大小就需要擴容，空間使用率大大降低， //若大于0.75如0.8，則會增大hash沖突的概率，影響查詢效率。 static final float DEFAULT_LOAD_FACTOR = 0.75f;//剛才提到了當鏈表長度過長時，會有一個閾值，超過這個閾值8就會轉化為紅黑樹 static final int TREEIFY_THRESHOLD = 8;//當紅黑樹上的元素個數，減少到6個時，就退化為鏈表 static final int UNTREEIFY_THRESHOLD = 6;//鏈表轉化為紅黑樹，除了有閾值的限制，還有另外一個限制，需要數組容量至少達到64，才會樹化。 //這是為了避免，數組擴容和樹化閾值之間的沖突。 static final int MIN_TREEIFY_CAPACITY = 64;//存放所有Node節點的數組 transient Node<K,V>[] table;//存放所有的鍵值對 transient Set<Map.Entry<K,V>> entrySet;//map中的實際鍵值對個數，即數組中元素個數 transient int size;//每次結構改變時，都會自增，fail-fast機制，這是一種錯誤檢測機制。 //當迭代集合的時候，如果結構發生改變，則會發生 fail-fast，拋出異常。 transient int modCount;//數組擴容閾值 int threshold;//加載因子 final float loadFactor; //普通單向鏈表節點類 static class Node<K,V> implements Map.Entry<K,V> {//key的hash值，put和get的時候都需要用到它來確定元素在數組中的位置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;} }//轉化為紅黑樹的節點類 static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {//當前節點的父節點TreeNode<K,V> parent; //左孩子節點TreeNode<K,V> left;//右孩子節點TreeNode<K,V> right;//指向前一個節點TreeNode<K,V> prev; // needed to unlink next upon deletion//當前節點是紅色或者黑色的標識boolean red;TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);} }HashMap 構造函數
HashMap有四個構造函數可供我們使用，一起來看下：
//默認無參構造，指定一個默認的加載因子 public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; }//可指定容量的有參構造，但是需要注意當前我們指定的容量并不一定就是實際的容量，下面會說 public HashMap(int initialCapacity) {//同樣使用默認加載因子this(initialCapacity, DEFAULT_LOAD_FACTOR); }//可指定容量和加載因子，但是筆者不建議自己手動指定非0.75的加載因子 public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;//這里就是把我們指定的容量改為一個大于它的的最小的2次冪值，如傳過來的容量是14，則返回16//注意這里，按理說返回的值應該賦值給 capacity，即保證數組容量總是2的n次冪，為什么這里賦值給了 threshold 呢？//先賣個關子，等到 resize 的時候再說this.threshold = tableSizeFor(initialCapacity); }//可傳入一個已有的map public HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false); }//把傳入的map里邊的元素都加載到當前map final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {int s = m.size();if (s > 0) {if (table == null) { // pre-sizefloat ft = ((float)s / loadFactor) + 1.0F;int t = ((ft < (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);if (t > threshold)threshold = tableSizeFor(t);}else if (s > threshold)resize();for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {K key = e.getKey();V value = e.getValue();//put方法的具體實現，后邊講putVal(hash(key), key, value, false, evict);}} }tableSizeFor()
上邊的第三個構造函數中，調用了 tableSizeFor 方法，這個方法是怎么實現的呢？
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; }我們以傳入參數為14 來舉例，計算這個過程。
首先，14傳進去之后先減1，n此時為13。然后是一系列的無符號右移運算。
//13的二進制 0000 0000 0000 0000 0000 0000 0000 1101 //無右移1位，高位補0 0000 0000 0000 0000 0000 0000 0000 0110 //然后把它和原來的13做或運算得到，此時的n值 0000 0000 0000 0000 0000 0000 0000 1111 //再以上邊的值，右移2位 0000 0000 0000 0000 0000 0000 0000 0011 //然后和第一次或運算之后的 n 值再做或運算，此時得到的n值 0000 0000 0000 0000 0000 0000 0000 1111 ... //我們會發現，再執行右移 4,8,16位，同樣n的值不變 //當n小于0時，返回1，否則判斷是否大于最大容量，是的話返回最大容量，否則返回 n+1 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; //很明顯我們這里返回的是 n+1 的值， 0000 0000 0000 0000 0000 0000 0000 1111 + 1 0000 0000 0000 0000 0000 0000 0001 0000將它轉為十進制，就是 2^4 = 16 。我們會發現一個規律，以上的右移運算，最終會把最低位的值都轉化為 1111 這樣的結構，然后再加1，就是1 0000 這樣的結構，它一定是 2的n次冪。因此，這個方法返回的就是大于當前傳入值的最小（最接近當前值）的一個2的n次冪的值。
put()方法詳解
//put方法，會先調用一個hash()方法，得到當前key的一個hash值， //用于確定當前key應該存放在數組的哪個下標位置 //這里的 hash方法，我們姑且先認為是key.hashCode()，其實不是的，一會兒細講 public V put(K key, V value) {return putVal(hash(key), key, value, false, true); }//把hash值和當前的key，value傳入進來 //這里onlyIfAbsent如果為true，表明不能修改已經存在的值，因此我們傳入false //evict只有在方法 afterNodeInsertion(boolean evict) { }用到，可以看到它是一個空實現，因此不用關注這個參數 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;//判斷table是否為空，如果空的話，會先調用resize擴容if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//根據當前key的hash值找到它在數組中的下標，判斷當前下標位置是否已經存在元素，//若沒有，則把key、value包裝成Node節點，直接添加到此位置。// i = (n - 1) & hash 是計算下標位置的，為什么這樣算，后邊講if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else { //如果當前位置已經有元素了，分為三種情況。Node<K,V> e; K k;//1.當前位置元素的hash值等于傳過來的hash，并且他們的key值也相等，//則把p賦值給e，跳轉到①處，后續需要做值的覆蓋處理if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//2.如果當前是紅黑樹結構，則把它加入到紅黑樹 else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//3.說明此位置已存在元素，并且是普通鏈表結構，則采用尾插法，把新節點加入到鏈表尾部for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {//如果頭結點的下一個節點為空，則插入新節點p.next = newNode(hash, key, value, null);//如果在插入的過程中，鏈表長度超過了8，則轉化為紅黑樹if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);//插入成功之后，跳出循環，跳轉到①處break;}//若在鏈表中找到了相同key的話，直接退出循環，跳轉到①處if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//① 此時e有兩種情況//1.說明發生了碰撞，e代表的是舊值，因此節點位置不變，但是需要替換為新值//2.說明e是插入鏈表或者紅黑樹，成功后的新節點if (e != null) { // existing mapping for keyV oldValue = e.value;//用新值替換舊值，并返回舊值。//oldValue為空，說明e是新增的節點或者也有可能舊值本來就是空的，因為hashmap可存空值if (!onlyIfAbsent || oldValue == null)e.value = value;//看方法名字即可知，這是在node被訪問之后需要做的操作。其實此處是一個空實現，//只有在 LinkedHashMap才會實現，用于實現根據訪問先后順序對元素進行排序，hashmap不提供排序功能// Callbacks to allow LinkedHashMap post-actions//void afterNodeAccess(Node<K,V> p) { }afterNodeAccess(e);return oldValue;}}//fail-fast機制++modCount;//如果當前數組中的元素個數超過閾值，則擴容if (++size > threshold)resize();//同樣的空實現afterNodeInsertion(evict);return null; }hash()計算原理
前面 put 方法中說到，需要先把當前key進行哈希處理，我們看下這個方法是怎么實現的。
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }這里，會先判斷key是否為空，若為空則返回0。這也說明了hashMap是支持key傳 null 的。若非空，則先計算key的hashCode值，賦值給h，然后把h右移16位，并與原來的h進行異或處理。為什么要這樣做，這樣做有什么好處呢？
我們知道，hashCode()方法繼承自父類Object，它返回的是一個 int 類型的數值，可以保證同一個應用單次執行的每次調用，返回結果都是相同的（這個說明可以在hashCode源碼上找到），這就保證了hash的確定性。在此基礎上，再進行某些固定的運算，肯定結果也是可以確定的。
我隨便運行一段程序，把它的 hashCode的二進制打印出來，如下。
public static void main(String[] args) {Object o = new Object();int hash = o.hashCode();System.out.println(hash);System.out.println(Integer.toBinaryString(hash));} //1836019240 //1101101011011110110111000101000然后，進行 (h = key.hashCode()) ^ (h >>> 16) 這一段運算。
//h原來的值 0110 1101 0110 1111 0110 1110 0010 1000 //無符號右移16位，其實相當于把低位16位舍去，只保留高16位 0000 0000 0000 0000 0110 1101 0110 1111 //然后高16位和原 h進行異或運算 0110 1101 0110 1111 0110 1110 0010 1000 ^ 0000 0000 0000 0000 0110 1101 0110 1111 = 0110 1101 0110 1111 0000 0011 0100 0111可以看到，其實相當于，我們把高16位值和當前h的低16位進行了混合，這樣可以盡量保留高16位的特征，從而降低哈希碰撞的概率。
思考一下，為什么這樣做，就可以降低哈希碰撞的概率呢？先別著急，我們需要結合 i = (n - 1) & hash 這一段運算來理解。
** (n-1) & hash 作用**
//② //這是 put 方法中用來根據hash()值尋找在數組中的下標的邏輯， //n為數組長度， hash為調用 hash()方法混合處理之后的hash值。 i = (n - 1) & hash復制代碼我們知道，如果給定某個數值，去找它在某個數組中的下標位置時，直接用模運算就可以了（假設數組值從0開始遞增）。如，我找 14 在數組長度為16的數組中的下標，即為 14 % 16，等于14 。 18的位置即為 18%16，等于2。
而②中，就是取模運算的位運算形式。以18%16為例
//18的二進制 0001 0010 //16 -1 即 15的二進制 0000 1111 //與運算之后的結果為 0000 0010 // 可以看到，上邊的結果轉化為十進制就是 2 。 //其實我們會發現一個規律，因為n是2的n次冪，因此它的二進制表現形式肯定是類似于 0001 0000 //這樣的形式，只有一個位是1，其他位都是0。而它減 1 之后的形式就是類似于 0000 1111 //這樣的形式，高位都是0，低位都是1，因此它和任意值進行與運算，結果值肯定在這個區間內 0000 0000 ~ 0000 1111 //也就是0到15之間，（以n為16為例） //因此，這個運算就可以實現取模運算，而且位運算還有個好處，就是速度比較快。復制代碼為什么高低位異或運算可以減少哈希碰撞
我們想象一下，假如用 key 原來的hashCode值，直接和 (n-1) 進行與運算來求數組下標，而不進行高低位混合運算，會產生什么樣的結果。
//例如我有另外一個h2，和原來的 h相比較，高16位有很大的不同，但是低16位相似度很高，甚至相同的話。 //原h值 0110 1101 0110 1111 0110 1110 0010 1000 //另外一個h2值 0100 0101 1110 1011 0110 0110 0010 1000 // n -1 ,即 15 的二進制 0000 0000 0000 0000 0000 0000 0000 1111 //可以發現 h2 和 h 的高位不相同，但是低位相似度非常高。 //他們分別和 n -1 進行與運算時，得到的結果卻是相同的。（此處n假設為16） //因為 n-1 的高16位都是0，不管 h 的高 16 位是什么，與運算之后，都不影響最終結果，高位一定全是 0 //因此，哈希碰撞的概率就大大增加了，并且 h 的高16 位特征全都丟失了。愛思考的同學可能就會有疑問了，我進行高低16位混合運算，是可以的，這樣可以保證盡量減少高區位的特征。那么，為什么選擇用異或運算呢，我用與、或、非運算不行嗎？
這是有一定的道理的。我們看一個表格，就能明白了。
可以看到兩個值進行與運算，結果會趨向于0；或運算，結果會趨向于1；而只有異或運算，0和1的比例可以達到1:1的平衡狀態。（非呢？別扯犢子了，兩個值怎么做非運算。。。）
所以，異或運算之后，可以讓結果的隨機性更大，而隨機性大了之后，哈希碰撞的概率當然就更小了。
以上，就是為什么要對一個hash值進行高低位混合，并且選擇異或運算來混合的原因。
resize() 擴容機制
在上邊 put 方法中，我們會發現，當數組為空的時候，會調用 resize 方法，當數組的 size 大于閾值的時候，也會調用 resize方法。 那么看下 resize 方法都做了哪些事情吧。
final Node<K,V>[] resize() {//舊數組Node<K,V>[] oldTab = table;//舊數組的容量int oldCap = (oldTab == null) ? 0 : oldTab.length;//舊數組的擴容閾值，注意看，這里取的是當前對象的 threshold 值，下邊的第2種情況會用到。int oldThr = threshold;//初始化新數組的容量和閾值，分三種情況討論。int newCap, newThr = 0;//1.當舊數組的容量大于0時，說明在這之前肯定調用過 resize擴容過一次，才會導致舊容量不為0。//為什么這樣說呢，之前我在 tableSizeFor 賣了個關子，需要注意的是，它返回的值是賦給了 threshold 而不是 capacity。//我們在這之前，壓根就沒有在任何地方看到過，它給 capacity 賦初始值。if (oldCap > 0) {//容量達到了最大值if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}//新數組的容量和閾值都擴大原來的2倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}//2.到這里，說明 oldCap <= 0，并且 oldThr(threshold) > 0，這就是 map 初始化的時候，第一次調用 resize的情況//而 oldThr的值等于 threshold，此時的 threshold 是通過 tableSizeFor 方法得到的一個2的n次冪的值(我們以16為例)。//因此，需要把 oldThr 的值，也就是 threshold ，賦值給新數組的容量 newCap，以保證數組的容量是2的n次冪。//所以我們可以得出結論，當map第一次 put 元素的時候，就會走到這個分支，把數組的容量設置為正確的值（2的n次冪)//但是，此時 threshold 的值也是2的n次冪，這不對啊，它應該是數組的容量乘以加載因子才對。別著急，這個會在③處理。else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;//3.到這里，說明 oldCap 和 oldThr 都是小于等于0的。也說明我們的map是通過默認無參構造來創建的，//于是，數組的容量和閾值都取默認值就可以了，即 16 和 12。else { // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//③ 這里就是處理第2種情況，因為只有這種情況 newThr 才為0，//因此計算 newThr（用 newCap即16 乘以加載因子 0.75，得到 12） ，并把它賦值給 thresholdif (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}//賦予 threshold 正確的值，表示數組下次需要擴容的閾值（此時就把原來的 16 修正為了 12）。threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;//如果原來的數組不為空，那么我們就需要把原來數組中的元素重新分配到新的數組中//如果是第2種情況，由于是第一次調用resize，此時數組肯定是空的，因此也就不需要重新分配元素。if (oldTab != null) {//遍歷舊數組for (int j = 0; j < oldCap; ++j) {Node<K,V> e;//取到當前下標的第一個元素，如果存在，則分三種情況重新分配位置if ((e = oldTab[j]) != null) {oldTab[j] = null;//1.如果當前元素的下一個元素為空，則說明此處只有一個元素//則直接用它的hash()值和新數組的容量取模就可以了，得到新的下標位置。if (e.next == null)newTab[e.hash & (newCap - 1)] = e;//2.如果是紅黑樹結構，則拆分紅黑樹，必要時有可能退化為鏈表else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap);//3.到這里說明，這是一個長度大于 1 的普通鏈表，則需要計算并//判斷當前位置的鏈表是否需要移動到新的位置else { // preserve order// loHead 和 loTail 分別代表鏈表舊位置的頭尾節點Node<K,V> loHead = null, loTail = null;// hiHead 和 hiTail 分別代表鏈表移動到新位置的頭尾節點Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;//如果當前元素的hash值和oldCap做與運算為0，則原位置不變if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}//否則，需要移動到新的位置else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);//原位置不變的一條鏈表，數組下標不變if (loTail != null) {loTail.next = null;newTab[j] = loHead;}//移動到新位置的一條鏈表，數組下標為原下標加上舊數組的容量if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab; }上邊還有一個非常重要的運算，我們沒有講解。就是下邊這個判斷，它用于把原來的普通鏈表拆分為兩條鏈表，位置不變或者放在新的位置。
if ((e.hash & oldCap) == 0) {} else {}我們以原數組容量16為例，擴容之后容量為32。說明下為什么這樣計算。
還是用之前的hash值舉例。
//e.hash值 0110 1101 0110 1111 0110 1110 0010 1000 //oldCap值，即16 0000 0000 0000 0000 0000 0000 0001 0000 //做與運算，我們會發現結果不是0就是非0， //而且它取決于 e.hash 二進制位的倒數第五位是 0 還是 1， //若倒數第五位為0，則結果為0，若倒數第五位為1，則結果為非0。 //那這個和新數組有什么關系呢？ //別著急，我們看下新數組的容量是32，如果求當前hash值在新數組中的下標，則為 // e.hash &( 32 - 1) 這樣的運算 ，即 hash 與 31 進行與運算， 0110 1101 0110 1111 0110 1110 0010 1000 & 0000 0000 0000 0000 0000 0000 0001 1111 = 0000 0000 0000 0000 0000 0000 0000 1000 //接下來，我們對比原來的下標計算結果和新的下標結果，看圖看下面的圖，我們觀察，hash值和舊數組進行與運算的結果 ，跟新數組的與運算結果有什么不同。
會發現一個規律：
若hash值的倒數第五位是0，則新下標與舊下標結果相同，都為 0000 1000
若hash值的倒數第五位是1，則新下標（0001 1000）與舊下標（0000 1000）結果值相差了 16 。
因此，我們就可以根據 （e.hash & oldCap == 0） 這個判斷的真假來決定，當前元素應該在原來的位置不變，還是在新的位置(原位置 + 16)。
如果，上邊的推理還是不明白的話，我再舉個簡單的例子。
18%16=2 18%32=18 34%16=2 34%32=2 50%16=2 50%32=18怎么樣，發現規律沒，有沒有那個感覺了？
計算中的18，34 ，50 其實就相當于 e.hash 值，和新舊數組做取模運算，得到的結果，要么就是原來的位置不變，要么就是原來的位置加上舊數組的長度。
get()方法
有了前面的基礎，get方法就比較簡單了。
public V get(Object key) {Node<K,V> e;//如果節點為空，則返回null，否則返回節點的value。這也說明，hashMap是支持value為null的。//因此，我們就明白了，為什么hashMap支持Key和value都為nullreturn (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;//首先要確保數組不能為空，然后取到當前hash值計算出來的下標位置的第一個元素if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {//若hash值和key都相等，則說明我們要找的就是第一個元素，直接返回if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;//如果不是的話，就遍歷當前鏈表（或紅黑樹）if ((e = first.next) != null) {//如果是紅黑樹結構，則找到當前key所在的節點位置if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);//如果是普通鏈表，則向后遍歷查找，直到找到或者遍歷到鏈表末尾為止。do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}//否則，說明沒有找到，返回nullreturn null; }為什么HashMap鏈表會形成死循環
準確的講應該是 JDK1.7 的 HashMap 鏈表會有死循環的可能，因為JDK1.7是采用的頭插法，在多線程環境下有可能會使鏈表形成環狀，從而導致死循環。JDK1.8做了改進，用的是尾插法，不會產生死循環。
那么，鏈表是怎么形成環狀的呢？
關于這一點的解釋，我發現網上文章抄來抄去的，而且都來自左耳朵耗子，更驚奇的是，連配圖都是一模一樣的。（別問我為什么知道，因為我也看過耗子叔的文章，哈哈。然而，菜雞的我，那篇文章，并沒有看懂。。。）
我實在看不下去了，于是一怒之下，就有了這篇文章。我會照著源碼一步一步的分析變量之間的關系怎么變化的，并有配圖哦。
我們從 put()方法開始，最終找到線程不安全的那個方法。這里省略中間不重要的過程，我只把方法的跳轉流程貼出來：
//添加元素方法 -> 添加新節點方法 -> 擴容方法 -> 把原數組元素重新分配到新數組中 put() --> addEntry() --> resize() --> transfer()問題就發生在 transfer 這個方法中。
我們假設，原數組容量只有2，其中一條鏈表上有兩個元素 A,B，如下圖
現在，有兩個線程都執行 transfer 方法。每個線程都會在它們自己的工作內存生成一個newTable 的數組，用于存儲變化后的鏈表，它們互不影響（這里互不影響，指的是兩個新數組本身互不影響）。但是，需要注意的是，它們操作的數據卻是同一份。
因為，真正的數組中的內容在堆中存儲，它們指向的是同一份數據內容。就相當于，有兩個不同的引用 X，Y，但是它們都指向同一個對象 Z。這里 X、Y就是兩個線程不同的新數組，Z就是堆中的A，B 等元素對象。
假設線程一執行到了上圖1中所指的代碼①處，恰好 CPU 時間片到了，線程被掛起，不能繼續執行了。 記住此時，線程一中記錄的 e = A ， e.next = B。
然后線程二正常執行，擴容后的數組長度為 4， 假設 A，B兩個元素又碰撞到了同一個桶中。然后，通過幾次 while 循環后，采用頭插法，最終呈現的結構如下：
此時，線程一解掛，繼續往下執行。注意，此時線程一，記錄的還是 e = A，e.next = B，因為它還未感知到最新的變化。
我們主要關注圖1中標注的①②③④處的變量變化：
/** * next = e.next * e.next = newTable[i] * newTable[i] = e; * e = next; *///第一次循環,(偽代碼) e=A;next=B; e.next=null //此時線程一的新數組剛初始化完成，還沒有元素 newTab[i] = A->null //把A節點頭插到新數組中 e=B; //下次循環的e值第一次循環結束后，線程一新數組的結構如下圖：
然后，由于 e=B，不為空，進入第二次循環。
//第二次循環 e=B;next=A; //此時A，B的內容已經被線程二修改為 B->A->null，然后被線程一讀到，所以B的下一個節點指向A e.next=A->null // A->null 為第一次循環后線程一新數組的結構 newTab[i] = B->A->null //新節點B插入之后，線程一新數組的結構 e=A; //下次循環的 e 值第二次循環結束后，線程一新數組的結構如下圖：
此時，由于 e=A，不為空，繼續循環。
//第三次循環 e=A;next=null; // A節點后邊已經沒有節點了 e.next= B->A->null // B->A->null 為第二次循環后線程一新數組的結構 //我們把A插入后，抽象的表達為 A->B->A->null，但是，A只能是一個，不能分身啊 //因此實際上是 e(A).next指向發生了變化，A的 next 由指向 null 改為指向了 B， //而 B 本身又指向A，因此A和B互相指向，成環 newTab[i] = A->B 且 B->A e=next=null; //e此時為空，結束循環第三次循環結束后，看下圖，A的指向由 null ，改為指向為 B，因此 A 和 B 之間成環。
這時，有的同學可能就會問了，就算他們成環了，又怎樣，跟死循環有什么關系？
我們看下 get() 方法（最終調用 getEntry 方法），
可以看到查找元素時，只要 e 不為空，就會一直循環查找下去。若有某個元素 C 的 hash 值也落在了和 A，B元素同一個桶中，則會由于， A，B互相指向，e.next 永遠不為空，就會形成死循環。
原文鏈接：https://juejin.im/post/5e93ca9d6fb9a03c3176248f
總結
以上是生活随笔為你收集整理的查询已有链表的hashmap_面试官再问你 HashMap 底层原理，就把这篇文章甩给他看...的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： c++创建文件_使用Python实现文件
- 下一篇： python 初始化一个4维向量_看图学