序言

在後端的日常開發工作中，

以前曾有詳細瞭解過HashMap的實現原理，看過源碼（JDK7版本）。但隨著jdk版本的飛速迭代（現在都到JDK13了，但新特性還從沒用過。。），主流的jdk使用版本也終於從JDK7挪到了JDK8。

由於JDK的向前兼容，在JDK8的使用過程中也沒發現HashMap有什麼特別之處，特性並無變化（依然線程不安全）。但最近的一次好奇心驅使，從IDE中點進去看了下HashMap的put()方法，有點兒懵逼，怎麼跟我記憶中的不太一樣？從JDK7到JDK8，HashMap也做了升級麼？升級了什麼哪些內容？

藉著這股好奇心，把JDK7和JDK8的源碼都翻了翻，對兩者的實現原理做一下對比，JDK版本都在半年左右一次的速度推陳出新，我們的認知當然也要跟上，不斷學習，站在浪潮之巔，不然就要被這滾滾的信息泥石流給裹挾淹沒了。

先展示下Map家族的關係層級，有助於我們更好的理解後面的內容。

HashMap的基本知識點介紹就不多囉嗦了，直奔主題，看JDK7和JDK8的功能實現吧。

一、JDK7中的HashMap底層實現

1.1 基礎知識

不管是1.7，還是1.8，HashMap的實現框架都是哈希表 + 鏈表的組合方式。結構圖如下：

平常使用最多的就是put()、get()操作，想要了解底層實現，最直接的就是從put()/get()方法看起。不過在具體看源碼前，我們先關注幾個域變量，打打基礎，如下：

上圖中，已對各個變量做了簡單的解釋。
再多說一下，最後一個變量

還需要說明的是，上面的域變量中存在一個等式：

threshold = table.length * loadFactor;

當執行put()操作放入一個新的值時，如果map中已經存在對應的key，則作替換即可，若不存在，則會首先判斷size>=threshold是否成立，這是決定哈希table是否擴容的重要因素。

就使用層面來說，用的最多的莫過於put()方法、get()方法。想要詳細瞭解運作原理，那就先從這兩個方法看起吧，這兩個方法弄明白了，也就基本能理清HashMap的實現原理了。

1.2 put()方法

當了解了以上的變量和用途後，接下來看下

如上面的截圖代碼所示，整個put方法的處理過程，可拆分為四部分：

• part1：特殊key值處理，key為null；
• part2：計算table中目標bucket的下標；
• part3：指定目標bucket，遍歷Entry結點鏈表，若找到key相同的Entry結點，則做替換；
• part4：若未找到目標Entry結點，則新增一個Entry結點。

不知大家有沒有發現，上面截圖中的put()方法是有返回值的，場景區分如下：

• 場景1：若執行put操作前，key已經存在，那麼在執行put操作時，會使用本次的新value值來覆蓋前一次的舊value值，返回的就是舊value值；
• 場景2：若key不存在，則返回null值。

下面對put方法的各部分做詳細的拆解分析。

1.2.1 特殊key值處理

特殊key值，指的就是key為null。
先說結論：
a) HashMap中，是允許key、value都為null的，且key為null只存一份，多次存儲會將舊value值覆蓋；

上代碼：

private V putForNullKey(V value) {
 for (Entry e = table[0]; e != null; e = e.next) {
 if (e.key == null) {
 V oldValue = e.value;
 e.value = value;
 e.recordAccess(this);
 return oldValue;
 }
 }
 modCount++;
 addEntry(0, null, value, 0);
 return null;
}


/**
 * Adds a new entry with the specified key, value and hash code to
 * the specified bucket. It is the responsibility of this
 * method to resize the table if appropriate.
 *
 * Subclass overrides this to alter the behavior of put method.
 */
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);
} 



/**
 * Like addEntry except that this version is used when creating entries
 * as part of Map construction or "pseudo-construction" (cloning,
 * deserialization). This version needn't worry about resizing the table.
 *
 * Subclass overrides this to alter the behavior of HashMap(Map),
 * clone, and readObject.
 */
void createEntry(int hash, K key, V value, int bucketIndex) {
 Entry e = table[bucketIndex];
 table[bucketIndex] = new Entry<>(hash, key, value, e);
 size++;
}

