透過面試題掌握HashMap【持續更新中】

• 2020 年 5 月 15 日
• 筆記

PS:最近做了一個面試題解答的開源項目，大家可以看一看，如果對大家有幫助，希望大家幫忙給一個star，謝謝大家了！

《面試指北》項目地址：//github.com/NotFound9/interviewGuide

之前建了一個技術交流群，大家感興趣也可以進一下，希望可以和大家一起學習進步！

本文主要是自己閱讀了HashMap和ConcurrentHashMap源碼及一些Java容器類相關的部落格後，找了一些很多面經中涉及到的Java容器相關的面試題，自己全部手寫的解答，也花了一些流程圖，之後會繼續更新這一部分。

HashMap相關的面試題

1.HashMap添加一個鍵值對的過程是怎麼樣的？

2.ConcurrentHashMap添加一個鍵值對的過程是怎麼樣的？

3.HashMap與HashTable，ConcurrentHashMap的區別是什麼？

4.HashMap擴容後是否需要rehash？

5.HashMap擴容是怎樣擴容的，為什麼都是2的N次冪的大小？

6.ConcurrentHashMap是怎麼記錄元素個數size的？

7.為什麼ConcurrentHashMap，HashTable不支援key，value為null?

8.HashSet和HashMap的區別？

9.HashMap遍歷時刪除元素的有哪些實現方法？

HashMap添加一個鍵值對的過程是怎麼樣的？

流程圖如下：

1.初始化table

判斷table是否為空或為null，否則執行resize()方法（resize方法一般是擴容時調用，也可以調用來初始化table）。

2.計算hash值

根據鍵值key計算hash值。（因為hashCode是一個int類型的變數，是4位元組，32位，所以這裡會將hashCode的低16位與高16位進行一個異或運算，來保留高位的特徵，以便於得到的hash值更加均勻分布）

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

3.插入或更新節點

根據(n – 1) & hash計算得到插入的數組下標i，然後進行判斷

table[i]==null

那麼說明當前數組下標下，沒有hash衝突的元素，直接新建節點添加。

table[i].hash == hash &&(table[i]== key || (key != null && key.equals(table[i].key)))

判斷table[i]的首個元素是否和key一樣，如果相同直接更新value。

table[i] instanceof TreeNode

判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對。

其他情況

上面的判斷條件都不滿足，說明table[i]存儲的是一個鏈表，那麼遍歷鏈表，判斷是否存在已有元素的key與插入鍵值對的key相等，如果是，那麼更新value，如果沒有，那麼在鏈表末尾插入一個新節點。插入之後判斷鏈表長度是否大於8，大於8的話把鏈錶轉換為紅黑樹。

4.擴容

插入成功後，判斷實際存在的鍵值對數量size是否超多了最大容量threshold(一般是數組長度*負載因子0.75)，如果超過，進行擴容。

源程式碼如下：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // tab為空則創建 
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 計算index，並對null做處理  
    // (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;
        // 節點key存在，直接覆蓋value 
        // 比較桶中第一個元素(數組中的結點)的hash值相等，key相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                // 將第一個元素賦值給e，用e來記錄
                e = p;
        // 判斷該鏈為紅黑樹 
        // hash值不相等，即key不相等；為紅黑樹結點
        else if (p instanceof TreeNode)
            // 放入樹中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 該鏈為鏈表 
        // 為鏈表結點
        else {
            // 在鏈表最末插入結點
            for (int binCount = 0; ; ++binCount) {
                // 到達鏈表的尾部
                if ((e = p.next) == null) {
                    // 在尾部插入新結點
                    p.next = newNode(hash, key, value, null);
                    // 結點數量達到閾值，轉化為紅黑樹
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    // 跳出循環
                    break;
                }
                // 判斷鏈表中結點的key值與插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循環
                    break;
                // 用於遍歷桶中的鏈表，與前面的e = p.next組合，可以遍歷鏈表
                p = e;
            }
        }
        // 表示在桶中找到key值、hash值與插入元素相等的結點
        if (e != null) { 
            // 記錄e的value
            V oldValue = e.value;
            // onlyIfAbsent為false或者舊值為null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替換舊值
                e.value = value;
            // 訪問後回調
            afterNodeAccess(e);
            // 返回舊值
            return oldValue;
        }
    }
    ++modCount;
    // 超過最大容量 就擴容 
    // 實際大小大於閾值則擴容
    if (++size > threshold)
        resize();
    // 插入後回調
    afterNodeInsertion(evict);
    return null;
}

