主頁 > 後端開發 > 透過面試題掌握HashMap【持續更新中】

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

2020-10-28 14:22:00 後端開發

本文已收錄到1.1K Star數開源學習指南——《大廠面試指北》，如果想要了解更多大廠面試相關的內容及獲取《大廠面試指北》離線PDF版，請掃描下方二維碼碼關注公眾號“大廠面試”，謝謝大家了！

《大廠面試指北》最佳閱讀地址：

http://notfound9.github.io/interviewGuide/

《大廠面試指北》專案地址：

https://github.com/NotFound9/interviewGuide

獲取《大廠面試指北》離線PDF版，請掃描下方二維碼關注公眾號“大廠面試”

《大廠面試指北》專案截圖：

本文主要是自己閱讀了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 = https://www.cnblogs.com/notfound9/p/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 =https://www.cnblogs.com/notfound9/p/= 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 =https://www.cnblogs.com/notfound9/p/= 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 =https://www.cnblogs.com/notfound9/p/= 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與陣列的長度取模進行計算得到的，而當陣列的長度是素數時，可以保證計算得到的陣列下標分布得更加均勻，可以看看這篇文章http://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 = https://www.cnblogs.com/notfound9/p/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例外，

《面試指北》

本文已經收錄到《面試指北》專欄，大家感興趣也可以看看《面試指北》這個開源專案
《面試指北》專案地址：https://github.com/NotFound9/interviewGuide
專案截圖：
image.png

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/195324.html

標籤：Java

上一篇：日志系列2——logback組態檔詳解