putForNullKey()方法中的代碼較為簡單：首先選擇table[0]位置的鏈表，然後對鏈表做遍歷操作，如果有結點的key為null，則將新value值替換掉舊value值，返回舊value值，如果未找到，則新增一個key為null的Entry結點。

重點我們看下第二個方法addEntry()。
這是一個通用方法：

給定hash、key、value、bucket下​標，新增一個Entry結點，另外還擔負了擴容職責。如果哈希表中存放的k-v對數量超過了當前閾值(threshold = table.length * loadFactor)，且當前的bucket下標有鏈表存在，那麼就做擴容處理（resize）。擴容後，重新計算hash，最終得到新的bucket下標，然後使用頭插法新增結點。

1.2.2 擴容

上一節有提及，當k-v對的容量超出一定限度後，需要對哈希table做擴容操作。那麼問題來了，怎麼擴容的？
下面看下源代碼：

有兩個核心點：
a) 擴容後大小是擴容前的2倍；

oldCapacity=table.length;
newCapacity = 2 * oldCapacity;

b) 數據搬遷，從舊table遷到擴容後的新table。
為避免碰撞過多，先決策是否需要對每個Entry鏈表結點重新hash，然後根據hash值計算得到bucket下標，然後使用頭插法做結點遷移。

1.2.3 如何計算bucket下標？

① hash值的計算

首先得有key的hash值，就是一個整數，int類型，其計算方式使用了一種可儘量減少碰撞的算式（高位運算），具體原理不再展開，只要知道一點就行：使用key的hashCode作為算式的輸入，得到了hash值。

從以上知識點，我們可以得到一個推論：
對於兩個對象，若其hashCode相同，那麼兩個對象的hash值就一定相同。

這裡還牽涉到另外一個知識點。對於HashMap中key的類型，必須滿足以下的條件：
若兩個對象邏輯相等，那麼他們的hashCode一定相等，反之卻不一定成立。

邏輯相等的含義就比較寬泛了，我們可以將邏輯的相等定義為兩個對象的內存地址相同，也可以定義為對象的某個域值相等，自定義兩個對象的邏輯相等，可通過重寫Object類的equals()方法來實現。
比如String類，請看以下代碼：

String str1 = "abc";
String str2 = new String("abc");
System.out.println(str1 == str2); // false，兩個對象的內存地址並不同
System.out.println(str1.equals(str2)); // true 兩個對象的域值相同，都存儲了 abc 這三個字符

對於上面代碼中的str1、str2兩個對象，雖然它們的內存地址不同，但根據String類中對Object類的equals()方法的重寫(@override)，兩個對象的域變量（即char數組）都存儲了'a'、'b'、'c'三個字符，因此邏輯上是相等的。既然str1

System.out.println(str1.hashCode() == str2.hashCode());


---輸出---
true

從而我們就可以知道，在同一個HashMap對象中，會有如下結果：

String str1 = "abc";
String str2 = new String("abc");
Map<string> testMap = new HashMap<>();
testMap.put(str1, 12);
testMap.put(str2, 13);


String str3 = new StringBuilder("ab").append("c").toString();
System.out.println(testMap.get(str3));


---輸出---
13/<string>

另外，我們也可以反過來想一下。

假設HashMap的key不滿足上面提到的條件，即：兩個對象相等的情況下，他們的hashCode可能不一致。那麼，這會帶來什麼後果呢？以上面示例代碼中的str1、str2為例，若它們的hashCode不相等，那麼對應的hash也就可能不相等（注意：這裡是

因此，再重新一遍，HashMap的key所對應的類型，一定要滿足如下條件：
若兩個對象邏輯相等，那麼他們的hashCode一定相等，反之卻不一定成立。

② 取模的邏輯

前面我們分析了hash值的計算，接下來就可以引出bucket下標的計算：

/**
 * Returns index for hash code h.
 */
static int indexFor(int h, int length) {
 return h & (length-1); 

}

計算相當簡潔：將table的容量與hash值做“與”運算，得到哈希table的bucket下標。

③ 拓展

這種通俗的不能再通俗的計算大家都能看懂，但為何要這樣做呢？背後的思考是什麼？在看到下面的解釋前，大家可以先思考下~