ConcurrentHashMap添加一個鍵值對的過程是怎麼樣的？

這是我自己流程圖如下所示：

1.判斷null值

判斷key==null 或者 value == null，如果是，拋出空指針異常。

2.計算hash

根據key計算hash值(計算結果跟HashMap是一致的，寫法不同)。

3.進入for循環，插入或更新元素

• 3.1 tabnull || tab.length0，

  說明當前tab還沒有初始化。

  那麼調用initTable()方法初始化tab。（在initTable方法中，為了控制只有一個執行緒對table進行初始化，當前執行緒會通過CAS操作對SIZECTL變數賦值為-1，如果賦值成功，執行緒才能初始化table，否則會調用Thread.yield()方法讓出時間片）。

• 3.2 f ==null

  （Node<K,V> f根據hash值計算得到數組下標，下標存儲的元素，f可能是null，鏈表頭節點，紅黑樹根節點或遷移標誌節點ForwardNode）

  說明當前位置還沒有哈希衝突的鍵值對。

  那麼根據key和value創建一個Node，使用CAS操作設置在當前數組下標下，並且break出for循環。

• 3.3 f != null && f.hash = -1

  說明ConcurrentHashMap正在在擴容，當前的節點f是一個標誌節點，當前下標存儲的hash衝突的元素已經遷移了。

  那麼當前執行緒會調用helpTransfer()方法來輔助擴容，擴容完成後會將tab指向新的table，然後繼續執行for循環。

• 3.4 除上面三種以外情況

  說明f節點是一個鏈表的頭結點或者是紅黑樹的根節點，那麼對f加sychronize同步鎖，然後進行以下判斷：

  • f.hash > 0

    如果是f的hash值大於0，當前數組下標存儲的是一個鏈表，f是鏈表的頭結點。

    對鏈表進行遍歷，如果有節點跟當前需要插入節點的hash值相同，那麼對節點的value進行更新，否則根據key，value創建一個Node<K,V>，添加到鏈表末尾。

  • f instanceof TreeBin

    如果f是TreeBin類型，那麼說明當前數組下標存儲的是一個紅黑樹，f是紅黑樹的根節點，調用putTreeVal方法，插入或更新節點。

  插入完成後，判斷binCount（數組下標存儲是一個鏈表時，binCount是鏈表長度），當binCount超過8時，並且數組的長度大於64時，那麼調用treeifyBin方法將鏈錶轉換為紅黑樹。最後break出for循環。

PS：

很多技術文章都是說鏈表長度大於8就轉換為紅黑樹，我當時也沒有注意這個細節，直到有個群里的朋友指正，當原來的鏈表長度超過8時，確實會調用treeifyBin方法，但是在treeifyBin方法中會判斷當前tab是否為空，或者數組長度是否小於64，如果滿足條件，那麼調用resize方法對tab初始化或者擴容，就不會將鏈錶轉換為紅黑樹了。

添加鍵值對的putVal方法的源碼：

treeifyBin方法的源碼：
MIN_TREEIFY_CAPACITY是64

4.判斷是否需要擴容

調用addCount()對當前數組長度加1，在addCount()方法中，會判斷當前元素個數是否超過sizeCtl(擴容閾值，總長度*0.75)，如果是，那麼會進行擴容，如果正處於擴容過程中，當前執行緒會輔助擴容。

