面渣逆襲：HashMap追魂二十三問

大家好，我是老三。

HashMap作為我們熟悉的一種集合，可以說是面試必考題。簡單的使用，再到原理、數據結構，還可以延伸到並發，可以說，就一個HashMap，能聊半個小時。

1.能說一下HashMap的數據結構嗎？

JDK1.7的數據結構是數組+鏈表，JDK1.7還有人在用？不會吧……

說一下JDK1.8的數據結構吧：

JDK1.8的數據結構是數組+鏈表+紅黑樹。

數據結構示意圖如下：

jdk1.8 hashmap數據結構示意圖

其中，桶數組是用來存儲數據元素，鏈表是用來解決衝突，紅黑樹是為了提高查詢的效率。

  • 數據元素通過映射關係，也就是散列函數，映射到桶數組對應索引的位置
  • 如果發生衝突，從衝突的位置拉一個鏈表，插入衝突的元素
  • 如果鏈表長度>8&數組大小>=64，鏈錶轉為紅黑樹
  • 如果紅黑樹節點個數<6 ，轉為鏈表

2.你對紅黑樹了解多少？為什麼不用二叉樹/平衡樹呢？

紅黑樹本質上是一種二叉查找樹，為了保持平衡，它又在二叉查找樹的基礎上增加了一些規則：

  1. 每個節點要麼是紅色，要麼是黑色；
  2. 根節點永遠是黑色的；
  3. 所有的葉子節點都是是黑色的（注意這裡說葉子節點其實是圖中的 NULL 節點）；
  4. 每個紅色節點的兩個子節點一定都是黑色；
  5. 從任一節點到其子樹中每個葉子節點的路徑都包含相同數量的黑色節點；

紅黑樹

之所以不用二叉樹：

紅黑樹是一種平衡的二叉樹，插入、刪除、查找的最壞時間複雜度都為 O(logn)，避免了二叉樹最壞情況下的O(n)時間複雜度。

之所以不用平衡二叉樹：

平衡二叉樹是比紅黑樹更嚴格的平衡樹，為了保持保持平衡，需要旋轉的次數更多，也就是說平衡二叉樹保持平衡的效率更低，所以平衡二叉樹插入和刪除的效率比紅黑樹要低。

3.紅黑樹怎麼保持平衡的知道嗎？

紅黑樹有兩種方式保持平衡：旋轉和染色。

  • 旋轉：旋轉分為兩種，左旋和右旋

左旋

右旋

  • 染⾊：

染色

4.HashMap的put流程知道嗎？

先上個流程圖吧:

HashMap插入數據流程圖

  1. 首先進行哈希值的擾動，獲取一個新的哈希值。(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

  2. 判斷tab是否位空或者長度為0，如果是則進行擴容操作。

    if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

  3. 根據哈希值計算下標，如果對應小標正好沒有存放數據，則直接插入即可否則需要覆蓋。tab[i = (n - 1) & hash])

  4. 判斷tab[i]是否為樹節點，否則向鏈表中插入數據，是則向樹中插入節點。

  5. 如果鏈表中插入節點的時候，鏈表長度大於等於8，則需要把鏈錶轉換為紅黑樹。treeifyBin(tab, hash);

  6. 最後所有元素處理完成後，判斷是否超過閾值；threshold，超過則擴容。

5.HashMap怎麼查找元素的呢？

先看流程圖：

HashMap查找流程圖

HashMap的查找就簡單很多：

  1. 使用擾動函數，獲取新的哈希值
  2. 計算數組下標，獲取節點
  3. 當前節點和key匹配，直接返回
  4. 否則，當前節點是否為樹節點，查找紅黑樹
  5. 否則，遍歷鏈表查找

6.HashMap的哈希/擾動函數是怎麼設計的?