在文檔開頭，給出了HashMap類中的各個域變量。其中，哈希table的初始大小默認設置為16，為2的次冪數。後面在擴容時，都是以2的倍數來擴容。為什麼非要將哈希table的大小控制為2的次冪數？

原因1：降低發生碰撞的概率，使散列更均勻。根據key的hash值計算bucket的下標位置時，使用“與”運算公式：h & (length-1)，當哈希表長度為2的次冪時，等同於使用表長度對hash值取模（不信大家可以自己演算一下），散列更均勻；
原因2：表的長度為2的次冪，那麼(length-1)的二進制最後一位一定是1，在對hash值做“與”運算時，最後一位就可能為1，也可能為0，換句話說，取模的結果既有偶數，又有奇數。設想若(length-1)為偶數，那麼“與”運算後的值只能是0，奇數下標的bucket就永遠散列不到，會浪費一半的空間。

1.2.4 在目標bucket中遍歷Entry結點

先把這部分代碼拎出來：

...
int i = indexFor(hash, table.length);
for (Entry 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;
 }
}
...

通過hash值計算出下標，找到對應的目標bucket，然後對鏈表做遍歷操作，逐個比較，如下：

注意這裡的查找條件：e.hash == hash && ((k = e.key) == key || key.equals(k))
結點的key與目標key的相等，要麼內存地址相等，要麼邏輯上相等，兩者有一個滿足即可。

1.3 get()方法

相比於put()方法，get()方法的實現就相對簡單多了。主要分為兩步，先是通過key的hash值計算目標bucket的下標，然後遍歷對應bucket上的鏈表，逐個對比，得到結果。

public V get(Object key) {
 if (key == null)
 return getForNullKey();
 Entry entry = getEntry(key);


 return null == entry ? null : entry.getValue();
}


/**
 * Returns the entry associated with the specified key in the
 * HashMap. Returns null if the HashMap contains no mapping
 * for the key.
 */
final Entry getEntry(Object key) {
 int hash = (key == null) ? 0 : hash(key);
 for (Entry e = table[indexFor(hash, table.length)];
 e != null; 

 e = e.next) {
 Object k;
 if (e.hash == hash &&
 ((k = e.key) == key || (key != null && key.equals(k))))
 return e;
 }
 return null;
}

1.4 Map中的迭代器Iterator

1.4.1 Map遍歷的幾種方式

先問個問題，你能想到幾種遍歷Map的方式？

方式1：Iterator迭代器

Iterator<entry>> iterator = testMap.entrySet().iterator();
while (iterator.hasNext()) {
 Entry<string> next = iterator.next();
 System.out.println(next.getKey() + ":" + next.getValue());
}/<string>/<entry>

逐個獲取哈希table中的每個bucket中的每個Entry結點，後面會詳細介紹。

方式2：最常見的使用方式，可同時得到key、value值

// 方式一
for (Map.Entry<string> entry : testMap.entrySet()) {
 System.out.println(entry.getKey() + ":" + entry.getValue());
}/<string> 

這種方式是一個語法糖，我們可通過反編譯命令javap，或通過IDE來查下編譯之後的語句：

Iterator var2 = testMap.entrySet().iterator();
while(var2.hasNext()) {
 Entry<string> entry = (Entry)var2.next();
 System.out.println((String)entry.getKey() + ":" + entry.getValue());
}/<string>

其底層還是使用的是Iterator功能。

方式3：使用foreach方式（JDK1.8才有）

testMap.forEach((key, value) -> {
 System.out.println(key + ":" + value);
});

這是一種Lambda表達式。foreach也是一個語法糖，其內部是使用了方式二的處理方式，Map的foreach方法實現如下：

方式4：通過key的set集合遍歷

Iterator<string> keyIterator = testMap.keySet().iterator();
while (keyIterator.hasNext()) {
 String key = keyIterator.next();
 System.out.println(key + ":" + testMap.get(key));
}/<string>

這種也是Iterator的方式，不過是通過Set類的iterator方式。

相比方式1，這種方式在獲取value時，還需要再次通過testMap.get()的方式，性能相比方式1要降低很多。但兩者有各自的使用場景，若在Map的遍歷中僅使用key，則方式4較為適合，若需用到value，推薦使用方式1。