HashMap與HashTable，ConcurrentHashMap的區別是什麼？

主要從底層數據結構，執行緒安全，執行效率，是否允許Null值，初始容量及擴容，hash值計算來進行分析。

1.底層數據結構

    transient Node<K,V>[] table; //HashMap
    
    transient volatile Node<K,V>[] table;//ConcurrentHashMap
    
    private transient Entry<?,?>[] table;//HashTable

HashMap=數組+鏈表+紅黑樹

HashMap的底層數據結構是一個數組+鏈表+紅黑樹，數組的每個元素存儲是一個鏈表的頭結點，鏈表中存儲了一組哈希值衝突的鍵值對，通過鏈地址法來解決哈希衝突的。為了避免鏈表長度過長，影響查找元素的效率，當鏈表的長度>8時，會將鏈錶轉換為紅黑樹，鏈表的長度<6時，將紅黑樹轉換為鏈表。之所以臨界點為8是因為紅黑樹的查找時間複雜度為logN，鏈表的平均時間查找複雜度為N/2，當N為8時，logN為3，是小於N/2的，正好可以通過轉換為紅黑樹減少查找的時間複雜度。

Hashtable=數組+鏈表

Hashtable底層數據結構跟HashMap一致，底層數據結構是一個數組+鏈表，也是通過鏈地址法來解決衝突，只是鏈表過長時，不會轉換為紅黑樹來減少查找時的時間複雜度。Hashtable屬於歷史遺留類，實際開發中很少使用。

ConcurrentHashMap=數組+鏈表+紅黑樹

ConcurrentHashMap底層數據結構跟HashMap一致，底層數據結構是一個數組+鏈表+紅黑樹。只不過使用了volatile來進行修飾它的屬性，來保證記憶體可見性(一個執行緒修改了這些屬性後，會使得其他執行緒中對於該屬性的快取失效，以便下次讀取時取最新的值)。

2.執行緒安全

HashMap 非執行緒安全

HashMap是非執行緒安全的。（例如多個執行緒插入多個鍵值對，如果兩個鍵值對的key哈希衝突，可能會使得兩個執行緒在操作同一個鏈表中的節點，導致一個鍵值對的value被覆蓋）

HashTable 執行緒安全

HashTable是執行緒安全的，主要通過使用synchronized關鍵字修飾大部分方法，使得每次只能一個執行緒對HashTable進行同步修改，性能開銷較大。

ConcurrentHashMap 執行緒安全

ConcurrentHashMap是執行緒安全的，主要是通過CAS操作+synchronized來保證執行緒安全的。

CAS操作

往ConcurrentHashMap中插入新的鍵值對時，如果對應的數組下標元素為null，那麼通過CAS操作原子性地將節點設置到數組中。

//這是添加新的鍵值對的方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
...其他程式碼
  if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
    if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) 				break; // 因為對應的數組下標元素為null，所以null作為預期值，new Node<K,V>(hash, key, value, null)作為即將更新的值，只有當記憶體中的值與即將預期值一致時，才會進行更新，保證原子性。
  }
...其他程式碼
}
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                        Node<K,V> c, Node<K,V> v) {
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

synchronized鎖

往ConcurrentHashMap中插入新的鍵值對時，如果對應的數組下標元素不為null，那麼會對數組下標存儲的元素(也就是鏈表的頭節點)加synchronized鎖， 然後進行插入操作，

Node<K,V> f = tabAt(tab, i = (n - 1) & hash));
synchronized (f) {//f就是數組下標存儲的元素
    if (tabAt(tab, i) == f) {
        if (fh >= 0) {
            binCount = 1;
            for (Node<K,V> e = f;; ++binCount) {
                K ek;
                if (e.hash == hash &&
                    ((ek = e.key) == key ||
                     (ek != null && key.equals(ek)))) {
                    oldVal = e.val;
                    if (!onlyIfAbsent)
                        e.val = value;
                    break;
                }
                Node<K,V> pred = e;
                if ((e = e.next) == null) {
                    pred.next = new Node<K,V>(hash, key,
                                              value, null);
                    break;
                }
            }
        }
        else if (f instanceof TreeBin) {
            Node<K,V> p;
            binCount = 2;
            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                           value)) != null) {
                oldVal = p.val;
                if (!onlyIfAbsent)
                    p.val = value;
            }
        }
    }
}

