.net 怎么循環得到數組里的值_HashMap 底層實現、加載因子、容量值及死循環

寫在前面：2020年面試必備的Java后端進階面試題總結了一份復習指南在Github上，內容詳細，圖文并茂，有需要學習的朋友可以Star一下！

GitHub地址：abel-max/Java-Study-Note

HashMap 簡介
HashMap 是一個基于哈希表實現的無序的 key-value 容器，它鍵和值允許設置為 null，同時它是線程不安全的。HashMap 底層實現

在 jdk 1.7中 HashMap 是以數組+鏈表的實現的
在 jdk1.8 開始引入紅黑樹，HashMap 底層變成了數組+鏈表+紅黑樹實現

紅黑樹簡介
紅黑樹是一種特殊的平衡二叉樹，它有如下的特征：

節點是紅色或黑色
根節點是黑色的
所有葉子都是黑色。（葉子是NULL節點）
每個紅色節點的兩個子節點都是黑色的（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點）
從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

所以紅黑樹的時間復雜度為: O(lgn)。jdk1.8：數組+鏈表+紅黑樹
HashMap 的底層首先是一個數組，元素存放的數組索引值就是由該元素的哈希值（key-value 中 key 的哈希值）確定的，這就可能產生一種特殊情況——不同的 key 哈希值相同。
在這樣的情況下，于是引入鏈表，如果 key 的哈希值相同，在數組的該索引中存放一個鏈表，這個鏈表就包含了所有 key 的哈希值相同的 value 值，這就解決了哈希沖突的問題。
但是如果發生大量哈希值相同的特殊情況，導致鏈表很長，就會嚴重影響 HashMap 的性能，因為鏈表的查詢效率需要遍歷所有節點。于是在 jdk1.8 引入了紅黑樹，當鏈表的長度大于8，且 HashMap 的容量大于64的時候，就會將鏈表轉化為紅黑樹。

// jdk1.8
// HashMap#putVal// binCount 是該鏈表的長度計數器，當鏈表長度大于等于8時，執行樹化方法
// TREEIFY_THRESHOLD = 8
if (binCount >= TREEIFY_THRESHOLD - 1)treeifyBin(tab, hash);// HashMap#treeifyBin    
final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;// MIN_TREEIFY_CAPACITY=64// 若 HashMap 的大小小于64，僅擴容，不樹化if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)resize();else if ((e = tab[index = (n - 1) & hash]) != null) {TreeNode<K,V> hd = null, tl = null;do {TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)hd = p;else {p.prev = tl;tl.next = p;}tl = p;} while ((e = e.next) != null);if ((tab[index] = hd) != null)hd.treeify(tab);}
}

加載因子為什么是0.75
所謂的加載因子，也叫擴容因子或者負載因子，它是用來進行擴容判斷的。
假設加載因子是0.5，HashMap 初始化容量是16，當 HashMap 中有 16 * 0。5=8個元素時，HashMap 就會進行擴容操作。
而 HashMap 中加載因子為0.75，是考慮到了性能和容量的平衡。
由加載因子的定義，可以知道它的取值范圍是(0, 1]。

如果加載因子過小，那么擴容門檻低，擴容頻繁，這雖然能使元素存儲得更稀疏，有效避免了哈希沖突發生，同時操作性能較高，但是會占用更多的空間。
如果加載因子過大，那么擴容門檻高，擴容不頻繁，雖然占用的空間降低了，但是這會導致元素存儲密集，發生哈希沖突的概率大大提高，從而導致存儲元素的數據結構更加復雜（用于解決哈希沖突），最終導致操作性能降低。
還有一個因素是為了提升擴容效率。因為 HashMap 的容量（size屬性，構造函數中的initialCapacity變量）有一個要求：它一定是2的冪。所以加載因子選擇了0.75就可以保證它與容量的乘積為整數。

// 構造函數
public HashMap(int initialCapacity, float loadFactor) {// ……this.loadFactor = loadFactor;// 加載因子this.threshold = tableSizeFor(initialCapacity);
}/*** Returns a power of two size for the given target capacity.返回2的冪* MAXIMUM_CAPACITY = 1 << 30*/
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;
}

HashMap 的容量為什么是2的 n 次冪
HashMap 的默認初始容量是16，而每次擴容是擴容為原來的2倍。這里的16和2倍就保證了 HashMap 的容量是2的 n 次冪，那么這樣設計的原因是什么呢？原因一：與運算高效
與運算 & ，基于二進制數值，同時為1結果為1，否則就是0。如1&1=1,1&0=0,0&0=0。使用與運算的原因就是對于計算機來說，與運算十分高效。原因二：有利于元素充分散列，減少 Hash 碰撞
在給 HashMap 添加元素的 putVal 函數中，有這樣一段代碼：

// n為容量，hash為該元素的hash值
if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);

它會在添加元素時，通過 i = (n - 1) & hash 計算該元素在 HashMap 中的位置。
當 HashMap 的容量為 2 的 n 次冪時，他的二進制值是100000……（n個0），所以n-1的值就是011111……（n個1），這樣的話 (n - 1) & hash 的值才能夠充分散列。
舉個例子，假設容量為16，現在有哈希值為1111，1110，1011，1001四種將被添加，它們與n-1(15的二進制=01111)的哈希值分別為1111、1110、1110、1011，都不相同。而假設容量不為2的n次冪，假設為10，與上述四個哈希值進行與運算的結果分別是：0101、0100、0001、0001。可以看到后兩個值發生了碰撞。所以 HashMap 的容量設置為 2 的 n 次冪有利于元素的充分散列。HashMap初始容量為什么是2的n次冪及擴容為什么是2倍的形式HashMap 是如何導致死循環的
HashMap 會導致死循環是在 jdk1.7 中，由于擴容時的操作是使用頭插法，在多線程的環境下可能產生循環鏈表，由此導致了死循環。在 jdk1.8 中改為使用尾插法，避免了該死循環的情況。