從前面的方式1和方式2可知，方式4還有如下的變體（語法糖的方式）：

for (String key : testMap.keySet()) {
 System.out.println(key + ":" + testMap.get(key));
}

綜合以上，在遍歷Map時，從性能方面考慮，若需同時使用key和value，推薦使用

另外，使用方式1時，還可以做remove操作，這個下面會講到。

1.4.2 Iterator的實現原理

先看一張類/接口的繼承關係圖：

Iterator為一個頂層接口，只提供了三個基礎方法聲明：

public interface Iterator {
 
 boolean hasNext();
 
 E next();
 
 default void remove() {
 throw new UnsupportedOperationException("remove");
 }
}

這也是我們使用Iterator時繞不開的三個方法。
在HashMap中，首先是新增了一個內部抽象類HashIterator，如下：

我們以Entry結點的遍歷為例（map的key、value的Iterator遍歷方式都類似）：

Iterator<entry>> iterator = testMap.entrySet().iterator();
while (iterator.hasNext()) {
 Entry<string> next = iterator.next();
 System.out.println(next.getKey() + ":" + next.getValue());
}/<string>/<entry>

首先，第一行代碼，找到Iterator接口的具體實現類EntryIterator：

private final class EntryIterator extends HashIterator<map.entry>> {
 public Map.Entry next() {
 return nextEntry();
 }
}/<map.entry>

非常簡潔有木有？？？就只有一個next()方法，其正是對Iterator接口的next()方法的實現。方法內部也只有一行，指向了父類的nextEntry()方法，即上面截圖中的HashIterator類中的nextEntry()方法。

HashMap中的Iterator實現原理也不過如此，就是這麼樸實無華，是不是都想動手自己擼一個HashMap的實現了？嗯，你可以的！！！

1.5 fail-fast策略

和fail-fast經常一起出現的還有一個異常類ConcurrentModificationException，接下來我們聊下這兩者是什麼關係，以及為什麼搞這麼個策略出來。

什麼是fail-fast？我們可以稱它為"快速失效策略"，下面是Wikipedia中的解釋：

In systems design, a fail-fast system is one which immediately reports at its interface any condition that is likely to indicate a failure. Fail-fast systems are usually designed to stop normal operation rather than attempt to continue a possibly flawed process.
Such designs often check the system's state at several points in an operation, so any failures can be detected early. The responsibility of a fail-fast module is detecting errors, then letting the next-highest level of the system handle them.

大白話翻譯過來，就是在系統設計中，當遇到可能會誘導失敗的條件時立即上報錯誤，快速失效系統往往被設計在立即終止正常操作過程，而不是嘗試去繼續一個可能會存在錯誤的過程。
再簡潔點說，就是儘可能早的發現問題，立即終止當前執行過程，由更高層級的系統來做處理。

在HashMap中，我們前面提到的modCount域變量，就是用於實現hashMap中的fail-fast。出現這種情況，往往是在非同步的多線程併發操作。

舉個栗子：

public static void main(String[] args) {
 Map<string> testMap = new HashMap<>();
 testMap.put("s1", 11);
 testMap.put("s2", 22);
 testMap.put("s3", 33);


 for (Map.Entry<string> entry : testMap.entrySet()) {
 String key = entry.getKey();
 if ("s1".equals(key)) {
 testMap.remove(key);
 }
 }
}


---- output ---
Exception in thread "main" java.util.ConcurrentModificationException
 at java.util.HashMap$HashIterator.nextNode(HashMap.java:1437)
 at java.util.HashMap$EntryIterator.next(HashMap.java:1471)
 at java.util.HashMap$EntryIterator.next(HashMap.java:1469)
 .../<string>/<string>

正確的刪除Map元素的姿勢：只有一個，Iteator的remove()

// 方式三
Iterator<entry>> iterator = testMap.entrySet().iterator();
while (iterator.hasNext()) {
 Entry<string> next = iterator.next();
 System.out.println(next.getKey() + ":" + next.getValue());
 if (next.getKey().equals("s2")) {
 iterator.remove();
 }
}/<string>/<entry>