3.執行效率

因為HashMap是非執行緒安全的，執行效率會高一些，其次是ConcurrentHashMap，因為HashTable在進行修改和訪問時是對整個HashTable加synchronized鎖，所以效率最低。

4.是否允許null值出現

HashMap的key和null都可以為null，如果key為null，那麼計算的hash值會是0，最終計算得到的數組下標也會是0，所以key為null的鍵值對會存儲在數組中的首元素的鏈表中。value為null的鍵值對也能正常插入，跟普通鍵值對插入過程一致。

static final int hash(Object key) {
	int h;
	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

HashTable的鍵和值都不能為null，如果將HashTable的一個鍵值對的key設置為null，因為null值沒法調用hashCode()方法獲取哈希值，所以會拋出空指針異常。同樣value為null時，在put方法中會進行判斷，然後拋出空指針異常。

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        ...其他程式碼
}

ConcurrentHashMap的鍵和值都不能為null,在putVal方法中會進行判斷，為null會拋出空指針異常。

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    ...其他程式碼
}

5.初始容量及擴容

不指定初始容量

如果不指定初始容量，HashMap和ConcurrentHashMap默認會是16，HashTable的容量默認會是11。

不指定初始容量

如果制定了初始容量，HashMap和ConcurrentHashMap的容量會是比初始容量稍微大一些的2的冪次方大小，HashTable會使用初始容量，

擴容

擴容時，HashMap和ConcurrentHashMap擴容時會是原來長度的兩倍，HashTable則是2倍加上1.

6.hash值計算

HashTable會擴容為2n+1，HashTable之所以容量取11，及擴容時是是2n+1，是為了保證 HashTable的長度是一個素數，因為數組的下標是用key的hashCode與數組的長度取模進行計算得到的，而當數組的長度是素數時，可以保證計算得到的數組下標分布得更加均勻，可以看看這篇文章//zhaox.github.io/algorithm/2015/06/29/hash

public synchronized V put(K key, V value) {
         ...其他程式碼
        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        ...其他程式碼
}

HashMap和ConcurrentHashMap的hash值都是通過將key的hashCode()高16位與低16位進行異或運算(這樣可以保留高位的特徵，避免一些key的hashCode高位不同，低位相同，造成hash衝突)，得到hash值，然後將hash&(n-1)計算得到數組下標。（n為數組的長度，因為當n為2的整數次冪時，hash mod n的結果在數學上等於hash&(n-1)，而且電腦進行&運算更快，所以這也是HashMap的長度總是設置為2的整數次冪的原因）

//HashMap計算hash值的方法
static int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 
}
//ConcurrentHashMap計算hash值的方法 
static  int spread(int h) {//h是對象的hashCode
    return (h ^ (h >>> 16)) & HASH_BITS;// HASH_BITS = 0x7fffffff;
}
  

HashMap擴容後是否需要rehash？

在JDK1.8以後，不需要rehash，因為鍵值對的Hash值主要是根據key的hashCode()的高16位與低16位進行異或計算後得到，根據hash%length，計算得到數組的下標index，因為length是2的整數次冪，當擴容後length變為原來的兩倍時，hash%(2*length)的計算結果結果差別在於第length位的值是1還是0，如果是0，那麼在新數組中的index與舊數組的一直，如果是1，在新數組中的index會是舊數組中的數組中的index+length。

HashMap擴容是怎樣擴容的，為什麼都是2的N次冪的大小？

觸發擴容