HashMap的哈希函數是先拿到 key 的hashcode，是一個32位的int類型的數值，然後讓hashcode的高16位和低16位進行異或操作。

    static final int hash(Object key) {
        int h;
        // key的hashCode和key的hashCode右移16位做異或運算
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

這麼設計是為了降低哈希碰撞的概率。

7.為什麼哈希/擾動函數能降hash碰撞？

因為 key.hashCode() 函數調用的是 key 鍵值類型自帶的哈希函數，返回 int 型散列值。int 值範圍為 -2147483648~2147483647，加起來大概 40 億的映射空間。

只要哈希函數映射得比較均勻鬆散，一般應用是很難出現碰撞的。但問題是一個 40 億長度的數組，內存是放不下的。

假如 HashMap 數組的初始大小才 16，就需要用之前需要對數組的長度取模運算，得到的餘數才能用來訪問數組下標。

源碼中模運算就是把散列值和數組長度 – 1 做一個 “與&” 操作，位運算比取余 % 運算要快。

bucketIndex = indexFor(hash, table.length);

static int indexFor(int h, int length) {
     return h & (length-1);
}

順便說一下，這也正好解釋了為什麼 HashMap 的數組長度要取 2 的整數冪。因為這樣（數組長度 – 1）正好相當於一個 「低位掩碼」。與 操作的結果就是散列值的高位全部歸零，只保留低位值，用來做數組下標訪問。以初始長度 16 為例，16-1=15。2 進制表示是 0000 0000 0000 0000 0000 0000 0000 1111。和某個散列值做 與 操作如下，結果就是截取了最低的四位值。

哈希&運算

這樣是要快捷一些，但是新的問題來了，就算散列值分佈再鬆散，要是只取最後幾位的話，碰撞也會很嚴重。如果散列本身做得不好，分佈上成等差數列的漏洞，如果正好讓最後幾個低位呈現規律性重複，那就更難搞了。

這時候 擾動函數 的價值就體現出來了，看一下擾動函數的示意圖：

擾動函數示意圖

右移 16 位，正好是 32bit 的一半，自己的高半區和低半區做異或，就是為了混合原始哈希碼的高位和低位，以此來加大低位的隨機性。而且混合後的低位摻雜了高位的部分特徵，這樣高位的信息也被變相保留下來。

8.為什麼HashMap的容量是2的倍數呢？

  • 第一個原因是為了方便哈希取余：

將元素放在table數組上面，是用hash值%數組大小定位位置，而HashMap是用hash值&(數組大小-1)，卻能和前面達到一樣的效果，這就得益於HashMap的大小是2的倍數，2的倍數意味着該數的二進制位只有一位為1，而該數-1就可以得到二進制位上1變成0，後面的0變成1，再通過&運算，就可以得到和%一樣的效果，並且位運算比%的效率高得多

HashMap的容量是2的n次冪時，(n-1)的2進制也就是1111111***111這樣形式的，這樣與添加元素的hash值進行位運算時，能夠充分的散列，使得添加的元素均勻分佈在HashMap的每個位置上，減少hash碰撞。

  • 第二個方面是在擴容時，利用擴容後的大小也是2的倍數，將已經產生hash碰撞的元素完美的轉移到新的table中去

我們可以簡單看看HashMap的擴容機制，HashMap中的元素在超過負載因子*HashMap大小時就會產生擴容。

put中的擴容

9.如果初始化HashMap，傳一個17的值new HashMap<>，它會怎麼處理？

簡單來說，就是初始化時，傳的不是2的倍數時，HashMap會向上尋找離得最近的2的倍數，所以傳入14，但HashMap的實際容量是32。

我們來看看詳情，在HashMap的初始化中，有這樣⼀段⽅法；

public HashMap(int initialCapacity, float loadFactor) {
 ...
 this.loadFactor = loadFactor;
 this.threshold = tableSizeFor(initialCapacity);
}
  • 閥值 threshold ，通過⽅法 tableSizeFor 進⾏計算，是根據初始化傳的參數來計算的。
  • 同時，這個⽅法也要要尋找⽐初始值⼤的，最⼩的那個2進制數值。⽐如傳了17，我應該找到的是32。
static final int tableSizeFor(int cap) {
 int n = cap - 1;
 n |= n >>> 1;
 n |= n >>> 2;
 n |= n >>> 4;
 n |= n >>> 8;
 n |= n >>> 16;
 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
  • MAXIMUM_CAPACITY = 1 << 30，這個是臨界範圍，也就是最⼤的Map集合。
  • 計算過程是向右移位1、2、4、8、16，和原來的數做|運算，這主要是為了把⼆進制的各個位置都填上1，當⼆進制的各個位置都是1以後，就是⼀個標準的2的倍數減1了，最後把結果加1再返回即可。

以17為例，看一下初始化計算table容量的過程：

容量計算

10.你還知道哪些哈希函數的構造方法呢？

HashMap里哈希構造函數的方法叫：

  • 除留取余法：H（key)=key%p（p<=N）,關鍵字除以一個不大於哈希表長度的正整數p，所得餘數為地址，當然HashMap里進行了優化改造，效率更高，散列也更均衡。

除此之外，還有這幾種常見的哈希函數構造方法：

  • 直接定址法

    直接根據key來映射到對應的數組位置，例如1232放到下標1232的位置。

  • 數字分析法

    取key的某些數字（例如十位和百位）作為映射的位置

  • 平方取中法

    取key平方的中間幾位作為映射的位置

  • 摺疊法

    將key分割成位數相同的幾段，然後把它們的疊加和作為映射的位置

散列函數構造

11.解決哈希衝突有哪些方法呢？

我們到現在已經知道，HashMap使用鏈表的原因為了處理哈希衝突，這種方法就是所謂的：

  • 鏈地址法：在衝突的位置拉一個鏈表，把衝突的元素放進去。

除此之外，還有一些常見的解決衝突的辦法：

  • 開放定址法：開放定址法就是從衝突的位置再接着往下找，給衝突元素找個空位。

    找到空閑位置的方法也有很多種：

    • 線行探查法: 從衝突的位置開始，依次判斷下一個位置是否空閑，直至找到空閑位置
    • 平方探查法: 從衝突的位置x開始，第一次增加1^2個位置，第二次增加2^2…，直至找到空閑的位置
    • ……

開放定址法

  • 再哈希法：換種哈希函數，重新計算衝突元素的地址。
  • 建立公共溢出區：再建一個數組，把衝突的元素放進去。

12.為什麼HashMap鏈錶轉紅黑樹的閾值為8呢？

樹化發生在table數組的長度大於64，且鏈表的長度大於8的時候。

為什麼是8呢？源碼的注釋也給出了答案。

源碼注釋

紅黑樹節點的大小大概是普通節點大小的兩倍，所以轉紅黑樹，犧牲了空間換時間，更多的是一種兜底的策略，保證極端情況下的查找效率。

閾值為什麼要選8呢？和統計學有關。理想情況下，使用隨機哈希碼，鏈表裡的節點符合泊松分佈，出現節點個數的概率是遞減的，節點個數為8的情況，發生概率僅為0.00000006。

至於紅黑樹轉回鏈表的閾值為什麼是6，而不是8？是因為如果這個閾值也設置成8，假如發生碰撞，節點增減剛好在8附近，會發生鏈表和紅黑樹的不斷轉換，導致資源浪費。

13.擴容在什麼時候呢？為什麼擴容因子是0.75？

為了減少哈希衝突發生的概率，噹噹前HashMap的元素個數達到一個臨界值的時候，就會觸發擴容，把所有元素rehash之後再放在擴容後的容器中，這是一個相當耗時的操作。

put時，擴容

而這個臨界值threshold就是由加載因子和當前容器的容量大小來確定的，假如採用默認的構造方法：

臨界值（threshold ）= 默認容量（DEFAULT_INITIAL_CAPACITY） * 默認擴容因子（DEFAULT_LOAD_FACTOR）

threshold計算

那就是大於16x0.75=12時，就會觸發擴容操作。

那麼為什麼選擇了0.75作為HashMap的默認加載因子呢？

簡單來說，這是對空間成本和時間成本平衡的考慮。

在HashMap中有這樣一段注釋：

關於默認負載因子的注釋

我們都知道，HashMap的散列構造方式是Hash取余，負載因子決定元素個數達到多少時候擴容。

假如我們設的比較大，元素比較多，空位比較少的時候才擴容，那麼發生哈希衝突的概率就增加了，查找的時間成本就增加了。

我們設的比較小的話，元素比較少，空位比較多的時候就擴容了，發生哈希碰撞的概率就降低了，查找時間成本降低，但是就需要更多的空間去存儲元素，空間成本就增加了。

14.那擴容機制了解嗎？

HashMap是基於數組+鏈表和紅黑樹實現的，但用於存放key值的桶數組的長度是固定的，由初始化參數確定。

那麼，隨着數據的插入數量增加以及負載因子的作用下，就需要擴容來存放更多的數據。而擴容中有一個非常重要的點，就是jdk1.8中的優化操作，可以不需要再重新計算每一個元素的哈希值。

因為HashMap的初始容量是2的次冪，擴容之後的長度是原來的二倍，新的容量也是2的次冪，所以，元素，要麼在原位置，要麼在原位置再移動2的次冪。

看下這張圖，n為table的長度，圖a表示擴容前的key1和key2兩種key確定索引的位置，圖b表示擴容後key1和key2兩種key確定索引位置。

擴容之後的索引計算

元素在重新計算hash之後，因為n變為2倍，那麼n-1的mask範圍在高位多1bit(紅色)，因此新的index就會發生這樣的變化：

擴容位置變化

所以在擴容時，只需要看原來的hash值新增的那一位是0還是1就行了，是0的話索引沒變，是1的化變成原索引+oldCap，看看如16擴容為32的示意圖：

擴容節點遷移示意圖

擴容節點遷移主要邏輯：

擴容主要邏輯

15.jdk1.8對HashMap主要做了哪些優化呢？為什麼？

jdk1.8 的HashMap主要有五點優化：

  1. 數據結構：數組 + 鏈表改成了數組 + 鏈表或紅黑樹

    原因：發生 hash 衝突，元素會存入鏈表，鏈表過長轉為紅黑樹，將時間複雜度由O(n)降為O(logn)

  2. 鏈表插入方式：鏈表的插入方式從頭插法改成了尾插法

    簡單說就是插入時，如果數組位置上已經有元素，1.7 將新元素放到數組中，原始節點作為新節點的後繼節點，1.8 遍歷鏈表，將元素放置到鏈表的最後。

    原因：因為 1.7 頭插法擴容時，頭插法會使鏈表發生反轉，多線程環境下會產生環。

  3. 擴容rehash：擴容的時候 1.7 需要對原數組中的元素進行重新 hash 定位在新數組的位置，1.8 採用更簡單的判斷邏輯，不需要重新通過哈希函數計算位置，新的位置不變或索引 + 新增容量大小。

    原因：提高擴容的效率，更快地擴容。

  4. 擴容時機：在插入時，1.7 先判斷是否需要擴容，再插入，1.8 先進行插入，插入完成再判斷是否需要擴容；

  5. 散列函數：1.7 做了四次移位和四次異或，jdk1.8隻做一次。

    原因：做 4 次的話，邊際效用也不大，改為一次，提升效率。

16.你能自己設計實現一個HashMap嗎？

這道題快手常考。

不要慌，紅黑樹版咱們多半是寫不出來，但是數組+鏈表版還是問題不大的，詳細可見： 手寫HashMap，快手面試官直呼內行！。

整體的設計：

  • 散列函數：hashCode()+除留餘數法
  • 衝突解決：鏈地址法
  • 擴容：節點重新hash獲取位置

自定義HashMap整體結構

完整代碼：

完整代碼

17.HashMap 是線程安全的嗎？多線程下會有什麼問題？

HashMap不是線程安全的，可能會發生這些問題：

  • 多線程下擴容死循環。JDK1.7 中的 HashMap 使用頭插法插入元素，在多線程的環境下，擴容的時候有可能導致環形鏈表的出現，形成死循環。因此，JDK1.8 使用尾插法插入元素，在擴容時會保持鏈表元素原本的順序，不會出現環形鏈表的問題。

  • 多線程的 put 可能導致元素的丟失。多線程同時執行 put 操作，如果計算出來的索引位置是相同的，那會造成前一個 key 被後一個 key 覆蓋，從而導致元素的丟失。此問題在 JDK 1.7 和 JDK 1.8 中都存在。

  • put 和 get 並發時，可能導致 get 為 null。線程 1 執行 put 時，因為元素個數超出 threshold 而導致 rehash，線程 2 此時執行 get，有可能導致這個問題。這個問題在 JDK 1.7 和 JDK 1.8 中都存在。

18.有什麼辦法能解決HashMap線程不安全的問題呢？

Java 中有 HashTable、Collections.synchronizedMap、以及 ConcurrentHashMap 可以實現線程安全的 Map。

  • HashTable 是直接在操作方法上加 synchronized 關鍵字，鎖住整個table數組，粒度比較大；
  • Collections.synchronizedMap 是使用 Collections 集合工具的內部類，通過傳入 Map 封裝出一個 SynchronizedMap 對象，內部定義了一個對象鎖，方法內通過對象鎖實現；
  • ConcurrentHashMap 在jdk1.7中使用分段鎖，在jdk1.8中使用CAS+synchronized。

19.能具體說一下ConcurrentHashmap的實現嗎？

ConcurrentHashmap線程安全在jdk1.7版本是基於分段鎖實現，在jdk1.8是基於CAS+synchronized實現。

1.7分段鎖

從結構上說，1.7版本的ConcurrentHashMap採用分段鎖機制，裏面包含一個Segment數組，Segment繼承於ReentrantLock，Segment則包含HashEntry的數組，HashEntry本身就是一個鏈表的結構，具有保存key、value的能力能指向下一個節點的指針。

實際上就是相當於每個Segment都是一個HashMap，默認的Segment長度是16，也就是支持16個線程的並發寫，Segment之間相互不會受到影響。

1.7ConcurrentHashMap示意圖

put流程

整個流程和HashMap非常類似，只不過是先定位到具體的Segment，然後通過ReentrantLock去操作而已，後面的流程，就和HashMap基本上是一樣的。

  1. 計算hash，定位到segment，segment如果是空就先初始化
  2. 使用ReentrantLock加鎖，如果獲取鎖失敗則嘗試自旋，自旋超過次數就阻塞獲取，保證一定獲取鎖成功
  3. 遍歷HashEntry，就是和HashMap一樣，數組中key和hash一樣就直接替換，不存在就再插入鏈表，鏈表同樣操作

jdk1.7 put流程

get流程

get也很簡單，key通過hash定位到segment，再遍歷鏈表定位到具體的元素上，需要注意的是value是volatile的，所以get是不需要加鎖的。

1.8 CAS+synchronized

jdk1.8實現線程安全不是在數據結構上下功夫，它的數據結構和HashMap是一樣的，數組+鏈表+紅黑樹。它實現線程安全的關鍵點在於put流程。

put流程

  1. 首先計算hash，遍歷node數組，如果node是空的話，就通過CAS+自旋的方式初始化
 tab = initTable();

node數組初始化：

    private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) {
            //如果正在初始化或者擴容
            if ((sc = sizeCtl) < 0)
                //等待
                Thread.yield(); // lost initialization race; just spin
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {   //CAS操作
                try {
                    if ((tab = table) == null || tab.length == 0) {
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = tab = nt;
                        sc = n - (n >>> 2);
                    }
                } finally {
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }

2.如果當前數組位置是空則直接通過CAS自旋寫入數據

    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);
    }
  1. 如果hash==MOVED，說明需要擴容，執行擴容
