HashMap為何從頭插入改為尾插入

摘要： 微信公眾號：如有問題或建議，請在下方留言; 最近更新：2018-09-21 前言 前面對於HashMap在jdk1.8中元素插入的實現原理，進行了詳細分析，具體請看：HashMap之元素插入。文章釋出之後，有一位朋友問了這麼一個問題："jdk1.7中採用頭插入，...

微信公眾號：如有問題或建議，請在下方留言;

最近更新：2018-09-21

前言

前面對於HashMap在jdk1.8中元素插入的實現原理，進行了詳細分析，具體請看：HashMap之元素插入。文章釋出之後，有一位朋友問了這麼一個問題："jdk1.7中採用頭插入，為什麼jdk1.8中改成了尾插入？"。有人說這就是java大神隨性而為，沒什麼特殊的用處。當時因為沒仔細看過1.7的原始碼，所以不好解答。現在特此寫了本文，來對該問題進行詳細的分析。

靜態常量

原始碼：

 1/**
 2 * 預設初始大小，值為16，要求必須為2的冪
 3 */
 4static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 5
 6/**
 7 * 最大容量，必須不大於2^30
 8 */
 9static final int MAXIMUM_CAPACITY = 1 << 30;
10
11/**
12 * 預設載入因子，值為0.75
13 */
14static final float DEFAULT_LOAD_FACTOR = 0.75f;
15
16/**
17 * HashMap的空陣列
18 */
19static final Entry<?,?>[] EMPTY_TABLE = {};
20
21/**
22 * 可選的預設雜湊閾值
23 */
24static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
複製程式碼

注意： jdk1.7中HashMap預設採用陣列+單鏈表方式儲存元素，當元素出現雜湊衝突時，會儲存到該位置的單鏈表中。這和1.8不同，除了陣列和單鏈表外，當單鏈表中元素個數超過8個時，會進而轉化為紅黑樹儲存，巧妙地將遍歷元素時時間複雜度從O(n)降低到了O(logn)）。

建構函式

1、無參建構函式：

1public HashMap() {
2this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
3}
複製程式碼

2、帶參建構函式，指定初始容量：

1public HashMap(int initialCapacity) {
2this(initialCapacity, DEFAULT_LOAD_FACTOR);
3}
複製程式碼

3、帶參建構函式，指定初始容量和載入因子：

 1public HashMap(int initialCapacity, float loadFactor) {
 2if (initialCapacity < 0)
 3throw new IllegalArgumentException("Illegal initial capacity: " +
 4initialCapacity);
 5if (initialCapacity > MAXIMUM_CAPACITY)
 6initialCapacity = MAXIMUM_CAPACITY;
 7if (loadFactor <= 0 || Float.isNaN(loadFactor))
 8throw new IllegalArgumentException("Illegal load factor: " +
 9loadFactor);
10
11this.loadFactor = loadFactor;
12threshold = initialCapacity;//和jdk8不同，初始閾值就是初始容量，並沒做2次冪處理
13init();
14}
複製程式碼

4、帶參建構函式，指定Map集合：

 1public void putAll(Map<? extends K, ? extends V> m) {
 2int numKeysToBeAdded = m.size();
 3if (numKeysToBeAdded == 0)
 4return;
 5
 6if (table == EMPTY_TABLE) {
 7inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
 8}
 9
10if (numKeysToBeAdded > threshold) {
11int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
12if (targetCapacity > MAXIMUM_CAPACITY)
13targetCapacity = MAXIMUM_CAPACITY;
14int newCapacity = table.length;
15while (newCapacity < targetCapacity)
16newCapacity <<= 1;
17if (newCapacity > table.length)
18resize(newCapacity);
19}
20
21for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
22put(e.getKey(), e.getValue());
23}
複製程式碼

說明： 執行建構函式時，儲存元素的陣列並不會進行初始化，而是在第一次放入元素的時候，才會進行初始化操作。建立HashMap物件時，僅僅計算初始容量和新增閾值。

新增元素