在沒有指定初始長度的情況下，HashMap數組的默認長度為16，在添加一個新的鍵值對時，會調用putVal()方法，在方法中，成功添加一個新的鍵值對以後，會判斷當前的元素個數是否超過閥值(數組長度*負載因子0.75)，如果超過那麼調用resize方法進行擴容。具體的擴容步驟如下：

計算擴容後的長度

• 如果當前table為null

  那麼直接初始化一個數組長度為16的數組返回。

• 如果當前table的length已經大於HashMap指定的最大值2的30次方

  那麼直接返回舊table，不進行擴容。

• 其他情況

  將table的length擴容為2倍，然後計算新的擴容閥值（新數組長度*0.75）。

初始化新數組

會根據擴容後的數組長度初始化話一個新的數組，並且直接賦值給當前hashMap的成員變數table。

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;

這一步就很有意思，也是HashMap是非執行緒安全的表現之一，因為此時newTab還是一個空數組，如果有其他執行緒訪問HashMap，根據key去newTab中找鍵值對，會返回null。實際上可能key是有對應的鍵值對的，只不過鍵值對都保存在舊table中，還沒有遷移過來。

（與之相反，HashTable在解決擴容時其他執行緒訪問的問題，是通過對大部分方法使用sychronized關鍵字修飾，也就是某個執行緒在執行擴容方法時，會對HashTable對象加鎖，其他執行緒無法訪問HashTable。ConcurrentHashMap在解決擴容時其他執行緒訪問的問題，是通過設置ForwardingNode標識節點來解決的，擴容時，某個執行緒對數組中某個下標下所有Hash衝突的元素進行遷移時，那麼會將數組下標的數組元素設置為一個標識節點ForwardingNode，之後其他執行緒在訪問時，如果發現key的hash值映射的數組下標對應是一個標識節點ForwardingNode（ForwardingNode繼承於普通Node，區別字啊呀這個節點的hash值會設置為-1，並且會多一個指向擴容過程中新tab的指針nextTable），那麼會根據ForwardingNode中的nextTable變數，去新的tab中查找元素。（如果是添加新的鍵值對時發現是ForwardingNode，那麼輔助擴容或阻塞等待，擴容完成後去新數組中更新或插入元素）

遷移元素

因為HashMap的數組長度總是2的N次冪，擴容後也是變為原來的2倍，所以有一個數學公式，當length為2的N次冪時，

hash%length=hash&(length-1)

而因為length是2的N次冪，length-1在二進位中其實是N-1個1。例如：

length為16，length用2進位表示是10000，

length-1是15，用2進位表示是1111，

2*length為32，length用2進位表示是100000，

2*length-1為31，length用2進位表示是11111，

所以hash&(length-1)的計算結果與hash&(2*length-1)的計算結果差別在於擴容後需要多看一位，也就是看第N位的1與hash值的&結果。

假設原數組長度為16，length-1二進位表示為1111。key1的hash值為9，二進位表示為01001，key2的hash值為25，11001，

所以hash&(length-1)的結果只要看低4位的結果，9和25的低4位都是1001，所以計算結果一致，計算結果都是9，所以在數組中處於數組下標為9的元素鏈表中。

擴容後數組長度為32，length-1二進位表示為11111，key1的hash值為9，二進位表示為01001，key2的hash值為25，11001，

所以hash&(2*length-1)的結果需要看低5位的結果，9和25的低4位都是1001，所以計算結果不一致，計算結果都是9和25，因為key2的hash值的第五位為1，key1的hash值的第五位為0，所以會多16，也就是原數組長度的大小。

所以原數組同一下標index下的鏈表存儲的hash衝突的元素，擴容後在新數組中的下標newIndex要麼為index，要麼為index+length（去決定於hash值的第N位為1，還是0，也就是hash&length的結果，原數組長度length為2的N-1次冪）