else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);

    final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
        Node<K,V>[] nextTab; int sc;
        if (tab != null && (f instanceof ForwardingNode) &&
            (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
            int rs = resizeStamp(tab.length);
            while (nextTab == nextTable && table == tab &&
                   (sc = sizeCtl) < 0) {
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || transferIndex <= 0)
                    break;
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                    transfer(tab, nextTab);
                    break;
                }
            }
            return nextTab;
        }
        return table;
    }
  1. 如果都不滿足，就使用synchronized寫入數據，寫入數據同樣判斷鏈表、紅黑樹，鏈表寫入和HashMap的方式一樣，key hash一樣就覆蓋，反之就尾插法，鏈表長度超過8就轉換成紅黑樹
 synchronized (f){
     ……
 }

ConcurrentHashmap jdk1.8put流程

get查詢

get很簡單，和HashMap基本相同，通過key計算位置，table該位置key相同就返回，如果是紅黑樹按照紅黑樹獲取，否則就遍歷鏈表獲取。

20.HashMap 內部節點是有序的嗎？

HashMap是無序的，根據 hash 值隨機插入。如果想使用有序的Map，可以使用LinkedHashMap 或者 TreeMap。

21.講講 LinkedHashMap 怎麼實現有序的？

LinkedHashMap維護了一個雙向鏈表，有頭尾節點，同時 LinkedHashMap 節點 Entry 內部除了繼承 HashMap 的 Node 屬性，還有 before 和 after 用於標識前置節點和後置節點。