但也要注意一點，能安全刪除，並不代表就是多線程安全的，在多線程併發執行時，若都執行上面的操作，因未設置為同步方法，也可能導致modCount與expectedModCount不一致，從而拋異常ConcurrentModificationException。
線程不安全的體現和規避方式，後續章節會詳細提及。

二、JDK8中的HashMap底層實現

前面我們已經詳細剖析了HashMap在JDK7中的實現，不知大家有沒有發現其中可以優化的地方？比如哈希表中因為hash碰撞而產生的鏈表結構，如果數據量很大，那麼產生碰撞的幾率很增加，這帶來的後果就是鏈表長度也一直在增加，對於查詢來說，性能會越來越低。如何提升查詢性能，成了JDK8中的HashMap要解決的問題。

因此，相比於JDK7，HashMap在JDK8中做鏈表結構做了優化（但仍然線程不安全），在一定條件下將鏈表轉為紅黑樹，提升查詢效率。

JDK8中的HashMap其底層存儲結構如下：

相比於JDK7，JDK8中的HashMap會將較長的鏈表轉為紅黑樹，這也是與JDK7的核心差異。下面先看下put()方法的實現。

2.1 put()操作

在進一步分析put()操作前，先說明一下：除了底層存儲結構有調整，鏈表結點的定義也由

先上源代碼：

是不是很長很複雜？其實不難，只要記住上面的底層存儲結構圖，代碼就很容易看懂。還是一樣的存儲套路，先根據key確定在哈希table中的下標，找到對應的bucket，遍歷鏈表（或紅黑樹），做插入操作。在JDK7中，新增結點是使用

為方便理解，將上面的代碼轉為了下面的流程圖：

步驟①：若哈希table為null，或長度為0，則做一次擴容操作；
步驟②

紅黑樹的轉換操作如下：

/**
 * Replaces all linked nodes in bin at index for given hash unless
 * table is too small, in which case resizes instead.
 */
final void treeifyBin(Node 
[] tab, int hash) {
 int n, index; Node e;
 // 若表為空，或表長度小於MIN_TREEIFY_CAPACITY，也不做轉換，直接做擴容處理。
 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
 resize();
 else if ((e = tab[index = (n - 1) & hash]) != null) {
 TreeNode hd = null, tl = null;
 do {
 TreeNode 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);
 }
}

2.2 擴容操作

什麼場景下會觸發擴容？
場景1：哈希table為null或長度為0；
場景2：Map中存儲的k-v對數量超過了閾值threshold；
場景3

一般的擴容分為2步，第1步是對哈希表長度的擴展（2倍），第2步是將舊table中的數據搬到新table上。
那麼，在JDK8中，HashMap是如何擴容的呢？

上源代碼片段：

...
// 前面已經做了第1步的長度拓展，我們主要分析第2步的操作：如何遷移數據
table = newTab;
if (oldTab != null) {
 // 循環遍歷哈希table的每個不為null的bucket
 // 注意，這裡是"++j"，略過了oldTab[0]的處理
 for (int j = 0; j < oldCap; ++j) {
 Node e;
 if ((e = oldTab[j]) != null) {
 oldTab[j] = null;
 // 若只有一個結點，則原地存儲
 if (e.next == null)
 newTab[e.hash & (newCap - 1)] = e;
 else if (e instanceof TreeNode)
 ((TreeNode)e).split(this, newTab, j, oldCap);
 else { // preserve order
 // "lo"前綴的代表要在原bucket上存儲，"hi"前綴的代表要在新的bucket上存儲
 // loHead代表是鏈表的頭結點，loTail代表鏈表的尾結點 

 Node loHead = null, loTail = null;
 Node hiHead = null, hiTail = null;
 Node next;
 do {
 next = e.next;
 // 以oldCap=8為例，
 // 0001 1000 e.hash=24
 // & 0000 1000 oldCap=8
 // = 0000 1000 --> 不為0，需要遷移
 // 這種規律可發現，[oldCap, (2*oldCap-1)]之間的數據，
 // 以及在此基礎上加n*2*oldCap的數據，都需要做遷移，剩餘的則不用遷移
 if ((e.hash & oldCap) == 0) {
 // 這種是有序插入，即依次將原鏈表的結點追加到當前鏈表的末尾
 if (loTail == null)
 loHead = e;
 else
 loTail.next = e;
 loTail = e;
 }
 else {
 if (hiTail == null)
 hiHead = e;
 else
 hiTail.next = e;
 hiTail = e;
 }
 } while ((e = next) != null);
 if (loTail != null) {
 loTail.next = null;
 newTab[j] = loHead;
 }
 if (hiTail != null) {
 hiTail.next = null;
 // 需要搬遷的結點，新下標為從當前下標往前挪oldCap個距離。
 newTab[j + oldCap] = hiHead;
 }
 } 

 }
 }
}