下一篇：反-反爬蟲的一些小技巧

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 【C++】Microsoft C++、C 和匯編程式檔案

    ......

    uj5u.com 2020-09-10 00:57:23 more
  • 例外宣告

    相比于斷言適用于排除邏輯上不可能存在的狀態，例外通常是用于邏輯上可能發生的錯誤。 例外宣告 Item 1：當函式不可能拋出例外或不能接受拋出例外時，使用noexcept 理由 如果不打算拋出例外的話，程式就會認為無法處理這種錯誤，并且應當盡早終止，如此可以有效地阻止例外的傳播與擴散。 示例 //不可 ......

    uj5u.com 2020-09-10 00:57:27 more
  • Codeforces 1400E Clear the Multiset(貪心 + 分治)

    鏈接：https://codeforces.com/problemset/problem/1400/E 來源：Codeforces 思路：給你一個陣列，現在你可以進行兩種操作，操作1：將一段沒有 0 的區間進行減一的操作，操作2：將 i 位置上的元素歸零。最終問：將這個陣列的全部元素歸零后操作的最少 ......

    uj5u.com 2020-09-10 00:57:30 more
  • UVA11610 【Reverse Prime】

    本人看到此題沒有翻譯，就附帶了一個自己的翻譯版本 思考 這一題，它的第一個要求是找出所有 $7$ 位反向質數及其質因數的個數。 我們應該需要質數篩篩選1~$10^{7}$的所有數，這里就不慢慢介紹了。但是，重讀題，我們突然發現反向質數都是 $7$ 位，而將它反過來后的數字卻是 $6$ 位數，這就說明 ......

    uj5u.com 2020-09-10 00:57:36 more
  • 統計區間素數數量

    1 #pragma GCC optimize(2) 2 #include <bits/stdc++.h> 3 using namespace std; 4 bool isprime[1000000010]; 5 vector<int> prime; 6 inline int getlist(int ......

    uj5u.com 2020-09-10 00:57:47 more
  • C/C++編程筆記：C++中的 const 變數詳解，教你正確認識const用法

    1、C中的const 1、區域const變數存放在堆疊區中，會分配記憶體（也就是說可以通過地址間接修改變數的值）。測驗代碼如下： 運行結果： 2、全域const變數存放在只讀資料段（不能通過地址修改，會發生寫入錯誤）， 默認為外部聯編，可以給其他源檔案使用（需要用extern關鍵字修飾） 運行結果： ......

    uj5u.com 2020-09-10 00:58:04 more
  • 【C++犯錯記錄】VS2019 MFC添加資源不懂如何修改資源宏ID

    1. 首先在資源視圖中，添加資源 2. 點擊新添加的資源，復制自動生成的ID 3. 在解決方案資源管理器中找到Resource.h檔案，編輯，使用整個專案搜索和替換的方式快速替換 宏宣告 4. Ctrl+Shift+F 全域搜索，點擊查找全部，然后逐個替換 5. 為什么使用搜索替換而不使用屬性視窗直 ......

    uj5u.com 2020-09-10 00:59:11 more
  • 【C++犯錯記錄】VS2019 MFC不懂的批量添加資源

    1. 打開資源頭檔案Resource.h，在其中預先定義好宏 ID（不清楚其實ID值應該設定多少，可以先新建一個相同的資源項，再在這個資源的ID值的基礎上遞增即可） 2. 在資源視圖中選中專案資源，按F7編輯資源檔案，按 ID 型別 相對路徑的形式添加 資源。（別忘了先把檔案拷貝到專案中的res檔案 ......

    uj5u.com 2020-09-10 01:00:19 more
  • C/C++編程筆記：關于C++的參考型別，專供新手入門使用

    今天要講的是C++中我最喜歡的一個用法——參考，也叫別名。 參考就是給一個變數名取一個變數名，方便我們間接地使用這個變數。我們可以給一個變數創建N個參考，這N + 1個變數共享了同一塊記憶體區域。(參考型別的變數會占用記憶體空間，占用的記憶體空間的大小和指標型別的大小是相同的。雖然參考是一個物件的別名，但 ......

    uj5u.com 2020-09-10 01:00:22 more
  • 【C/C++編程筆記】從頭開始學習C ++：初學者完整指南

    眾所周知，C ++的學習曲線陡峭，但是花時間學習這種語言將為您的職業帶來奇跡，并使您與其他開發人員區分開。您會更輕松地學習新語言，形成真正的解決問題的技能，并在編程的基礎上打下堅實的基礎。 C ++將幫助您養成良好的編程習慣（即清晰一致的編碼風格，在撰寫代碼時注釋代碼，并限制類內部的可見性），并且由 ......

    uj5u.com 2020-09-10 01:00:41 more
最新发布
  • Rust中的智能指標:Box<T> Rc<T> Arc<T> Cell<T> RefCell<T> Weak

    Rust中的智能指標是什么 智能指標（smart pointers）是一類資料結構，是擁有資料所有權和額外功能的指標。是指標的進一步發展 指標（pointer）是一個包含記憶體地址的變數的通用概念。這個地址參考，或 ” 指向”（points at）一些其 他資料 。參考以 & 符號為標志并借用了他們所 ......

    uj5u.com 2023-04-20 07:24:10 more
  • Java的值傳遞和參考傳遞

    值傳遞不會改變本身，參考傳遞（如果傳遞的值需要實體化到堆里）如果發生修改了會改變本身。 1.基本資料型別都是值傳遞 package com.example.basic; public class Test { public static void main(String[] args) { int ......

    uj5u.com 2023-04-20 07:24:04 more
  • [2]SpinalHDL教程——Scala簡單入門

    第一個 Scala 程式 shell里面輸入 $ scala scala> 1 + 1 res0: Int = 2 scala> println("Hello World!") Hello World! 檔案形式 object HelloWorld { /* 這是我的第一個 Scala 程式 * 以 ......

    uj5u.com 2023-04-20 07:23:58 more
  • 理解函式指標和回呼函式

    理解 函式指標 指向函式的指標。比如： 理解函式指標的偽代碼 void (*p)(int type, char *data); // 定義一個函式指標p void func(int type, char *data); // 宣告一個函式func p = func; // 將指標p指向函式func ......

    uj5u.com 2023-04-20 07:23:52 more
  • Django筆記二十五之資料庫函式之日期函式

    本文首發于公眾號：Hunter后端 原文鏈接：Django筆記二十五之資料庫函式之日期函式 日期函式主要介紹兩個大類，Extract() 和 Trunc() Extract() 函式作用是提取日期，比如我們可以提取一個日期欄位的年份，月份，日等資料 Trunc() 的作用則是截取，比如 2022-0 ......

    uj5u.com 2023-04-20 07:23:45 more
  • 一天吃透JVM面試八股文

    什么是JVM？ JVM，全稱Java Virtual Machine（Java虛擬機），是通過在實際的計算機上仿真模擬各種計算機功能來實作的。由一套位元組碼指令集、一組暫存器、一個堆疊、一個垃圾回收堆和一個存盤方法域等組成。JVM屏蔽了與作業系統平臺相關的資訊，使得Java程式只需要生成在Java虛擬機 ......

    uj5u.com 2023-04-20 07:23:31 more
  • 使用Java接入小程式訂閱訊息！

    更新完微信服務號的模板訊息之后，我又趕緊把微信小程式的訂閱訊息給實作了！之前我一直以為微信小程式也是要企業才能申請，沒想到小程式個人就能申請。 訊息推送平臺🔥推送下發【郵件】【短信】【微信服務號】【微信小程式】【企業微信】【釘釘】等訊息型別。 https://gitee.com/zhongfuch ......

    uj5u.com 2023-04-20 07:22:59 more
  • java -- 緩沖流、轉換流、序列化流

    緩沖流 緩沖流, 也叫高效流, 按照資料型別分類： 位元組緩沖流：BufferedInputStream，BufferedOutputStream 字符緩沖流：BufferedReader，BufferedWriter 緩沖流的基本原理，是在創建流物件時，會創建一個內置的默認大小的緩沖區陣列，通過緩沖 ......

    uj5u.com 2023-04-20 07:22:49 more
  • Java-SpringBoot-Range請求頭設定實作視頻分段傳輸

    老實說，人太懶了，現在基本都不喜歡寫筆記了，但是網上有關Range請求頭的文章都太水了 下面是抄的一段StackOverflow的代碼...自己大修改過的，寫的注釋挺全的，應該直接看得懂，就不解釋了 寫的不好...只是希望能給視頻網站開發的新手一點點幫助吧. 業務場景：視頻分段傳輸、視頻多段傳輸（理 ......

    uj5u.com 2023-04-20 07:22:42 more
  • Windows 10開發教程_編程入門自學教程_菜鳥教程-免費教程分享

    教程簡介 Windows 10開發入門教程 - 從簡單的步驟了解Windows 10開發，從基本到高級概念，包括簡介，UWP，第一個應用程式，商店，XAML控制元件，資料系結，XAML性能，自適應設計，自適應UI，自適應代碼，檔案管理，SQLite資料庫，應用程式到應用程式通信，應用程式本地化，應用程式 ......

    uj5u.com 2023-04-20 07:22:35 more

Copyright © 2010-2020 有解無憂