透過面試題掌握HashMap【持續(xù)更新中】

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

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

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

《大廠面試指北》項目地址：

https://github.com/NotFound9/interviewGuide

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

image.png

《大廠面試指北》項目截圖：

image.png

文章說明

下面是主要是自己看了《瘋狂Java講義》和一些Java容器類相關(guān)的博客，以及很多面經(jīng)中涉及到的Java容器相關(guān)的面試題后，自己全部手寫的解答，也花了一些流程圖，之后會繼續(xù)更新這一部分。

HashMap相關(guān)的面試題

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

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

3.HashMap與HashTable，ConcurrentHashMap的區(qū)別是什么？

4.HashMap擴(kuò)容后是否需要rehash？

5.HashMap擴(kuò)容是怎樣擴(kuò)容的，為什么都是2的N次冪的大小？

6.ConcurrentHashMap是怎么記錄元素個數(shù)size的？

7.為什么ConcurrentHashMap，HashTable不支持key，value為null?

8.HashSet和HashMap的區(qū)別？

9.HashMap遍歷時刪除元素的有哪些實現(xiàn)方法？

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

流程圖如下：

image

1.初始化table

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

2.計算hash值

根據(jù)鍵值key計算hash值。（因為hashCode是一個int類型的變量，是4字節(jié)，32位，所以這里會將hashCode的低16位與高16位進(jìn)行一個異或運(yùn)算，來保留高位的特征，以便于得到的hash值更加均勻分布）

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

3.插入或更新節(jié)點

根據(jù)(n - 1) & hash計算得到插入的數(shù)組下標(biāo)i，然后進(jìn)行判斷

table[i]==null

那么說明當(dāng)前數(shù)組下標(biāo)下，沒有hash沖突的元素，直接新建節(jié)點添加。

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，如果沒有，那么在鏈表末尾插入一個新節(jié)點。插入之后判斷鏈表長度是否大于8，大于8的話把鏈表轉(zhuǎn)換為紅黑樹。

4.擴(kuò)容

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

源代碼如下：

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

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

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

image

1.判斷null值

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

2.計算hash

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

3.進(jìn)入for循環(huán)，插入或更新元素

  • 3.1 tab==null || tab.length==0，

    說明當(dāng)前tab還沒有初始化。

    那么調(diào)用initTable()方法初始化tab。（在initTable方法中，為了控制只有一個線程對table進(jìn)行初始化，當(dāng)前線程會通過CAS操作對SIZECTL變量賦值為-1，如果賦值成功，線程才能初始化table，否則會調(diào)用Thread.yield()方法讓出時間片）。

  • 3.2 f ==null

    （Node<K,V> f根據(jù)hash值計算得到數(shù)組下標(biāo)，下標(biāo)存儲的元素，f可能是null，鏈表頭節(jié)點，紅黑樹根節(jié)點或遷移標(biāo)志節(jié)點ForwardNode）

    說明當(dāng)前位置還沒有哈希沖突的鍵值對。

    那么根據(jù)key和value創(chuàng)建一個Node，使用CAS操作設(shè)置在當(dāng)前數(shù)組下標(biāo)下，并且break出for循環(huán)。

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

    說明ConcurrentHashMap正在在擴(kuò)容，當(dāng)前的節(jié)點f是一個標(biāo)志節(jié)點，當(dāng)前下標(biāo)存儲的hash沖突的元素已經(jīng)遷移了。

    那么當(dāng)前線程會調(diào)用helpTransfer()方法來輔助擴(kuò)容，擴(kuò)容完成后會將tab指向新的table，然后繼續(xù)執(zhí)行for循環(huán)。

  • 3.4 除上面三種以外情況

    說明f節(jié)點是一個鏈表的頭結(jié)點或者是紅黑樹的根節(jié)點，那么對f加sychronize同步鎖，然后進(jìn)行以下判斷：

    • f.hash > 0

      如果是f的hash值大于0，當(dāng)前數(shù)組下標(biāo)存儲的是一個鏈表，f是鏈表的頭結(jié)點。

      對鏈表進(jìn)行遍歷，如果有節(jié)點跟當(dāng)前需要插入節(jié)點的hash值相同，那么對節(jié)點的value進(jìn)行更新，否則根據(jù)key，value創(chuàng)建一個Node<K,V>，添加到鏈表末尾。

    • f instanceof TreeBin