2.3 get()操作

瞭解了上面的put()操作，get()操作就比較簡單了。

public V get(Object key) {
 Node e;
 return (e = getNode(hash(key), key)) == null ? null : e.value;
}


final Node getNode(int hash, Object key) {
 Node[] tab; Node first, e; int n; K k;
 if ((tab = table) != null && (n = tab.length) > 0 &&
 (first = tab[(n - 1) & hash]) != null) {
 if (first.hash == hash && // always check first node
 ((k = first.key) == key || (key != null && key.equals(k))))
 return first;
 if ((e = first.next) != null) {
 if (first instanceof TreeNode)
 return ((TreeNode)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);
 }
 }
 return null;
} 

先根據key計算hash值，進一步計算得到哈希table的目標index，若此bucket上為紅黑樹，則再紅黑樹上查找，若不是紅黑樹，遍歷鏈表。

三、HashMap、HashTable是什麼關係？

再把文章開頭的這張圖放出來，溫習一下：

3.1 共同點與異同點

共同點：

• 底層都是使用哈希表 + 鏈表的實現方式。

區別：

• 從層級結構上看，HashMap、HashTable有一個共用的Map接口。另外，HashTable還單獨繼承了一個抽象類Dictionary；
• HashTable誕生自JDK1.0，HashMap從JDK1.2之後才有；
• HashTable線程安全，HashMap線程不安全；
• 初始值和擴容方式不同。HashTable的初始值為11，擴容為原大小的2*d+1。容量大小都採用奇數且為素數，且採用取模法，這種方式散列更均勻。但有個缺點就是對素數取模的性能較低（涉及到除法運算），而HashTable的長度都是2的次冪，設計就較為巧妙，前面章節也提到過，這種方式的取模都是直接做位運算，性能較好。
• HashMap的key、value都可為null，且value可多次為null，key多次為null時會覆蓋。當HashTable的key、value都不可為null，否則直接NPE(NullPointException)。

示例：

public static void main(String[] args) {
 Map<string> testTable = new Hashtable<>();
 testTable.put(null, 23); // 拋NPE
 testTable.put("s1", null); // 拋NPE
}/<string>

看下put()方法的源碼：

public synchronized V put(K key, V value) {
 // Make sure the value is not null
 if (value == null) {
 throw new NullPointerException();
 }


 // Makes sure the key is not already in the hashtable.
 Entry,?> tab[] = table;
 int hash = key.hashCode();
 int index = (hash & 0x7FFFFFFF) % tab.length;
 @SuppressWarnings("unchecked")
 Entry entry = (Entry)tab[index];
 for(; entry != null ; entry = entry.next) {
 if ((entry.hash == hash) && entry.key.equals(key)) {
 V old = entry.value;
 entry.value = value;
 return old;
 }
 }


 addEntry(hash, key, value, index);
 return null;
}

源碼中不允許value為null，若為null則直接拋NPE。
對於key為null時，源碼第9行：int hash = key.hashCode(); 未做判空操作，也會外拋NPE。

另外，我們現在看到的抽象類Dictionary，是一個已經廢棄的類，源碼註釋中有如下說明：

NOTE: This class is obsolete. New implementations should
implement the Map interface, rather than extending this class.

3.2 HashMap的線程安全

能保證線程線程安全的方式有多個，比如添加synchronized關鍵字，或者使用lock機制。兩者的差異不在此展開，後續會寫有關線程安全的文章，到時再詳細說明。而HashTable使用了前者，即synchronized關鍵字。

put操作、get操作、remove操作、equals操作，都使用了synchronized關鍵字修飾。