所以會遍歷鏈表(或者紅黑樹)，然後對數組下標index下每個節點計算hash&length的結果，然後存放在兩個不同的臨時鏈表中，遍歷完成後，hash&length結果為0的元素組成的臨時鏈表會存儲在新數組index位置，hash&length結果為1的元素組成的臨時鏈表會存儲在新數組index+length位置。

ConcurrentHashMap是怎麼記錄元素個數size的？

HashMap默認是非執行緒安全的，可以認為每次只有一個執行緒來執行操作，所以hashMap就使用一個很簡單的int類型的size變數來記錄HashMap鍵值對數量就行了。

HashMap記錄鍵值對數量的實現如下：

transient int size;
public int size() {
	return size;
}

ConcurrentHashMap記錄鍵值對數量的實現如下：

//size方法最大只能返回Integer.MAX_VALUE
public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 : (n > (long)Integer.MAX_VALUE) ?Integer.MAX_VALUE : (int)n);
}

//mappingCount方法可以返回long類型的最大值，
public long mappingCount() {
    long n = sumCount();
    return (n < 0L) ? 0L : n; // ignore transient negative values
}

private transient volatile long baseCount;
private transient volatile CounterCell[] counterCells;

//sumCount會返回sumCount加上CounterCells數組中每個元素as存儲的value
final long sumCount() {
		CounterCell[] as = counterCells; CounterCell a;
		long sum = baseCount;
		if (as != null) {
				for (int i = 0; i < as.length; ++i) {
					if ((a = as[i]) != null)
							sum += a.value;
				}
		}
		return sum;
}

@sun.misc.Contended //這個註解可以避免偽共享，提升性能。加與不加，性能差距達到了 5 倍。在快取系統中，由於一個快取行是出於32-256個位元組之間，常見的快取行為64個位元組。而一般的變數可能達不到那麼多位元組，所以會出現多個相互獨立的變數存儲在一個快取行中的情況，此時即便多執行緒訪問快取行上相互獨立變數時，也涉及到並發競爭，會有性能開銷，加了@sun.misc.Contended這個註解，在jDK8中，會對對象前後都增加128位元組的padding，使用2倍於大多數硬體快取行的大小來避免相鄰扇區預取導致的偽共享衝突。
static final class CounterCell {
    volatile long value;
    CounterCell(long x) { value = x; }
}

每次添加x個新的鍵值對後，會調用addCount()方法使用CAS操作對baseCount+x，如果操作失敗，那麼會新建一個CounterCell類型的對象，保存新增的數量x，並且將對象添加到CounterCells數組中去。

為什麼ConcurrentHashMap，HashTable不支援key，value為null？

因為HashMap是非執行緒安全的，默認單執行緒環境中使用，如果get(key)為null，可以通過containsKey(key)
方法來判斷這個key的value為null，還是不存在這個key，而ConcurrentHashMap，HashTable是執行緒安全的，
在多執行緒操作時，因為get(key)和containsKey(key)兩個操作和在一起不是一個原子性操作，
可能在執行中間，有其他執行緒修改了數據，所以無法區分value為null還是不存在key。
至於ConcurrentHashMap，HashTable的key不能為null，主要是設計者的設計意圖。

HashSet和HashMap的區別？

HashMap主要是用於存儲非重複鍵值對，HashSet存儲非重複的對象。雖然HashMap是繼承於AbstractMap，實現了Map介面，HashSet繼承於AbstractSet，實現了Set介面。但是由於它們都有去重的需求，所以HashSet主要實現都是基於HashMap的（如果需要復用一個類，我們可以使用繼承模式，也可以使用組合模式。組合模式就是將一個類作為新類的組成部分，以此來達到復用的目的。）例如，在HashSet類中，有一個HashMap類型的成員變數map，這就是組合模式的應用。

    public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    private transient HashMap<E,Object> map;
    private static final Object PRESENT = new Object();//佔位對象
    public HashSet() {
        map = new HashMap<>();
    }
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;//佔位對象
    }
}