如果f是TreeBin類型，那么說明當(dāng)前數(shù)組下標(biāo)存儲的是一個紅黑樹，f是紅黑樹的根節(jié)點，調(diào)用putTreeVal方法，插入或更新節(jié)點。
  • 插入完成后，判斷binCount（數(shù)組下標(biāo)存儲是一個鏈表時，binCount是鏈表長度），當(dāng)binCount超過8時，并且數(shù)組的長度大于64時，那么調(diào)用treeifyBin方法將鏈表轉(zhuǎn)換為紅黑樹。最后break出for循環(huán)。

PS：

很多技術(shù)文章都是說鏈表長度大于8就轉(zhuǎn)換為紅黑樹，我當(dāng)時也沒有注意這個細(xì)節(jié)，直到有個群里的朋友指正，當(dāng)原來的鏈表長度超過8時，確實會調(diào)用treeifyBin方法，但是在treeifyBin方法中會判斷當(dāng)前tab是否為空，或者數(shù)組長度是否小于64，如果滿足條件，那么調(diào)用resize方法對tab初始化或者擴(kuò)容，就不會將鏈表轉(zhuǎn)換為紅黑樹了。

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

image

<figcaption style="box-sizing: border-box; display: block; text-align: center; font-size: 0.8em; line-height: 2em; color: rgb(144, 144, 144);"></figcaption>

treeifyBin方法的源碼： MIN_TREEIFY_CAPACITY是64

image

4.判斷是否需要擴(kuò)容

調(diào)用addCount()對當(dāng)前數(shù)組長度加1，在addCount()方法中，會判斷當(dāng)前元素個數(shù)是否超過sizeCtl(擴(kuò)容閾值，總長度*0.75)，如果是，那么會進(jìn)行擴(kuò)容，如果正處于擴(kuò)容過程中，當(dāng)前線程會輔助擴(kuò)容。

HashMap與HashTable，ConcurrentHashMap的區(qū)別是什么？

主要從底層數(shù)據(jù)結(jié)構(gòu)，線程安全，執(zhí)行效率，是否允許Null值，初始容量及擴(kuò)容，hash值計算來進(jìn)行分析。

1.底層數(shù)據(jù)結(jié)構(gòu)

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

HashMap=數(shù)組+鏈表+紅黑樹

HashMap的底層數(shù)據(jù)結(jié)構(gòu)是一個數(shù)組+鏈表+紅黑樹，數(shù)組的每個元素存儲是一個鏈表的頭結(jié)點，鏈表中存儲了一組哈希值沖突的鍵值對，通過鏈地址法來解決哈希沖突的。為了避免鏈表長度過長，影響查找元素的效率，當(dāng)鏈表的長度>8時，會將鏈表轉(zhuǎn)換為紅黑樹，鏈表的長度<6時，將紅黑樹轉(zhuǎn)換為鏈表。之所以臨界點為8是因為紅黑樹的查找時間復(fù)雜度為logN，鏈表的平均時間查找復(fù)雜度為N/2，當(dāng)N為8時，logN為3，是小于N/2的，正好可以通過轉(zhuǎn)換為紅黑樹減少查找的時間復(fù)雜度。

Hashtable=數(shù)組+鏈表

Hashtable底層數(shù)據(jù)結(jié)構(gòu)跟HashMap一致，底層數(shù)據(jù)結(jié)構(gòu)是一個數(shù)組+鏈表，也是通過鏈地址法來解決沖突，只是鏈表過長時，不會轉(zhuǎn)換為紅黑樹來減少查找時的時間復(fù)雜度。Hashtable屬于歷史遺留類，實際開發(fā)中很少使用。

ConcurrentHashMap=數(shù)組+鏈表+紅黑樹

ConcurrentHashMap底層數(shù)據(jù)結(jié)構(gòu)跟HashMap一致，底層數(shù)據(jù)結(jié)構(gòu)是一個數(shù)組+鏈表+紅黑樹。只不過使用了volatile來進(jìn)行修飾它的屬性，來保證內(nèi)存可見性(一個線程修改了這些屬性后，會使得其他線程中對于該屬性的緩存失效，以便下次讀取時取最新的值)。

2.線程安全

HashMap 非線程安全

HashMap是非線程安全的。（例如多個線程插入多個鍵值對，如果兩個鍵值對的key哈希沖突，可能會使得兩個線程在操作同一個鏈表中的節(jié)點，導(dǎo)致一個鍵值對的value被覆蓋）