1、原始碼：

 1public V put(K key, V value) {
 2if (table == EMPTY_TABLE) {
 3inflateTable(threshold);//初始化陣列
 4}
 5if (key == null)//key為null，做key為null的新增
 6return putForNullKey(value);
 7int hash = hash(key);//計算鍵值的雜湊
 8int i = indexFor(hash, table.length);//根據雜湊值獲取在陣列中的索引位置
 9for (Entry<K,V> e = table[i]; e != null; e = e.next) {//遍歷索引位置的單鏈表，判斷是否存在指定key
10Object k;
11if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//key已存在則更新value值
12V oldValue = e.value;
13e.value = value;
14e.recordAccess(this);
15return oldValue;
16}
17}
18
19modCount++;
20addEntry(hash, key, value, i);//key不存在，則插入元素
21return null;
22}
23
24private V putForNullKey(V value) {
25for (Entry<K,V> e = table[0]; e != null; e = e.next) {
26if (e.key == null) {//key為null已存在，更新value值
27V oldValue = e.value;
28e.value = value;
29e.recordAccess(this);
30return oldValue;
31}
32}
33modCount++;
34addEntry(0, null, value, 0);//不存在則新增，key為null的雜湊值為0
35return null;
36}
37
38void addEntry(int hash, K key, V value, int bucketIndex) {
39if ((size >= threshold) && (null != table[bucketIndex])) {//插入位置存在元素，並且元素個數大於等於新增閾值
40resize(2 * table.length);//進行2倍擴容
41hash = (null != key) ? hash(key) : 0;//擴容中可能會調整雜湊種子的值，所以重新計算雜湊值
42bucketIndex = indexFor(hash, table.length);//重新計算在擴容後陣列中的位置
43}
44
45createEntry(hash, key, value, bucketIndex);//新增元素
46}
47
48//計算物件雜湊值
49final int hash(Object k) {
50int h = hashSeed;
51if (0 != h && k instanceof String) {//String採用單獨的演算法
52return sun.misc.Hashing.stringHash32((String) k);
53}
54
55h ^= k.hashCode();//利用雜湊種子異或雜湊值，為了進行優化，增加隨機性
56
57h ^= (h >>> 20) ^ (h >>> 12);
58return h ^ (h >>> 7) ^ (h >>> 4);//這裡的移位異或操作屬於擾亂函式，都是為了增加雜湊值的隨機性，降低雜湊衝突的概率
59}
60
61void createEntry(int hash, K key, V value, int bucketIndex) {
62Entry<K,V> e = table[bucketIndex];
63table[bucketIndex] = new Entry<>(hash, key, value, e);//新增元素插入到陣列索引位置，原來元素作為其後繼節點，即採用頭插入方法
64size++;
65}
複製程式碼

2、流程圖：

3、示例：

初始化陣列

1、原始碼：

 1//根據指定的大小，初始化陣列
 2private void inflateTable(int toSize) {
 3// Find a power of 2 >= toSize
 4int capacity = roundUpToPowerOf2(toSize);
 5
 6threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//根據容量和載入因子計算閾值，最大為2^30+1
 7table = new Entry[capacity];//建立指定容量大小的陣列
 8initHashSeedAsNeeded(capacity);
 9}
10
11//獲取大於指定值的最小2次冪，最大為2^30
12private static int roundUpToPowerOf2(int number) {
13// assert number >= 0 : "number must be non-negative";
14return number >= MAXIMUM_CAPACITY
15? MAXIMUM_CAPACITY
16: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
17}
複製程式碼

2、說明：

關於雜湊種子，是為了優化雜湊函式，讓其值更加隨機，從而降低雜湊衝突的概率。通過HashMap中私有靜態類Holder，在JVM啟動的時候，指定-Djdk.map.althashing.threshold=值，來設定可選的雜湊閾值，從而在initHashSeedAsNeeded中決定是否需要調整雜湊種子。

 1private static class Holder {
 2
 3/**
 4* Table capacity above which to switch to use alternative hashing.
 5*/
 6static final int ALTERNATIVE_HASHING_THRESHOLD;
 7
 8static {
 9String altThreshold = java.security.AccessController.doPrivileged(
10new sun.security.action.GetPropertyAction(
11"jdk.map.althashing.threshold"));//通過-Djdk.map.althashing.threshold=值指定可選雜湊閾值
12
13int threshold;
14try {
15threshold = (null != altThreshold)
16? Integer.parseInt(altThreshold)
17: ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;//預設為Integer.MAX_VALUE
18
19// disable alternative hashing if -1
20if (threshold == -1) {
21threshold = Integer.MAX_VALUE;
22}
23
24if (threshold < 0) {
25throw new IllegalArgumentException("value must be positive integer.");
26}
27} catch(IllegalArgumentException failed) {
28throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
29}
30
31ALTERNATIVE_HASHING_THRESHOLD = threshold;//指定可選的雜湊閾值，在initHashSeedAsNeeded作為是否初始化雜湊種子的判定條件
32}
33}
34
35//根據容量決定是否需要初始化雜湊種子
36final boolean initHashSeedAsNeeded(int capacity) {
37boolean currentAltHashing = hashSeed != 0;//雜湊種子預設為0
38boolean useAltHashing = sun.misc.VM.isBooted() &&
39(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);//如果容量大於可選的雜湊閾值，則需要初始化雜湊種子
40boolean switching = currentAltHashing ^ useAltHashing;
41if (switching) {
42hashSeed = useAltHashing
43? sun.misc.Hashing.randomHashSeed(this)//生成一個隨機的雜湊種子
44: 0;
45}
46return switching;
47}
複製程式碼

擴容