在HashSet的構造方法中，創建了一個HashMap，賦值給map屬性，之後在添加元素時，就是將元素作為key添加到HashMap中，只不過value是一個佔位對象PRESENT。除了 clone()、writeObject()、readObject()是 HashSet 自己不得不實現之外，其他方法都是直接調用 HashMap 中的方法。那麼HashMap又是如何實現key不重複的呢？

在調用HashMap的putVal方法添加新的鍵值對時，會進行如下操作：

1.根據key計算hash值。

2.根據hash值映射數組下標，然後獲取數組下標的對應的元素。

3.數組下標存儲的是一個鏈表，鏈表包含了哈希衝突的元素，會對鏈表進行遍歷，判斷hash1hash2，除此以外，還必須要key1key2，或者key1.equals(key2)。

因為兩個不同的對象的hashCode可能相等，但是相同的對象的hashCode肯定相等，

==是判斷兩個變數或實例是不是指向同一個記憶體地址，如果是同一個記憶體地址，對象肯定相等。

int hash = hash(key);//根據key計算hash值
p = tab[i = (n - 1) & hash];//根據hash值映射數組下標，然後獲取數組下標的對應的元素。
for (int binCount = 0; ; ++binCount) {//數組下標存儲的是一個鏈表，鏈表包含了哈希衝突的元素，會對鏈表進行遍歷，判斷每個節點的hash值與插入元素的hash值是否相等，並且是存儲key對象的地址相等，或者key相等。
if (e.hash == hash &&
	((k = e.key) == key || (key != null && key.equals(k))))
		break;
		p = e;
}

HashMap遍歷時刪除元素的有哪些實現方法？

首先結論如下：

第1種方法 – for-each遍歷HashMap.entrySet，使用HashMap.remove()刪除(結果：拋出異常)。

第2種方法-for-each遍歷HashMap.keySet，使用HashMap.remove()刪除(結果：拋出異常)。

第3種方法-使用HashMap.entrySet().iterator()遍歷刪除(結果：正確刪除)。

下面讓我們來詳細探究一下原因吧！

HashMap的遍歷刪除方法與ArrayList的大同小異，只是api的調用方式不同。首先初始化一個HashMap，我們要刪除key包含”3″字元串的鍵值對。

HashMap<String,Integer> hashMap = new HashMap<String,Integer>();
hashMap.put("key1",1);
hashMap.put("key2",2);
hashMap.put("key3",3);
hashMap.put("key4",4);
hashMap.put("key5",5);
hashMap.put("key6",6);

第1種方法 – for-each遍歷HashMap.entrySet，使用HashMap.remove()刪除(結果：拋出異常)

for (Map.Entry<String,Integer> entry: hashMap.entrySet()) {
        String key = entry.getKey();
        if(key.contains("3")){
            hashMap.remove(entry.getKey());
        }
     System.out.println("當前HashMap是"+hashMap+" 當前entry是"+entry);

}

輸出結果：

當前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 當前entry是key1=1
當前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 當前entry是key2=2
當前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 當前entry是key5=5
當前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 當前entry是key6=6
當前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4} 當前entry是key3=3
Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.HashMap$HashIterator.nextNode(HashMap.java:1429)
	at java.util.HashMap$EntryIterator.next(HashMap.java:1463)
	at java.util.HashMap$EntryIterator.next(HashMap.java:1461)
	at com.test.HashMapTest.removeWayOne(HashMapTest.java:29)
	at com.test.HashMapTest.main(HashMapTest.java:22)

第2種方法-for-each遍歷HashMap.keySet，使用HashMap.remove()刪除(結果：拋出異常)

Set<String> keySet = hashMap.keySet();
for(String key : keySet){
    if(key.contains("3")){
        keySet.remove(key);
    }
    System.out.println("當前HashMap是"+hashMap+" 當前key是"+key);
}

輸出結果如下：