HashMap 非線程安全

HashTable是線程安全的，主要通過使用synchronized關(guān)鍵字修飾大部分方法，使得每次只能一個線程對HashTable進(jìn)行同步修改，性能開銷較大。

ConcurrentHashMap 線程安全

ConcurrentHashMap是線程安全的，主要是通過CAS操作+synchronized來保證線程安全的。

CAS操作

往ConcurrentHashMap中插入新的鍵值對時，如果對應(yīng)的數(shù)組下標(biāo)元素為null，那么通過CAS操作原子性地將節(jié)點設(shè)置到數(shù)組中。

//這是添加新的鍵值對的方法
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; // 因為對應(yīng)的數(shù)組下標(biāo)元素為null，所以null作為預(yù)期值，new Node<K,V>(hash, key, value, null)作為即將更新的值，只有當(dāng)內(nèi)存中的值與即將預(yù)期值一致時，才會進(jìn)行更新，保證原子性。
  }
...其他代碼
}
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中插入新的鍵值對時，如果對應(yīng)的數(shù)組下標(biāo)元素不為null，那么會對數(shù)組下標(biāo)存儲的元素(也就是鏈表的頭節(jié)點)加synchronized鎖， 然后進(jìn)行插入操作，

Node<K,V> f = tabAt(tab, i = (n - 1) & hash));
synchronized (f) {//f就是數(shù)組下標(biāo)存儲的元素
    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.執(zhí)行效率

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

4.是否允許null值出現(xiàn)

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

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

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

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方法中會進(jìn)行判斷，為null會拋出空指針異常。

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

5.初始容量及擴(kuò)容

不指定初始容量

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

不指定初始容量

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

擴(kuò)容

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

6.hash值計算

HashTable會擴(kuò)容為2n+1，HashTable之所以容量取11，及擴(kuò)容時是是2n+1，是為了保證 HashTable的長度是一個素數(shù)，因為數(shù)組的下標(biāo)是用key的hashCode與數(shù)組的長度取模進(jìn)行計算得到的，而當(dāng)數(shù)組的長度是素數(shù)時，可以保證計算得到的數(shù)組下標(biāo)分布得更加均勻，可以看看這篇文章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位進(jìn)行異或運(yùn)算(這樣可以保留高位的特征，避免一些key的hashCode高位不同，低位相同，造成hash沖突)，得到hash值，然后將hash&(n-1)計算得到數(shù)組下標(biāo)。（n為數(shù)組的長度，因為當(dāng)n為2的整數(shù)次冪時，hash mod n的結(jié)果在數(shù)學(xué)上等于hash&(n-1)，而且計算機(jī)進(jìn)行&運(yùn)算更快，所以這也是HashMap的長度總是設(shè)置為2的整數(shù)次冪的原因）

//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擴(kuò)容后是否需要rehash？

在JDK1.8以后，不需要rehash，因為鍵值對的Hash值主要是根據(jù)key的hashCode()的高16位與低16位進(jìn)行異或計算后得到，根據(jù)hash%length，計算得到數(shù)組的下標(biāo)index，因為length是2的整數(shù)次冪，當(dāng)擴(kuò)容后length變?yōu)樵瓉淼膬杀稌r，hash%(2*length)的計算結(jié)果結(jié)果差別在于第length位的值是1還是0，如果是0，那么在新數(shù)組中的index與舊數(shù)組的一直，如果是1，在新數(shù)組中的index會是舊數(shù)組中的數(shù)組中的index+length。

HashMap擴(kuò)容是怎樣擴(kuò)容的，為什么都是2的N次冪的大?。?/h3>

觸發(fā)擴(kuò)容

在沒有指定初始長度的情況下，HashMap數(shù)組的默認(rèn)長度為16，在添加一個新的鍵值對時，會調(diào)用putVal()方法，在方法中，成功添加一個新的鍵值對以后，會判斷當(dāng)前的元素個數(shù)是否超過閥值(數(shù)組長度*負(fù)載因子0.75)，如果超過那么調(diào)用resize方法進(jìn)行擴(kuò)容。具體的擴(kuò)容步驟如下：