這麼做是保證了HashTable對象的線程安全特性，但同樣也帶來了問題，突出問題就是效率低下。為何會說它效率低下呢？
因為按synchronized的特性，對於多線程共享的臨界資源，同一時刻只能有一個線程在佔用，其他線程必須原地等待，為方便理解，大家不妨想下計時用的沙漏，中間最細的瓶頸處阻擋了上方細沙的下落，同樣的道理，當有大量線程要執行get()操作時，也存在此類問題，大量線程必須排隊一個個處理。

這時可能會有人說，既然get()方法只是獲取數據，並沒有修改Map的結構和數據，不加不就行了嗎？不好意思，不加也不行，別的方法都加，就你不加，會有一種場景，那就是A線程在做put或remove操作時，B線程、C線程此時都可以同時執行get操作，可能哈希table已經被A線程改變了，也會帶來問題，因此不加也不行。

現在好了，HashMap線程不安全，HashTable雖然線程安全，但性能差，那怎麼破？使用ConcurrentHashMap類吧，既線程安全，還操作高效，誰用誰說好。莫急，下面章節會詳細解釋ConcurrentHashMap類。

四、HashMap線程不安全在哪？

本章節主要探討下HashMap的線程不安全會帶來哪些方面的問題。

4.1 數據覆蓋問題

兩個線程執行put()操作時，可能導致數據覆蓋。JDK7版本和JDK8版本的都存在此問題，這裡以JDK7為例。

假設A、B兩個線程同時執行put()操作，且兩個key都指向同一個buekct，那麼此時兩個結點，都會做頭插法。
先看這裡的代碼實現：

public V put(K key, V value) { 

 ...
 addEntry(hash, key, value, i);
}


void addEntry(int hash, K key, V value, int bucketIndex) {
 ...
 createEntry(hash, key, value, bucketIndex);
}


void createEntry(int hash, K key, V value, int bucketIndex) {
 Entry e = table[bucketIndex];
 table[bucketIndex] = new Entry<>(hash, key, value, e);
 size++;
}

看下最後的createEntry()方法，首先獲取到了bucket上的頭結點，然後再將新結點作為bucket的頭部，並指向舊的頭結點，完成一次頭插法的操作。
當線程A和線程B都獲取到了bucket的頭結點後，若此時線程A的時間片用完，線程B將其新數據完成了頭插法操作，此時輪到線程A操作，但這時線程A所據有的舊頭結點已經過時了（並未包含線程B剛插入的新結點），線程A再做頭插法操作，就會抹掉B剛剛新增的結點，導致數據丟失。

其實不光是put()操作，刪除操作、修改操作，同樣都會有覆蓋問題。

4.2 擴容時導致死循環

這是最常遇到的情況，也是面試經常被問及的考題。但說實話，這個多線程環境下導致的死循環問題，並不是那麼容易解釋清楚，因為這裡已經深入到了擴容的細節。這裡儘可能簡單的描述死循環的產生過程。

另外，只有JDK7及以前的版本會存在死循環現象，在JDK8中，resize()方式已經做了調整，使用兩隊鏈表，且都是使用的尾插法，及時多線程下，也頂多是從頭結點再做一次尾插法，不會造成死循環。而JDK7能造成死循環，就是因為resize()時使用了頭插法，將原本的順序做了反轉，才留下了死循環的機會。

在進一步說明死循環的過程前，我們先看下JDK7中的擴容代碼片段：

void transfer(Entry[] newTable, boolean rehash) {
 int newCapacity = newTable.length;
 for (Entry e : table) {
 while(null != e) {
 Entry 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;
 }
 }
}

其實就是簡單的鏈表反轉，再進一步簡化的話，分為當前結點e，以及下一個結點e.next。我們以鏈表a->b->c->null為例，兩個線程A和B，分別做擴容操作。

原表

線程A和B各自新增了一個新的哈希table，在線程A已做完擴容操作後，線程B才開始擴容。此時對於線程B來說，當前結點e指向a結點，下一個結點e.next仍然指向b結點（此時在線程A的鏈表中，已經是c->b->a的順序）。按照頭插法，哈希表的bucket指向a結點，此時a結點成為線程B中鏈表的頭結點，如下圖所示：