當前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 當前key是key1
當前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 當前key是key2
當前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 當前key是key5
當前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 當前key是key6
當前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4} 當前key是key3
Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.HashMap$HashIterator.nextNode(HashMap.java:1429)
	at java.util.HashMap$KeyIterator.next(HashMap.java:1453)
	at com.test.HashMapTest.removeWayTwo(HashMapTest.java:40)
	at com.test.HashMapTest.main(HashMapTest.java:23)

第3種方法-使用HashMap.entrySet().iterator()遍歷刪除(結果：正確刪除)

Iterator<Map.Entry<String, Integer>> iterator  = hashMap.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, Integer> entry = iterator.next();
    if(entry.getKey().contains("3")){
        iterator.remove();
    }
    System.out.println("當前HashMap是"+hashMap+" 當前entry是"+entry);
}

輸出結果：

當前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 當前entry是key1=1
當前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 當前entry是key2=2
當前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 當前entry是key5=5
當前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 當前entry是key6=6
當前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 當前entry是key4=4
當前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4} 當前entry是deletekey=3

第1種方法和第2種方法拋出ConcurrentModificationException異常與上面ArrayList錯誤遍歷-刪除方法的原因一致，HashIterator也有一個expectedModCount，在遍歷時獲取下一個元素時，會調用next()方法，然後對
expectedModCount和modCount進行判斷，不一致就拋出ConcurrentModificationException異常。

abstract class HashIterator {
    Node<K,V> next;        // next entry to return
    Node<K,V> current;     // current entry
    int expectedModCount;  // for fast-fail
    int index;             // current slot

    HashIterator() {
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // advance to first entry
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        if ((next = (current = e).next) == null && (t = table) != null) {
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }

    public final void remove() {
        Node<K,V> p = current;
        if (p == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null;
        K key = p.key;
        removeNode(hash(key), key, null, false, false);
        expectedModCount = modCount;
    }
}

PS：ConcurrentModificationException是什麼？

根據ConcurrentModificationException的文檔介紹，一些對象不允許並發修改，當這些修改行為被檢測到時，就會拋出這個異常。（例如一些集合不允許一個執行緒一邊遍歷時，另一個執行緒去修改這個集合）。

一些集合（例如Collection, Vector, ArrayList，LinkedList, HashSet, Hashtable, TreeMap, AbstractList, Serialized Form）的Iterator實現中，如果提供這種並發修改異常檢測，那麼這些Iterator可以稱為是”fail-fast Iterator”，意思是快速失敗迭代器，就是檢測到並發修改時，直接拋出異常，而不是繼續執行，等到獲取到一些錯誤值時在拋出異常。

異常檢測主要是通過modCount和expectedModCount兩個變數來實現的，

• modCount
  集合被修改的次數，一般是被集合(ArrayList之類的)持有，每次調用add()，remove()方法會導致modCount+1

• expectedModCount
  期待的modCount，一般是被Iterator(ArrayList.iterator()方法返回的iterator對象)持有，一般在Iterator初始化時會賦初始值，在調用Iterator的remove()方法時會對expectedModCount進行更新。（可以看看上面的ArrayList.Itr源碼）

然後在Iterator調用next()遍曆元素時，會調用checkForComodification()方法比較modCount和expectedModCount，不一致就拋出ConcurrentModificationException。

單執行緒操作Iterator不當時也會拋出ConcurrentModificationException異常。（上面的例子就是）

總結

因為ArrayList和HashMap的Iterator都是上面所說的「fail-fast Iterator」，Iterator在獲取下一個元素，刪除元素時，都會比較expectedModCount和modCount，不一致就會拋出異常。

所以當使用Iterator遍曆元素(for-each遍歷底層實現也是Iterator)時，需要刪除元素，一定需要使用 Iterator的remove()方法 來刪除，而不是直接調用ArrayList或HashMap自身的remove()方法,否則會導致Iterator中的expectedModCount沒有及時更新，之後獲取下一個元素或者刪除元素時，expectedModCount和modCount不一致，然後拋出ConcurrentModificationException異常。