計算擴(kuò)容后的長度

  • 如果當(dāng)前table為null

    那么直接初始化一個數(shù)組長度為16的數(shù)組返回。

  • 如果當(dāng)前table的length已經(jīng)大于HashMap指定的最大值2的30次方

    那么直接返回舊table，不進(jìn)行擴(kuò)容。

  • 其他情況

    將table的length擴(kuò)容為2倍，然后計算新的擴(kuò)容閥值（新數(shù)組長度*0.75）。

初始化新數(shù)組

會根據(jù)擴(kuò)容后的數(shù)組長度初始化話一個新的數(shù)組，并且直接賦值給當(dāng)前hashMap的成員變量table。

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

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

（與之相反，HashTable在解決擴(kuò)容時其他線程訪問的問題，是通過對大部分方法使用sychronized關(guān)鍵字修飾，也就是某個線程在執(zhí)行擴(kuò)容方法時，會對HashTable對象加鎖，其他線程無法訪問HashTable。ConcurrentHashMap在解決擴(kuò)容時其他線程訪問的問題，是通過設(shè)置ForwardingNode標(biāo)識節(jié)點來解決的，擴(kuò)容時，某個線程對數(shù)組中某個下標(biāo)下所有Hash沖突的元素進(jìn)行遷移時，那么會將數(shù)組下標(biāo)的數(shù)組元素設(shè)置為一個標(biāo)識節(jié)點ForwardingNode，之后其他線程在訪問時，如果發(fā)現(xiàn)key的hash值映射的數(shù)組下標(biāo)對應(yīng)是一個標(biāo)識節(jié)點ForwardingNode（ForwardingNode繼承于普通Node，區(qū)別字啊呀這個節(jié)點的hash值會設(shè)置為-1，并且會多一個指向擴(kuò)容過程中新tab的指針nextTable），那么會根據(jù)ForwardingNode中的nextTable變量，去新的tab中查找元素。（如果是添加新的鍵值對時發(fā)現(xiàn)是ForwardingNode，那么輔助擴(kuò)容或阻塞等待，擴(kuò)容完成后去新數(shù)組中更新或插入元素）

遷移元素

因為HashMap的數(shù)組長度總是2的N次冪，擴(kuò)容后也是變?yōu)樵瓉淼?倍，所以有一個數(shù)學(xué)公式，當(dāng)length為2的N次冪時，

hash%length=hash&(length-1)

而因為length是2的N次冪，length-1在二進(jìn)制中其實是N-1個1。例如：

length為16，length用2進(jìn)制表示是10000，

length-1是15，用2進(jìn)制表示是1111，

2*length為32，length用2進(jìn)制表示是100000，

2*length-1為31，length用2進(jìn)制表示是11111，

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

假設(shè)原數(shù)組長度為16，length-1二進(jìn)制表示為1111。key1的hash值為9，二進(jìn)制表示為01001，key2的hash值為25，11001，

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

擴(kuò)容后數(shù)組長度為32，length-1二進(jìn)制表示為11111，key1的hash值為9，二進(jìn)制表示為01001，key2的hash值為25，11001，

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

所以原數(shù)組同一下標(biāo)index下的鏈表存儲的hash沖突的元素，擴(kuò)容后在新數(shù)組中的下標(biāo)newIndex要么為index，要么為index+length（去決定于hash值的第N位為1，還是0，也就是hash&length的結(jié)果，原數(shù)組長度length為2的N-1次冪）

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

ConcurrentHashMap是怎么記錄元素個數(shù)size的？

HashMap默認(rèn)是非線程安全的，可以認(rèn)為每次只有一個線程來執(zhí)行操作，所以hashMap就使用一個很簡單的int類型的size變量來記錄HashMap鍵值對數(shù)量就行了。

HashMap記錄鍵值對數(shù)量的實現(xiàn)如下：

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

ConcurrentHashMap記錄鍵值對數(shù)量的實現(xiàn)如下：

//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數(shù)組中每個元素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 //這個注解可以避免偽共享，提升性能。加與不加，性能差距達(dá)到了 5 倍。在緩存系統(tǒng)中，由于一個緩存行是出于32-256個字節(jié)之間，常見的緩存行為64個字節(jié)。而一般的變量可能達(dá)不到那么多字節(jié)，所以會出現(xiàn)多個相互獨立的變量存儲在一個緩存行中的情況，此時即便多線程訪問緩存行上相互獨立變量時，也涉及到并發(fā)競爭，會有性能開銷，加了@sun.misc.Contended這個注解，在jDK8中，會對對象前后都增加128字節(jié)的padding，使用2倍于大多數(shù)硬件緩存行的大小來避免相鄰扇區(qū)預(yù)取導(dǎo)致的偽共享沖突。
static final class CounterCell {
    volatile long value;
    CounterCell(long x) { value = x; }
}

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