Entry節點

可以實現按插入的順序或訪問順序排序。

LinkedHashMap實現原理

22.講講 TreeMap 怎麼實現有序的？

TreeMap 是按照 Key 的自然順序或者 Comprator 的順序進行排序，內部是通過紅黑樹來實現。所以要麼 key 所屬的類實現 Comparable 接口，或者自定義一個實現了 Comparator 接口的比較器，傳給 TreeMap 用於 key 的比較。

TreeMap

23.講講HashSet的底層實現？

HashSet 底層就是基於 HashMap 實現的。（ HashSet 的源碼⾮常⾮常少，因為除了 clone() 、 writeObject() 、 readObject() 是 HashSet⾃⼰不得不實現之外，其他⽅法都是直接調⽤ HashMap 中的⽅法。

HashSet的add方法，直接調用HashMap的put方法，將添加的元素作為key，new一個Object作為value，直接調用HashMap的put方法，它會根據返回值是否為空來判斷是否插入元素成功。

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

HashSet套娃

而在HashMap的putVal方法中，進行了一系列判斷，最後的結果是，只有在key在table數組中不存在的時候，才會返回插入的值。

            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }

參考：

[1]. 一個HashMap跟面試官扯了半個小時

[2]. 《大廠面試》—Java 集合連環30問

[3]. 面經手冊 · 第4篇《HashMap數據插入、查找、刪除、遍歷，源碼分析》

[4]. 《我想進大廠》之Java基礎奪命連環16問

[5]. 數據結構之LinkedHashMap

[6].面經手冊 · 第3篇《HashMap核心知識，擾動函數、負載因子、擴容鏈表拆分，深度學習》

[7]. 面試官：為什麼 HashMap 的加載因子是0.75？

[8]. 面試舊敵之紅黑樹（直白介紹深入理解）

[9]. Java TreeMap工作原理及實現

[10]. 手寫HashMap，快手面試官直呼內行！

[11].Java 8系列之重新認識HashMap

Tags:

VirMach 便宜 VPS

QNews

QNews