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

1.能說一下HashMap的資料結構嗎？

JDK1.7的資料結構是數組+連結清單，JDK1.7還有人在用？不會吧……

說一下JDK1.8的資料結構吧：

JDK1.8的資料結構是數組+連結清單+紅黑樹。

資料結構示意圖如下：

其中，桶數組是用來存儲資料元素，連結清單是用來解決沖突，紅黑樹是為了提高查詢的效率。

資料元素通過映射關系，也就是散列函數，映射到桶數組對應索引的位置
如果發生沖突，從沖突的位置拉一個連結清單，插入沖突的元素
如果連結清單長度>8&數組大小>=64，連結清單轉為紅黑樹
如果紅黑樹節點個數<6 ，轉為連結清單

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

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

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

之是以不用二叉樹：

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

之是以不用平衡二叉樹：

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

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

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

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

染⾊：

4.HashMap的put流程知道嗎？

先上個流程圖吧:

首先進行哈希值的擾動，擷取一個新的哈希值。(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
判斷tab是否位空或者長度為0，如果是則進行擴容操作。
if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; 複制代碼
根據哈希值計算下标，如果對應小标正好沒有存放資料，則直接插入即可否則需要覆寫。tab[i = (n - 1) & hash])
判斷tab[i]是否為樹節點，否則向連結清單中插入資料，是則向樹中插入節點。
如果連結清單中插入節點的時候，連結清單長度大于等于8，則需要把連結清單轉換為紅黑樹。treeifyBin(tab, hash);
最後所有元素處理完成後，判斷是否超過門檻值；threshold，超過則擴容。

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

先看流程圖：

HashMap的查找就簡單很多：

使用擾動函數，擷取新的哈希值
計算數組下标，擷取節點
目前節點和key比對，直接傳回
否則，目前節點是否為樹節點，查找紅黑樹
否則，周遊連結清單查找

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大小時就會産生擴容。

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

簡單來說，就是初始化時，傳的不是2的倍數時，HashMap會向上尋找離得最近的2的倍數，是以傳入17，但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之後再放在擴容後的容器中，這是一個相當耗時的操作。

而這個臨界值threshold就是由加載因子和目前容器的容量大小來确定的，假如采用預設的構造方法：

臨界值（threshold ）= 預設容量（DEFAULT_INITIAL_CAPACITY） * 預設擴容因子（DEFAULT_LOAD_FACTOR）

那就是大于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主要有五點優化：

資料結構：數組 + 連結清單改成了數組 + 連結清單或紅黑樹
原因：發生 hash 沖突，元素會存傳入連結表，連結清單過長轉為紅黑樹，将時間複雜度由O(n)降為O(logn)
連結清單插入方式：連結清單的插入方式從頭插法改成了尾插法
簡單說就是插入時，如果數組位置上已經有元素，1.7 将新元素放到數組中，原始節點作為新節點的後繼節點，1.8 周遊連結清單，将元素放置到連結清單的最後。
原因：因為 1.7 頭插法擴容時，頭插法會使連結清單發生反轉，多線程環境下會産生環。
擴容rehash：擴容的時候 1.7 需要對原數組中的元素進行重新 hash 定位在新數組的位置，1.8 采用更簡單的判斷邏輯，不需要重新通過哈希函數計算位置，新的位置不變或索引 + 新增容量大小。
原因：提高擴容的效率，更快地擴容。
擴容時機：在插入時，1.7 先判斷是否需要擴容，再插入，1.8 先進行插入，插入完成再判斷是否需要擴容；
散列函數：1.7 做了四次移位和四次異或，jdk1.8隻做一次。
原因：做 4 次的話，邊際效用也不大，改為一次，提升效率。

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

這道題快手常考。

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

整體的設計：

散列函數：hashCode()+除留餘數法
沖突解決：鍊位址法
擴容：節點重新hash擷取位置

完整代碼：

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之間互相不會受到影響。

put流程

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

計算hash，定位到segment，segment如果是空就先初始化
使用ReentrantLock加鎖，如果擷取鎖失敗則嘗試自旋，自旋超過次數就阻塞擷取，保證一定擷取鎖成功
周遊HashEntry，就是和HashMap一樣，數組中key和hash一樣就直接替換，不存在就再插傳入連結表，連結清單同樣操作

get流程

get也很簡單，key通過hash定位到segment，再周遊連結清單定位到具體的元素上，需要注意的是value是volatile的，是以get是不需要加鎖的。

1.8 CAS+synchronized

jdk1.8實作線程安全不是在資料結構上下功夫，它的資料結構和HashMap是一樣的，數組+連結清單+紅黑樹。它實作線程安全的關鍵點在于put流程。

put流程

首先計算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);
    }
複制代碼

如果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;
    }
複制代碼

如果都不滿足，就使用synchronized寫入資料，寫入資料同樣判斷連結清單、紅黑樹，連結清單寫入和HashMap的方式一樣，key hash一樣就覆寫，反之就尾插法，連結清單長度超過8就轉換成紅黑樹

synchronized (f){
     ……
 }
複制代碼

get查詢

get很簡單，和HashMap基本相同，通過key計算位置，table該位置key相同就傳回，如果是紅黑樹按照紅黑樹擷取，否則就周遊連結清單擷取。

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

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

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

LinkedHashMap維護了一個雙向連結清單，有頭尾節點，同時 LinkedHashMap 節點 Entry 内部除了繼承 HashMap 的 Node 屬性，還有 before 和 after 用于辨別前置節點和後置節點。

可以實作按插入的順序或通路順序排序。

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

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

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;
    }
複制代碼

而在HashMap的putVal方法中，進行了一系列判斷，最後的結果是，key在HashMap中存在，就會傳回舊值。HashSet add方法就會傳回false。

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

HashMap的追魂二十三問，面渣逆襲必備。