為什么ConcurrentHashMap，HashTable不支持key，value為null？

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

HashSet和HashMap的區(qū)別？

HashMap主要是用于存儲非重復(fù)鍵值對，HashSet存儲非重復(fù)的對象。雖然HashMap是繼承于AbstractMap，實現(xiàn)了Map接口，HashSet繼承于AbstractSet，實現(xiàn)了Set接口。但是由于它們都有去重的需求，所以HashSet主要實現(xiàn)都是基于HashMap的（如果需要復(fù)用一個類，我們可以使用繼承模式，也可以使用組合模式。組合模式就是將一個類作為新類的組成部分，以此來達(dá)到復(fù)用的目的。）例如，在HashSet類中，有一個HashMap類型的成員變量map，這就是組合模式的應(yīng)用。

    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的構(gòu)造方法中，創(chuàng)建了一個HashMap，賦值給map屬性，之后在添加元素時，就是將元素作為key添加到HashMap中，只不過value是一個占位對象PRESENT。除了 clone()、writeObject()、readObject()是 HashSet 自己不得不實現(xiàn)之外，其他方法都是直接調(diào)用 HashMap 中的方法。那么HashMap又是如何實現(xiàn)key不重復(fù)的呢？

在調(diào)用HashMap的putVal方法添加新的鍵值對時，會進(jìn)行如下操作：

1.根據(jù)key計算hash值。

2.根據(jù)hash值映射數(shù)組下標(biāo)，然后獲取數(shù)組下標(biāo)的對應(yīng)的元素。

3.數(shù)組下標(biāo)存儲的是一個鏈表，鏈表包含了哈希沖突的元素，會對鏈表進(jìn)行遍歷，判斷hash1==hash2，除此以外，還必須要key1==key2，或者key1.equals(key2)。

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

==是判斷兩個變量或?qū)嵗遣皇侵赶蛲粋€內(nèi)存地址，如果是同一個內(nèi)存地址，對象肯定相等。

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

HashMap遍歷時刪除元素的有哪些實現(xiàn)方法？

首先結(jié)論如下：

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

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

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

下面讓我們來詳細(xì)探究一下原因吧！

HashMap的遍歷刪除方法與ArrayList的大同小異，只是api的調(diào)用方式不同。首先初始化一個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()刪除(結(jié)果：拋出異常)

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

}

輸出結(jié)果：

當(dāng)前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 當(dāng)前entry是key1=1
當(dāng)前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 當(dāng)前entry是key2=2
當(dāng)前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 當(dāng)前entry是key5=5
當(dāng)前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 當(dāng)前entry是key6=6
當(dāng)前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4} 當(dāng)前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()刪除(結(jié)果：拋出異常)

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

輸出結(jié)果如下：

當(dāng)前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 當(dāng)前key是key1
當(dāng)前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 當(dāng)前key是key2
當(dāng)前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 當(dāng)前key是key5
當(dāng)前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 當(dāng)前key是key6
當(dāng)前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4} 當(dāng)前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()遍歷刪除(結(jié)果：正確刪除)

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("當(dāng)前HashMap是"+hashMap+" 當(dāng)前entry是"+entry);
}

輸出結(jié)果：

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

第1種方法和第2種方法拋出ConcurrentModificationException異常與上面ArrayList錯誤遍歷-刪除方法的原因一致，HashIterator也有一個expectedModCount，在遍歷時獲取下一個元素時，會調(diào)用next()方法，然后對
expectedModCount和modCount進(jìn)行判斷，不一致就拋出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是什么？

根據(jù)ConcurrentModificationException的文檔介紹，一些對象不允許并發(fā)修改，當(dāng)這些修改行為被檢測到時，就會拋出這個異常。（例如一些集合不允許一個線程一邊遍歷時，另一個線程去修改這個集合）。

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

異常檢測主要是通過modCount和expectedModCount兩個變量來實現(xiàn)的，

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

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

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

單線程操作Iterator不當(dāng)時也會拋出ConcurrentModificationException異常。（上面的例子就是）

總結(jié)

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

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

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容