a結點成為線程B中鏈表的頭結點後，下一個結點e.next為b結點。既然下一個結點e.next不為null，那麼當前結點e就變成了b結點，下一個結點e.next變為a結點。繼續執行頭插法，將b變為鏈表的頭結點，同時next指針指向舊的頭節點a，如下圖：

此時，下一個結點e.next為a節點，不為null，繼續頭插法。指針後移，那麼當前結點e就成為了a結點，下一個結點為null。將a結點作為線程B鏈表中的頭結點，並將next指針指向原來的舊頭結點b，如下圖所示：

此時，已形成環鏈表。同時下一個結點e.next為null，流程結束。

4.3 小結

多線程環境下使用HashMap，會引起各類問題，上面僅為不安全問題的兩個典型示例，具體問題無法一一列舉，但大體會分為以下三類：

• 死循環
• 數據重複
• 數據丟失（覆蓋）

在JDK1.5之前，多線程環境往往使用HashTable，但在JDK1.5及以後的版本中，在併發包中引入了專門用於多線程環境的ConcurrentHashMap類，採用分段鎖實現了線程安全，相比HashTable有更高的性能，推薦使用。

五、如何規避HashMap的線程不安全？

前面提到了HashMap在多線程環境下的各類不安全問題，那麼有哪些方式可以轉成線程安全的呢？

5.1 將Map轉為包裝類

如何轉？使用Collections.SynchronizedMap()方法，示例代碼：

Map<string> testMap = new HashMap<>();
...
// 轉為線程安全的map
Map<string> map = Collections.synchronizedMap(testMap);/<string>/<string>

其內部實現也很簡單，等同於HashTable，只是對當前傳入的map對象，新增對象鎖（synchronized）：

// 源碼來自Collections類
 


private static class SynchronizedMap implements Map, Serializable {
 private static final long serialVersionUID = 1978198479659022715L;


 private final Map m; // Backing Map
 final Object mutex; // Object on which to synchronize


 SynchronizedMap(Map m) {
 this.m = Objects.requireNonNull(m);
 mutex = this;
 }


 SynchronizedMap(Map m, Object mutex) {
 this.m = m;
 this.mutex = mutex;
 }


 public int size() {
 synchronized (mutex) {return m.size();}
 }
 public boolean isEmpty() {
 synchronized (mutex) {return m.isEmpty();}
 }
 public boolean containsKey(Object key) {
 synchronized (mutex) {return m.containsKey(key);}
 }
 public boolean containsValue(Object value) {
 synchronized (mutex) {return m.containsValue(value);}
 }
 public V get(Object key) {
 synchronized (mutex) {return m.get(key);}
 }


 public V put(K key, V value) {
 synchronized (mutex) {return m.put(key, value);}
 }
 public V remove(Object key) {
 synchronized (mutex) {return m.remove(key);}
 }
 public void putAll(Map extends K, ? extends V> map) { 

 synchronized (mutex) {m.putAll(map);}
 }
 public void clear() {
 synchronized (mutex) {m.clear();}
 }
}

5.2 使用ConcurrentHashMap

既然HashMap類是線程不安全的，那就不妨找個線程安全的替代品——ConcurrentHashMap類。

使用示例：

Map<string> susuMap = new ConcurrentHashMap<>();
susuMap.put("susu1", 111);
susuMap.put("susu2", 222);
System.out.println(susuMap.get("susu1"));/<string>

在使用習慣上完全兼容了HashMap的使用。

JDK1.5版本引入，位於併發包java.util.concurrent下。

在JDK7版本及以前，ConcurrentHashMap類使用了分段鎖的技術（segment + Lock），但在jdk8中，也做了較大改動，使用回了synchronized修飾符。

文章比較長 希望對你們有所幫助。

讀者福利

歡迎做Java的朋友們私信我【資料】免費獲取免費的Java架構學習資料（裡面有高可用、高併發、高性能及分佈式、Jvm性能調優、Spring源碼，MyBatis，Netty,Redis,Kafka,Mysql,Zookeeper,Tomcat,Docker,Dubbo,Nginx等多個知識點的架構資料）

其中覆蓋了互聯網的方方面面，期間碰到各種產品各種場景下的各種問題，很值得大家借鑑和學習，擴展自己的技術廣度和知識面。

閱讀更多 Java小野貓 的文章

關鍵字: 源碼 集成開發環境 面試題