來源：https://www.tuicool.com/articles/ieQVzqi

以下篇章來自博客【占小狼】
原文鏈接：https://blog.csdn.net/maohoo/article/details/81531925

問題
如果是在單線程下使用HashMap，自然是沒有問題的，如果后期由于代碼優化，這段邏輯引入了多線程并發執行，在一個未知的時間點，會發現CPU占用100%，居高不下，通過查看堆棧，你會驚訝的發現，線程都Hang在hashMap的get()方法上，服務重啟之后，問題消失，過段時間可能又復現了。
這是為什么？原因分析
在了解來龍去脈之前，我們先看看HashMap的數據結構。
在內部，HashMap使用一個Entry數組保存key、value數據，當一對key、value被加入時，會通過一個hash算法得到數組的下標index，算法很簡單，根據key的hash值，對數組的大小取模 hash & (length-1)，并把結果插入數組該位置，如果該位置上已經有元素了，就說明存在hash沖突，這樣會在index位置生成鏈表。
如果存在hash沖突，最慘的情況，就是所有元素都定位到同一個位置，形成一個長長的鏈表，這樣get一個值時，最壞情況需要遍歷所有節點，性能變成了O(n)，所以元素的hash值算法和HashMap的初始化大小很重要。
當插入一個新的節點時，如果不存在相同的key，則會判斷當前內部元素是否已經達到閾值（默認是數組大小的0.75），如果已經達到閾值，會對數組進行擴容，也會對鏈表中的元素進行rehash。源碼分析
HashMap的put方法實現：
1、判斷key是否已經存在

public V put(K key, V value) {if (table == EMPTY_TABLE) {inflateTable(threshold);}if (key == null)return putForNullKey(value);int hash = hash(key);int i = indexFor(hash, table.length);// 如果key已經存在，則替換value，并返回舊值for (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;addEntry(hash, key, value, i);return null;
}
1234567891011121314151617181920212223

2、檢查容量是否達到閾值threshold

void addEntry(int hash, K key, V value, int bucketIndex) {if ((size >= threshold) && (null != table[bucketIndex])) {resize(2 * table.length);hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex);
}
123456789

如果元素個數已經達到閾值，則擴容，并把原來的元素移動過去。
3、擴容實現

void resize(int newCapacity) {Entry[] oldTable = table;int oldCapacity = oldTable.length;if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}Entry[] newTable = new Entry[newCapacity];transfer(newTable, initHashSeedAsNeeded(newCapacity));table = newTable;threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
12345678910111213

這里會新建一個更大的數組，并通過transfer方法，移動元素。

void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) {while(null != e) {Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}int i = indexFor(e.hash, newCapacity);e.next = newTable[i];newTable[i] = e;e = next;}}
}
123456789101112131415

移動的邏輯也很清晰，遍歷原來table中每個位置的鏈表，并對每個元素進行重新hash，在新的newTable找到歸宿，并插入。
案例分析
假設HashMap初始化大小為4，插入個3節點，不巧的是，這3個節點都hash到同一個位置，如果按照默認的負載因子的話，插入第3個節點就會擴容，為了驗證效果，假設負載因子是1.

void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) {while(null != e) {Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}int i = indexFor(e.hash, newCapacity);e.next = newTable[i];newTable[i] = e;e = next;}}
}
123456789101112131415

以上是節點移動的相關邏輯。

插入第4個節點時，發生rehash，假設現在有兩個線程同時進行，線程1和線程2，兩個線程都會新建新的數組

假設線程2 在執行到Entry < K,V > next = e.next;之后，cpu時間片用完了，這時變量e指向節點a，變量next指向節點b。線程1繼續執行，很不巧，a、b、c節點rehash之后又是在同一個位置7，開始移動節點第一步，移動節點a

第二步，移動節點b

注意，這里的順序是反過來的，繼續移動節點c

這個時候線程1 的時間片用完，內部的table還沒有設置成新的newTable，線程2 開始執行，這時內部的引用關系如下：

這時，在線程2 中，變量e指向節點a，變量next指向節點b，開始執行循環體的剩余邏輯

Entry<K,V> next = e.next;int i = indexFor(e.hash, newCapacity);e.next = newTable[i];newTable[i] = e;e = next;
12345

執行之后的引用關系如下圖

執行后，變量e指向節點b，因為e不是null，則繼續執行循環體，執行后的引用關系

變量e又重新指回節點a，只能繼續執行循環體，這里仔細分析下：

1、執行完Entry < K,V > next = e.next;，目前節點a沒有next，所以變量next指向null；

2、e.next = newTable[i]; 其中 newTable[i] 指向節點b，那就是把a的next指向了節點b，這樣a和b就相互引用了，形成了一個環；

3、newTable[i] = e 把節點a放到了數組i位置；

4、e = next; 把變量e賦值為null，因為第一步中變量next就是指向null；
所以最終的引用關系是這樣的：

節點a和b互相引用，形成了一個環，當在數組該位置get尋找對應的key時，就發生了死循環。
另外，如果線程2把newTable設置成到內部的table，節點c的數據就丟了，看來還有數據遺失的問題。
總結所以在并發的情況，發生擴容時，可能會產生循環鏈表，在執行get的時候，會觸發死循環，引起CPU的100%問題，所以一定要避免在并發環境下使用HashMap。
曾經有人把這個問題報給了Sun，不過Sun不認為這是一個bug，因為在HashMap本來就不支持多線程使用，要并發就用ConcurrentHashmap。