1、原始碼：

 1//按照指定容量進行陣列擴容
 2void resize(int newCapacity) {
 3Entry[] oldTable = table;
 4int oldCapacity = oldTable.length;
 5if (oldCapacity == MAXIMUM_CAPACITY) {//原有容量達到最大值，則不再擴容
 6threshold = Integer.MAX_VALUE;
 7return;
 8}
 9
10Entry[] newTable = new Entry[newCapacity];
11transfer(newTable, initHashSeedAsNeeded(newCapacity));
12table = newTable;
13threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//按照擴容後容量重新計算閾值
14}
15
16//將元素重新分配到新陣列中
17void transfer(Entry[] newTable, boolean rehash) {
18int newCapacity = newTable.length;
19for (Entry<K,V> e : table) {//遍歷原陣列
20while(null != e) {
21Entry<K,V> next = e.next;
22if (rehash) {//擴容後陣列需要重新計算雜湊
23e.hash = null == e.key ? 0 : hash(e.key);
24}
25int i = indexFor(e.hash, newCapacity);//計算新陣列中的位置
26e.next = newTable[i];//採用頭插入法，新增到新陣列中
27newTable[i] = e;
28e = next;
29}
30}
31}
複製程式碼

2、問題：

上述擴容程式碼，在併發情況下執行，就會出現常說的連結串列成環的問題，下面通過示例來分析：

2.1、初始狀態：

執行緒1插入18，執行緒2插入26。此時執行緒1發現size為6，進行擴容。執行緒2發現size為6，也進行擴容。

2.2、 執行緒1執行：

執行緒1首先獲取到CPU執行權，執行transfer()中程式碼：

 1for (Entry<K,V> e : table) {
 2while(null != e) {
 3Entry<K,V> next = e.next;//執行緒1執行到此行程式碼，e為10，next為2。此時CPU排程執行緒2執行。
 4if (rehash) {
 5e.hash = null == e.key ? 0 : hash(e.key);
 6}
 7int i = indexFor(e.hash, newCapacity);
 8e.next = newTable[i];
 9newTable[i] = e;
10e = next;
11}
12}
複製程式碼

2.3、 執行緒2執行：

執行緒2此時獲取到CPU執行權，執行transfer()中程式碼：

 1for (Entry<K,V> e : table) {
 2while(null != e) {
 3Entry<K,V> next = e.next;
 4if (rehash) {
 5e.hash = null == e.key ? 0 : hash(e.key);
 6}
 7int i = indexFor(e.hash, newCapacity);
 8e.next = newTable[i];
 9newTable[i] = e;
10e = next;
11}
12}
複製程式碼

第一次遍歷：e為10，next為2，rehash為false，i為2，newTable[2]為null，10.next為null，newTable[2]為10，e為2。

第二次遍歷：e為2，next為null，rehash為false，i為2，newTable[2]為10，2.next為10，newTable[2]為2，e為null。

第三次遍歷：e為null，退出迴圈。

2.4、 執行緒1執行：

 1for (Entry<K,V> e : table) {
 2while(null != e) {
 3Entry<K,V> next = e.next;//執行緒1執行到此行程式碼，e為10，next為2。CPU排程執行緒1繼續執行。
 4if (rehash) {
 5e.hash = null == e.key ? 0 : hash(e.key);
 6}
 7int i = indexFor(e.hash, newCapacity);
 8e.next = newTable[i];
 9newTable[i] = e;
10e = next;
11}
12}
複製程式碼

e為10，next為2，rehash為false，i為2，newTable[2]為2，10.next為2，newTable[2]為10，e為2。

第二次遍歷：e為2，next為null，rehash為false，i為2，newTable[2]為10，2.next為10，newTable[2]為2，e為10。此時，連結串列已經成環，進入死迴圈！！！

3、說明：

由上例可知，HashMap在jdk1.7中採用頭插入法，在擴容時會改變連結串列中元素原本的順序，以至於在併發場景下導致連結串列成環的問題。而在jdk1.8中採用尾插入法，在擴容時會保持連結串列元素原本的順序，就不會出現連結串列成環的問題了。

總結

通過上述的分析，在這裡總結下HashMap在1.7和1.8之間的變化：

• 1.7採用陣列+單鏈表，1.8在單鏈表超過一定長度後改成紅黑樹儲存
• 1.7擴容時需要重新計算雜湊值和索引位置，1.8並不重新計算雜湊值，巧妙地採用和擴容後容量進行&操作來計算新的索引位置。
• 1.7插入元素到單鏈表中採用頭插入法，1.8採用的是尾插入法。

通過對HashMap在jdk1.7和1.8中原始碼的學習，深深地體會到一個道理：一切設計都有著它背後的原因。作為學習者，我們需要不斷的問自己，為什麼這麼設計，這麼設計有什麼好處。本著這樣的學習態度，我想不久的將來，你就會變成他。

文章的最後，感謝大家的支援，歡迎掃描下方二維碼，進行關注。如有任何疑問，歡迎大家留言。