Java 集合框架八股文（理解版）
大家好，我是二哥呀。前面分享了 Java基礎(chǔ)篇、Java并發(fā)篇、Java 虛擬機(jī)的硬核圖文版的高頻面試題，今天我們來補(bǔ)上最后一個(gè)板塊 Java 集合框架（容器），整個(gè) Java 核心板塊就非常完善了。
我寫的這一系列，不是背誦版，是理解版，很多地方都是在講原理，內(nèi)容也比較充足，死記硬背很難，大家一定要去理解性地去記憶。
引言
1.說說有哪些常見集合？
集合相關(guān)類和接口都在java.util中，主要分為3種：List（列表）、Map（映射）、Set(集)。
其中Collection是集合List、Set的父接口，它主要有兩個(gè)子接口：
List：存儲(chǔ)的元素有序，可重復(fù)。Set：存儲(chǔ)的元素不無序，不可重復(fù)。
Map是另外的接口，是鍵值對(duì)映射結(jié)構(gòu)的集合。
List
List，也沒啥好問的，但不排除面試官劍走偏鋒，比如面試官也看了我這篇文章。
2.ArrayList和LinkedList有什么區(qū)別？
（1）數(shù)據(jù)結(jié)構(gòu)不同
ArrayList基于數(shù)組實(shí)現(xiàn) LinkedList基于雙向鏈表實(shí)現(xiàn)
（2） 多數(shù)情況下，ArrayList更利于查找，LinkedList更利于增刪
ArrayList基于數(shù)組實(shí)現(xiàn)，get(int index)可以直接通過數(shù)組下標(biāo)獲取，時(shí)間復(fù)雜度是O(1)；LinkedList基于鏈表實(shí)現(xiàn)，get(int index)需要遍歷鏈表，時(shí)間復(fù)雜度是O(n)；當(dāng)然，get(E element)這種查找，兩種集合都需要遍歷，時(shí)間復(fù)雜度都是O(n)。
ArrayList增刪如果是數(shù)組末尾的位置，直接插入或者刪除就可以了，但是如果插入中間的位置，就需要把插入位置后的元素都向前或者向后移動(dòng)，甚至還有可能觸發(fā)擴(kuò)容；雙向鏈表的插入和刪除只需要改變前驅(qū)節(jié)點(diǎn)、后繼節(jié)點(diǎn)和插入節(jié)點(diǎn)的指向就行了，不需要移動(dòng)元素。
ArrayList和LinkedList中間插入
注意，這個(gè)地方可能會(huì)出陷阱，LinkedList更利于增刪更多是體現(xiàn)在平均步長(zhǎng)上，不是體現(xiàn)在時(shí)間復(fù)雜度上，二者增刪的時(shí)間復(fù)雜度都是O(n)
（3）是否支持隨機(jī)訪問
ArrayList基于數(shù)組，所以它可以根據(jù)下標(biāo)查找，支持隨機(jī)訪問，當(dāng)然，它也實(shí)現(xiàn)了RandmoAccess 接口，這個(gè)接口只是用來標(biāo)識(shí)是否支持隨機(jī)訪問。 LinkedList基于鏈表，所以它沒法根據(jù)序號(hào)直接獲取元素，它沒有實(shí)現(xiàn)RandmoAccess 接口，標(biāo)記不支持隨機(jī)訪問。
（4）內(nèi)存占用，ArrayList基于數(shù)組，是一塊連續(xù)的內(nèi)存空間，LinkedList基于鏈表，內(nèi)存空間不連續(xù)，它們?cè)诳臻g占用上都有一些額外的消耗：
ArrayList是預(yù)先定義好的數(shù)組，可能會(huì)有空的內(nèi)存空間，存在一定空間浪費(fèi) LinkedList每個(gè)節(jié)點(diǎn)，需要存儲(chǔ)前驅(qū)和后繼，所以每個(gè)節(jié)點(diǎn)會(huì)占用更多的空間
3.ArrayList的擴(kuò)容機(jī)制了解嗎？
ArrayList是基于數(shù)組的集合，數(shù)組的容量是在定義的時(shí)候確定的，如果數(shù)組滿了，再插入，就會(huì)數(shù)組溢出。所以在插入時(shí)候，會(huì)先檢查是否需要擴(kuò)容，如果當(dāng)前容量+1超過數(shù)組長(zhǎng)度，就會(huì)進(jìn)行擴(kuò)容。
ArrayList的擴(kuò)容是創(chuàng)建一個(gè)1.5倍的新數(shù)組，然后把原數(shù)組的值拷貝過去。
4.ArrayList怎么序列化的知道嗎？為什么用transient修飾數(shù)組？
ArrayList的序列化不太一樣，它使用transient修飾存儲(chǔ)元素的elementData的數(shù)組，transient關(guān)鍵字的作用是讓被修飾的成員屬性不被序列化。
為什么最A(yù)rrayList不直接序列化元素?cái)?shù)組呢？
出于效率的考慮，數(shù)組可能長(zhǎng)度100，但實(shí)際只用了50，剩下的50不用其實(shí)不用序列化，這樣可以提高序列化和反序列化的效率，還可以節(jié)省內(nèi)存空間。
那ArrayList怎么序列化呢？
ArrayList通過兩個(gè)方法readObject、writeObject自定義序列化和反序列化策略，實(shí)際直接使用兩個(gè)流ObjectOutputStream和ObjectInputStream來進(jìn)行序列化和反序列化。
5.快速失敗(fail-fast)和安全失敗(fail-safe)了解嗎？
快速失敗（fail—fast）：快速失敗是Java集合的一種錯(cuò)誤檢測(cè)機(jī)制
在用迭代器遍歷一個(gè)集合對(duì)象時(shí)，如果線程A遍歷過程中，線程B對(duì)集合對(duì)象的內(nèi)容進(jìn)行了修改（增加、刪除、修改），則會(huì)拋出Concurrent Modification Exception。 原理：迭代器在遍歷時(shí)直接訪問集合中的內(nèi)容，并且在遍歷過程中使用一個(gè) modCount?變量。集合在被遍歷期間如果內(nèi)容發(fā)生變化，就會(huì)改變modCount的值。每當(dāng)?shù)魇褂胔ashNext()/next()遍歷下一個(gè)元素之前，都會(huì)檢測(cè)modCount變量是否為expectedmodCount值，是的話就返回遍歷；否則拋出異常，終止遍歷。注意：這里異常的拋出條件是檢測(cè)到 modCount！=expectedmodCount ?這個(gè)條件。如果集合發(fā)生變化時(shí)修改modCount值剛好又設(shè)置為了expectedmodCount值，則異常不會(huì)拋出。因此，不能依賴于這個(gè)異常是否拋出而進(jìn)行并發(fā)操作的編程，這個(gè)異常只建議用于檢測(cè)并發(fā)修改的bug。 場(chǎng)景：java.util包下的集合類都是快速失敗的，不能在多線程下發(fā)生并發(fā)修改（迭代過程中被修改），比如ArrayList 類。
安全失敗（fail—safe）
采用安全失敗機(jī)制的集合容器，在遍歷時(shí)不是直接在集合內(nèi)容上訪問的，而是先復(fù)制原有集合內(nèi)容，在拷貝的集合上進(jìn)行遍歷。 原理：由于迭代時(shí)是對(duì)原集合的拷貝進(jìn)行遍歷，所以在遍歷過程中對(duì)原集合所作的修改并不能被迭代器檢測(cè)到，所以不會(huì)觸發(fā)Concurrent Modification Exception。 缺點(diǎn)：基于拷貝內(nèi)容的優(yōu)點(diǎn)是避免了Concurrent Modification Exception，但同樣地，迭代器并不能訪問到修改后的內(nèi)容，即：迭代器遍歷的是開始遍歷那一刻拿到的集合拷貝，在遍歷期間原集合發(fā)生的修改迭代器是不知道的。 場(chǎng)景：java.util.concurrent包下的容器都是安全失敗，可以在多線程下并發(fā)使用，并發(fā)修改，比如CopyOnWriteArrayList類。
6.有哪幾種實(shí)現(xiàn)ArrayList線程安全的方法？
fail-fast是一種可能觸發(fā)的機(jī)制，實(shí)際上，ArrayList的線程安全仍然沒有保證，一般，保證ArrayList的線程安全可以通過這些方案：
使用 Vector 代替 ArrayList。（不推薦，Vector是一個(gè)歷史遺留類） 使用 Collections.synchronizedList 包裝 ArrayList，然后操作包裝后的 list。 使用 CopyOnWriteArrayList 代替 ArrayList。 在使用 ArrayList 時(shí)，應(yīng)用程序通過同步機(jī)制去控制 ArrayList 的讀寫。
7.CopyOnWriteArrayList了解多少？
CopyOnWriteArrayList就是線程安全版本的ArrayList。
它的名字叫CopyOnWrite——寫時(shí)復(fù)制，已經(jīng)明示了它的原理。
CopyOnWriteArrayList采用了一種讀寫分離的并發(fā)策略。CopyOnWriteArrayList容器允許并發(fā)讀，讀操作是無鎖的，性能較高。至于寫操作，比如向容器中添加一個(gè)元素，則首先將當(dāng)前容器復(fù)制一份，然后在新副本上執(zhí)行寫操作，結(jié)束之后再將原容器的引用指向新容器。
Map
Map中，毫無疑問，最重要的就是HashMap，面試基本被盤出包漿了，各種問法，一定要好好準(zhǔn)備。
8.能說一下HashMap的數(shù)據(jù)結(jié)構(gòu)嗎？
JDK1.7的數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表，JDK1.7還有人在用？不會(huì)吧……
說一下JDK1.8的數(shù)據(jù)結(jié)構(gòu)吧：
JDK1.8的數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表+紅黑樹。
數(shù)據(jù)結(jié)構(gòu)示意圖如下：
其中，桶數(shù)組是用來存儲(chǔ)數(shù)據(jù)元素，鏈表是用來解決沖突，紅黑樹是為了提高查詢的效率。
數(shù)據(jù)元素通過映射關(guān)系，也就是散列函數(shù)，映射到桶數(shù)組對(duì)應(yīng)索引的位置 如果發(fā)生沖突，從沖突的位置拉一個(gè)鏈表，插入沖突的元素 如果鏈表長(zhǎng)度>8&數(shù)組大小>=64，鏈表轉(zhuǎn)為紅黑樹 如果紅黑樹節(jié)點(diǎn)個(gè)數(shù)<6 ，轉(zhuǎn)為鏈表
9.你對(duì)紅黑樹了解多少？為什么不用二叉樹/平衡樹呢？
紅黑樹本質(zhì)上是一種二叉查找樹，為了保持平衡，它又在二叉查找樹的基礎(chǔ)上增加了一些規(guī)則：
每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色； 根節(jié)點(diǎn)永遠(yuǎn)是黑色的； 所有的葉子節(jié)點(diǎn)都是是黑色的（注意這里說葉子節(jié)點(diǎn)其實(shí)是圖中的 NULL 節(jié)點(diǎn)）； 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)一定都是黑色； 從任一節(jié)點(diǎn)到其子樹中每個(gè)葉子節(jié)點(diǎn)的路徑都包含相同數(shù)量的黑色節(jié)點(diǎn)；
之所以不用二叉樹：
紅黑樹是一種平衡的二叉樹，插入、刪除、查找的最壞時(shí)間復(fù)雜度都為 O(logn)，避免了二叉樹最壞情況下的O(n)時(shí)間復(fù)雜度。
之所以不用平衡二叉樹：
平衡二叉樹是比紅黑樹更嚴(yán)格的平衡樹，為了保持保持平衡，需要旋轉(zhuǎn)的次數(shù)更多，也就是說平衡二叉樹保持平衡的效率更低，所以平衡二叉樹插入和刪除的效率比紅黑樹要低。
10.紅黑樹怎么保持平衡的知道嗎？
紅黑樹有兩種方式保持平衡：旋轉(zhuǎn)和染色。
旋轉(zhuǎn)：旋轉(zhuǎn)分為兩種，左旋和右旋
染?：
11.HashMap的put流程知道嗎？
先上個(gè)流程圖吧:
首先進(jìn)行哈希值的擾動(dòng)，獲取一個(gè)新的哈希值。
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);判斷tab是否位空或者長(zhǎng)度為0，如果是則進(jìn)行擴(kuò)容操作。
if?((tab?=?table)?==?null?||?(n?=?tab.length)?==?0)
????n?=?(tab?=?resize()).length;根據(jù)哈希值計(jì)算下標(biāo)，如果對(duì)應(yīng)小標(biāo)正好沒有存放數(shù)據(jù)，則直接插入即可否則需要覆蓋。
tab[i = (n - 1) & hash])判斷tab[i]是否為樹節(jié)點(diǎn)，否則向鏈表中插入數(shù)據(jù)，是則向樹中插入節(jié)點(diǎn)。
如果鏈表中插入節(jié)點(diǎn)的時(shí)候，鏈表長(zhǎng)度大于等于8，則需要把鏈表轉(zhuǎn)換為紅黑樹。
treeifyBin(tab, hash);最后所有元素處理完成后，判斷是否超過閾值；
threshold，超過則擴(kuò)容。
12.HashMap怎么查找元素的呢？
先看流程圖：
HashMap的查找就簡(jiǎn)單很多：
使用擾動(dòng)函數(shù)，獲取新的哈希值 計(jì)算數(shù)組下標(biāo)，獲取節(jié)點(diǎn) 當(dāng)前節(jié)點(diǎn)和key匹配，直接返回 否則，當(dāng)前節(jié)點(diǎn)是否為樹節(jié)點(diǎn)，查找紅黑樹 否則，遍歷鏈表查找
13.HashMap的哈希/擾動(dòng)函數(shù)是怎么設(shè)計(jì)的?
HashMap的哈希函數(shù)是先拿到 key 的hashcode，是一個(gè)32位的int類型的數(shù)值，然后讓hashcode的高16位和低16位進(jìn)行異或操作。
????static?final?int?hash(Object?key)?{
????????int?h;
????????//?key的hashCode和key的hashCode右移16位做異或運(yùn)算
????????return?(key?==?null)???0?:?(h?=?key.hashCode())?^?(h?>>>?16);
????}
這么設(shè)計(jì)是為了降低哈希碰撞的概率。
14.為什么哈希/擾動(dòng)函數(shù)能降hash碰撞？
因?yàn)?key.hashCode() 函數(shù)調(diào)用的是 key 鍵值類型自帶的哈希函數(shù)，返回 int 型散列值。int 值范圍為 -2147483648~2147483647，加起來大概 40 億的映射空間。
只要哈希函數(shù)映射得比較均勻松散，一般應(yīng)用是很難出現(xiàn)碰撞的。但問題是一個(gè) 40 億長(zhǎng)度的數(shù)組，內(nèi)存是放不下的。
假如 HashMap 數(shù)組的初始大小才 16，就需要用之前需要對(duì)數(shù)組的長(zhǎng)度取模運(yùn)算，得到的余數(shù)才能用來訪問數(shù)組下標(biāo)。
源碼中模運(yùn)算就是把散列值和數(shù)組長(zhǎng)度 - 1 做一個(gè) "與&" 操作，位運(yùn)算比取余 % 運(yùn)算要快。
bucketIndex?=?indexFor(hash,?table.length);
static?int?indexFor(int?h,?int?length)?{
?????return?h?&?(length-1);
}
順便說一下，這也正好解釋了為什么 HashMap 的數(shù)組長(zhǎng)度要取 2 的整數(shù)冪。因?yàn)檫@樣（數(shù)組長(zhǎng)度 - 1）正好相當(dāng)于一個(gè) “低位掩碼”。與 操作的結(jié)果就是散列值的高位全部歸零，只保留低位值，用來做數(shù)組下標(biāo)訪問。以初始長(zhǎng)度 16 為例，16-1=15。2 進(jìn)制表示是 0000 0000 0000 0000 0000 0000 0000 1111。和某個(gè)散列值做 與 操作如下，結(jié)果就是截取了最低的四位值。
這樣是要快捷一些，但是新的問題來了，就算散列值分布再松散，要是只取最后幾位的話，碰撞也會(huì)很嚴(yán)重。如果散列本身做得不好，分布上成等差數(shù)列的漏洞，如果正好讓最后幾個(gè)低位呈現(xiàn)規(guī)律性重復(fù)，那就更難搞了。
這時(shí)候 擾動(dòng)函數(shù) 的價(jià)值就體現(xiàn)出來了，看一下擾動(dòng)函數(shù)的示意圖：
右移 16 位，正好是 32bit 的一半，自己的高半?yún)^(qū)和低半?yún)^(qū)做異或，就是為了混合原始哈希碼的高位和低位，以此來加大低位的隨機(jī)性。而且混合后的低位摻雜了高位的部分特征，這樣高位的信息也被變相保留下來。
15.為什么HashMap的容量是2的倍數(shù)呢？
第一個(gè)原因是為了方便哈希取余：
將元素放在table數(shù)組上面，是用hash值%數(shù)組大小定位位置，而HashMap是用hash值&(數(shù)組大小-1)，卻能和前面達(dá)到一樣的效果，這就得益于HashMap的大小是2的倍數(shù)，2的倍數(shù)意味著該數(shù)的二進(jìn)制位只有一位為1，而該數(shù)-1就可以得到二進(jìn)制位上1變成0，后面的0變成1，再通過&運(yùn)算，就可以得到和%一樣的效果，并且位運(yùn)算比%的效率高得多
HashMap的容量是2的n次冪時(shí)，(n-1)的2進(jìn)制也就是1111111***111這樣形式的，這樣與添加元素的hash值進(jìn)行位運(yùn)算時(shí)，能夠充分的散列，使得添加的元素均勻分布在HashMap的每個(gè)位置上，減少hash碰撞。
第二個(gè)方面是在擴(kuò)容時(shí)，利用擴(kuò)容后的大小也是2的倍數(shù)，將已經(jīng)產(chǎn)生hash碰撞的元素完美的轉(zhuǎn)移到新的table中去
我們可以簡(jiǎn)單看看HashMap的擴(kuò)容機(jī)制，HashMap中的元素在超過負(fù)載因子*HashMap大小時(shí)就會(huì)產(chǎn)生擴(kuò)容。
16.如果初始化HashMap，傳一個(gè)17的值new HashMap<>，它會(huì)怎么處理？
簡(jiǎn)單來說，就是初始化時(shí)，傳的不是2的倍數(shù)時(shí)，HashMap會(huì)向上尋找離得最近的2的倍數(shù)，所以傳入17，但HashMap的實(shí)際容量是32。
我們來看看詳情，在HashMap的初始化中，有這樣?段?法；
public?HashMap(int?initialCapacity,?float?loadFactor)?{
?...
?this.loadFactor?=?loadFactor;
?this.threshold?=?tableSizeFor(initialCapacity);
}
閥值 threshold ，通過?法 tableSizeFor進(jìn)?計(jì)算，是根據(jù)初始化傳的參數(shù)來計(jì)算的。同時(shí)，這個(gè)?法也要要尋找?初始值?的，最?的那個(gè)2進(jìn)制數(shù)值。?如傳了17，我應(yīng)該找到的是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，這個(gè)是臨界范圍，也就是最?的Map集合。 計(jì)算過程是向右移位1、2、4、8、16，和原來的數(shù)做 |運(yùn)算，這主要是為了把?進(jìn)制的各個(gè)位置都填上1，當(dāng)?進(jìn)制的各個(gè)位置都是1以后，就是?個(gè)標(biāo)準(zhǔn)的2的倍數(shù)減1了，最后把結(jié)果加1再返回即可。
以17為例，看一下初始化計(jì)算table容量的過程：
17.你還知道哪些哈希函數(shù)的構(gòu)造方法呢？
HashMap里哈希構(gòu)造函數(shù)的方法叫：
除留取余法：H（key)=key%p（p<=N）,關(guān)鍵字除以一個(gè)不大于哈希表長(zhǎng)度的正整數(shù)p，所得余數(shù)為地址，當(dāng)然HashMap里進(jìn)行了優(yōu)化改造，效率更高，散列也更均衡。
除此之外，還有這幾種常見的哈希函數(shù)構(gòu)造方法：
直接定址法
直接根據(jù)
key來映射到對(duì)應(yīng)的數(shù)組位置，例如1232放到下標(biāo)1232的位置。數(shù)字分析法
取
key的某些數(shù)字（例如十位和百位）作為映射的位置平方取中法
取
key平方的中間幾位作為映射的位置折疊法
將
key分割成位數(shù)相同的幾段，然后把它們的疊加和作為映射的位置
18.解決哈希沖突有哪些方法呢？
我們到現(xiàn)在已經(jīng)知道，HashMap使用鏈表的原因?yàn)榱颂幚砉_突，這種方法就是所謂的：
鏈地址法：在沖突的位置拉一個(gè)鏈表，把沖突的元素放進(jìn)去。
除此之外，還有一些常見的解決沖突的辦法：
開放定址法：開放定址法就是從沖突的位置再接著往下找，給沖突元素找個(gè)空位。
找到空閑位置的方法也有很多種：
線行探查法: 從沖突的位置開始，依次判斷下一個(gè)位置是否空閑，直至找到空閑位置 平方探查法: 從沖突的位置x開始，第一次增加 1^2個(gè)位置，第二次增加2^2…，直至找到空閑的位置……
再哈希法：換種哈希函數(shù)，重新計(jì)算沖突元素的地址。 建立公共溢出區(qū)：再建一個(gè)數(shù)組，把沖突的元素放進(jìn)去。
19.為什么HashMap鏈表轉(zhuǎn)紅黑樹的閾值為8呢？
樹化發(fā)生在table數(shù)組的長(zhǎng)度大于64，且鏈表的長(zhǎng)度大于8的時(shí)候。
為什么是8呢？源碼的注釋也給出了答案。
紅黑樹節(jié)點(diǎn)的大小大概是普通節(jié)點(diǎn)大小的兩倍，所以轉(zhuǎn)紅黑樹，犧牲了空間換時(shí)間，更多的是一種兜底的策略，保證極端情況下的查找效率。
閾值為什么要選8呢？和統(tǒng)計(jì)學(xué)有關(guān)。理想情況下，使用隨機(jī)哈希碼，鏈表里的節(jié)點(diǎn)符合泊松分布，出現(xiàn)節(jié)點(diǎn)個(gè)數(shù)的概率是遞減的，節(jié)點(diǎn)個(gè)數(shù)為8的情況，發(fā)生概率僅為0.00000006。
至于紅黑樹轉(zhuǎn)回鏈表的閾值為什么是6，而不是8？是因?yàn)槿绻@個(gè)閾值也設(shè)置成8，假如發(fā)生碰撞，節(jié)點(diǎn)增減剛好在8附近，會(huì)發(fā)生鏈表和紅黑樹的不斷轉(zhuǎn)換，導(dǎo)致資源浪費(fèi)。
20.擴(kuò)容在什么時(shí)候呢？為什么擴(kuò)容因子是0.75？
為了減少哈希沖突發(fā)生的概率，當(dāng)當(dāng)前HashMap的元素個(gè)數(shù)達(dá)到一個(gè)臨界值的時(shí)候，就會(huì)觸發(fā)擴(kuò)容，把所有元素rehash之后再放在擴(kuò)容后的容器中，這是一個(gè)相當(dāng)耗時(shí)的操作。
而這個(gè)臨界值threshold就是由加載因子和當(dāng)前容器的容量大小來確定的，假如采用默認(rèn)的構(gòu)造方法：
臨界值（threshold ）= 默認(rèn)容量（DEFAULT_INITIAL_CAPACITY） * 默認(rèn)擴(kuò)容因子（DEFAULT_LOAD_FACTOR）
那就是大于16x0.75=12時(shí)，就會(huì)觸發(fā)擴(kuò)容操作。
那么為什么選擇了0.75作為HashMap的默認(rèn)加載因子呢？
簡(jiǎn)單來說，這是對(duì)空間成本和時(shí)間成本平衡的考慮。
在HashMap中有這樣一段注釋：
我們都知道，HashMap的散列構(gòu)造方式是Hash取余，負(fù)載因子決定元素個(gè)數(shù)達(dá)到多少時(shí)候擴(kuò)容。
假如我們?cè)O(shè)的比較大，元素比較多，空位比較少的時(shí)候才擴(kuò)容，那么發(fā)生哈希沖突的概率就增加了，查找的時(shí)間成本就增加了。
我們?cè)O(shè)的比較小的話，元素比較少，空位比較多的時(shí)候就擴(kuò)容了，發(fā)生哈希碰撞的概率就降低了，查找時(shí)間成本降低，但是就需要更多的空間去存儲(chǔ)元素，空間成本就增加了。
21.那擴(kuò)容機(jī)制了解嗎？
HashMap是基于數(shù)組+鏈表和紅黑樹實(shí)現(xiàn)的，但用于存放key值的桶數(shù)組的長(zhǎng)度是固定的，由初始化參數(shù)確定。
那么，隨著數(shù)據(jù)的插入數(shù)量增加以及負(fù)載因子的作用下，就需要擴(kuò)容來存放更多的數(shù)據(jù)。而擴(kuò)容中有一個(gè)非常重要的點(diǎn)，就是jdk1.8中的優(yōu)化操作，可以不需要再重新計(jì)算每一個(gè)元素的哈希值。
因?yàn)镠ashMap的初始容量是2的次冪，擴(kuò)容之后的長(zhǎng)度是原來的二倍，新的容量也是2的次冪，所以，元素，要么在原位置，要么在原位置再移動(dòng)2的次冪。
看下這張圖，n為table的長(zhǎng)度，圖a表示擴(kuò)容前的key1和key2兩種key確定索引的位置，圖b表示擴(kuò)容后key1和key2兩種key確定索引位置。
元素在重新計(jì)算hash之后，因?yàn)閚變?yōu)?倍，那么n-1的mask范圍在高位多1bit(紅色)，因此新的index就會(huì)發(fā)生這樣的變化：
所以在擴(kuò)容時(shí)，只需要看原來的hash值新增的那一位是0還是1就行了，是0的話索引沒變，是1的化變成原索引+oldCap，看看如16擴(kuò)容為32的示意圖：
擴(kuò)容節(jié)點(diǎn)遷移主要邏輯：
22.jdk1.8對(duì)HashMap主要做了哪些優(yōu)化呢？為什么？
jdk1.8 的HashMap主要有五點(diǎn)優(yōu)化：
數(shù)據(jù)結(jié)構(gòu)：數(shù)組 + 鏈表改成了數(shù)組 + 鏈表或紅黑樹
原因：發(fā)生 hash 沖突，元素會(huì)存入鏈表，鏈表過長(zhǎng)轉(zhuǎn)為紅黑樹，將時(shí)間復(fù)雜度由O(n)降為O(logn)鏈表插入方式：鏈表的插入方式從頭插法改成了尾插法
簡(jiǎn)單說就是插入時(shí)，如果數(shù)組位置上已經(jīng)有元素，1.7 將新元素放到數(shù)組中，原始節(jié)點(diǎn)作為新節(jié)點(diǎn)的后繼節(jié)點(diǎn)，1.8 遍歷鏈表，將元素放置到鏈表的最后。
原因：因?yàn)?1.7 頭插法擴(kuò)容時(shí)，頭插法會(huì)使鏈表發(fā)生反轉(zhuǎn)，多線程環(huán)境下會(huì)產(chǎn)生環(huán)。擴(kuò)容rehash：擴(kuò)容的時(shí)候 1.7 需要對(duì)原數(shù)組中的元素進(jìn)行重新 hash 定位在新數(shù)組的位置，1.8 采用更簡(jiǎn)單的判斷邏輯，不需要重新通過哈希函數(shù)計(jì)算位置，新的位置不變或索引 + 新增容量大小。
原因：提高擴(kuò)容的效率，更快地?cái)U(kuò)容。擴(kuò)容時(shí)機(jī)：在插入時(shí)，1.7 先判斷是否需要擴(kuò)容，再插入，1.8 先進(jìn)行插入，插入完成再判斷是否需要擴(kuò)容；
散列函數(shù)：1.7 做了四次移位和四次異或，jdk1.8只做一次。
原因：做 4 次的話，邊際效用也不大，改為一次，提升效率。
23.你能自己設(shè)計(jì)實(shí)現(xiàn)一個(gè)HashMap嗎？
這道題快手常考。
不要慌，紅黑樹版咱們多半是寫不出來，但是數(shù)組+鏈表版還是問題不大的，詳細(xì)可見：手寫HashMap，快手面試官直呼內(nèi)行！。
整體的設(shè)計(jì)：
散列函數(shù)：hashCode()+除留余數(shù)法 沖突解決：鏈地址法 擴(kuò)容：節(jié)點(diǎn)重新hash獲取位置
完整代碼：
24.HashMap 是線程安全的嗎？多線程下會(huì)有什么問題？
HashMap不是線程安全的，可能會(huì)發(fā)生這些問題：
多線程下擴(kuò)容死循環(huán)。JDK1.7 中的 HashMap 使用頭插法插入元素，在多線程的環(huán)境下，擴(kuò)容的時(shí)候有可能導(dǎo)致環(huán)形鏈表的出現(xiàn)，形成死循環(huán)。因此，JDK1.8 使用尾插法插入元素，在擴(kuò)容時(shí)會(huì)保持鏈表元素原本的順序，不會(huì)出現(xiàn)環(huán)形鏈表的問題。
多線程的 put 可能導(dǎo)致元素的丟失。多線程同時(shí)執(zhí)行 put 操作，如果計(jì)算出來的索引位置是相同的，那會(huì)造成前一個(gè) key 被后一個(gè) key 覆蓋，從而導(dǎo)致元素的丟失。此問題在 JDK 1.7 和 JDK 1.8 中都存在。
put 和 get 并發(fā)時(shí)，可能導(dǎo)致 get 為 null。線程 1 執(zhí)行 put 時(shí)，因?yàn)樵貍€(gè)數(shù)超出 threshold 而導(dǎo)致 rehash，線程 2 此時(shí)執(zhí)行 get，有可能導(dǎo)致這個(gè)問題。這個(gè)問題在 JDK 1.7 和 JDK 1.8 中都存在。
25.有什么辦法能解決HashMap線程不安全的問題呢？
Java 中有 HashTable、Collections.synchronizedMap、以及 ConcurrentHashMap 可以實(shí)現(xiàn)線程安全的 Map。
HashTable 是直接在操作方法上加 synchronized 關(guān)鍵字，鎖住整個(gè)table數(shù)組，粒度比較大； Collections.synchronizedMap 是使用 Collections 集合工具的內(nèi)部類，通過傳入 Map 封裝出一個(gè) SynchronizedMap 對(duì)象，內(nèi)部定義了一個(gè)對(duì)象鎖，方法內(nèi)通過對(duì)象鎖實(shí)現(xiàn)； ConcurrentHashMap 在jdk1.7中使用分段鎖，在jdk1.8中使用CAS+synchronized。
26.能具體說一下ConcurrentHashmap的實(shí)現(xiàn)嗎？
ConcurrentHashmap線程安全在jdk1.7版本是基于分段鎖實(shí)現(xiàn)，在jdk1.8是基于CAS+synchronized實(shí)現(xiàn)。
1.7分段鎖
從結(jié)構(gòu)上說，1.7版本的ConcurrentHashMap采用分段鎖機(jī)制，里面包含一個(gè)Segment數(shù)組，Segment繼承于ReentrantLock，Segment則包含HashEntry的數(shù)組，HashEntry本身就是一個(gè)鏈表的結(jié)構(gòu)，具有保存key、value的能力能指向下一個(gè)節(jié)點(diǎn)的指針。
實(shí)際上就是相當(dāng)于每個(gè)Segment都是一個(gè)HashMap，默認(rèn)的Segment長(zhǎng)度是16，也就是支持16個(gè)線程的并發(fā)寫，Segment之間相互不會(huì)受到影響。
put流程
整個(gè)流程和HashMap非常類似，只不過是先定位到具體的Segment，然后通過ReentrantLock去操作而已，后面的流程，就和HashMap基本上是一樣的。
計(jì)算hash，定位到segment，segment如果是空就先初始化 使用ReentrantLock加鎖，如果獲取鎖失敗則嘗試自旋，自旋超過次數(shù)就阻塞獲取，保證一定獲取鎖成功 遍歷HashEntry，就是和HashMap一樣，數(shù)組中key和hash一樣就直接替換，不存在就再插入鏈表，鏈表同樣操作
get流程
get也很簡(jiǎn)單，key通過hash定位到segment，再遍歷鏈表定位到具體的元素上，需要注意的是value是volatile的，所以get是不需要加鎖的。
1.8 CAS+synchronized
jdk1.8實(shí)現(xiàn)線程安全不是在數(shù)據(jù)結(jié)構(gòu)上下功夫，它的數(shù)據(jù)結(jié)構(gòu)和HashMap是一樣的，數(shù)組+鏈表+紅黑樹。它實(shí)現(xiàn)線程安全的關(guān)鍵點(diǎn)在于put流程。
put流程
首先計(jì)算hash，遍歷node數(shù)組，如果node是空的話，就通過CAS+自旋的方式初始化
?tab?=?initTable();
node數(shù)組初始化：
????private?final?Node[]?initTable()?{
????????Node[]?tab;?int?sc;
????????while?((tab?=?table)?==?null?||?tab.length?==?0)?{
????????????//如果正在初始化或者擴(kuò)容
????????????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[]?nt?=?(Node[])new?Node[n];
????????????????????????table?=?tab?=?nt;
????????????????????????sc?=?n?-?(n?>>>?2);
????????????????????}
????????????????}?finally?{
????????????????????sizeCtl?=?sc;
????????????????}
????????????????break;
????????????}
????????}
????????return?tab;
????}
2.如果當(dāng)前數(shù)組位置是空則直接通過CAS自旋寫入數(shù)據(jù)
????static?final??boolean?casTabAt(Node[]?tab,?int?i,
????????????????????????????????????????Node?c,?Node?v) ?{
????????return?U.compareAndSwapObject(tab,?((long)i?<????}
如果hash==MOVED，說明需要擴(kuò)容，執(zhí)行擴(kuò)容
else?if?((fh?=?f.hash)?==?MOVED)
????????????????tab?=?helpTransfer(tab,?f);
????final?Node[]?helpTransfer(Node[]?tab,?Node?f)?{
????????Node[]?nextTab;?int?sc;
????????if?(tab?!=?null?&&?(f?instanceof?ForwardingNode)?&&
????????????(nextTab?=?((ForwardingNode)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寫入數(shù)據(jù)，寫入數(shù)據(jù)同樣判斷鏈表、紅黑樹，鏈表寫入和HashMap的方式一樣，key hash一樣就覆蓋，反之就尾插法，鏈表長(zhǎng)度超過8就轉(zhuǎn)換成紅黑樹
?synchronized?(f){
?????……
?}
get查詢
get很簡(jiǎn)單，和HashMap基本相同，通過key計(jì)算位置，table該位置key相同就返回，如果是紅黑樹按照紅黑樹獲取，否則就遍歷鏈表獲取。
27.HashMap 內(nèi)部節(jié)點(diǎn)是有序的嗎？
HashMap是無序的，根據(jù) hash 值隨機(jī)插入。如果想使用有序的Map，可以使用LinkedHashMap 或者 TreeMap。
28.講講 LinkedHashMap 怎么實(shí)現(xiàn)有序的？
LinkedHashMap維護(hù)了一個(gè)雙向鏈表，有頭尾節(jié)點(diǎn)，同時(shí) LinkedHashMap 節(jié)點(diǎn) Entry 內(nèi)部除了繼承 HashMap 的 Node 屬性，還有 before 和 after 用于標(biāo)識(shí)前置節(jié)點(diǎn)和后置節(jié)點(diǎn)。
可以實(shí)現(xiàn)按插入的順序或訪問順序排序。
29.講講 TreeMap 怎么實(shí)現(xiàn)有序的？
TreeMap 是按照 Key 的自然順序或者 Comprator 的順序進(jìn)行排序，內(nèi)部是通過紅黑樹來實(shí)現(xiàn)。所以要么 key 所屬的類實(shí)現(xiàn) Comparable 接口，或者自定義一個(gè)實(shí)現(xiàn)了 Comparator 接口的比較器，傳給 TreeMap 用于 key 的比較。
Set
Set面試沒啥好問的，拿HashSet來湊個(gè)數(shù)。
30.講講HashSet的底層實(shí)現(xiàn)？
HashSet 底層就是基于 HashMap 實(shí)現(xiàn)的。（ HashSet 的源碼?常?常少，因?yàn)槌?clone() 、 writeObject() 、 readObject() 是 HashSet??不得不實(shí)現(xiàn)之外，其他?法都是直接調(diào)? HashMap 中的?法。
HashSet的add方法，直接調(diào)用HashMap的put方法，將添加的元素作為key，new一個(gè)Object作為value，直接調(diào)用HashMap的put方法，它會(huì)根據(jù)返回值是否為空來判斷是否插入元素成功。
????public?boolean?add(E?e)?{
????????return?map.put(e,?PRESENT)==null;
????}
而在HashMap的putVal方法中，進(jìn)行了一系列判斷，最后的結(jié)果是，只有在key在table數(shù)組中不存在的時(shí)候，才會(huì)返回插入的值。
????????????if?(e?!=?null)?{?//?existing?mapping?for?key
????????????????V?oldValue?=?e.value;
????????????????if?(!onlyIfAbsent?||?oldValue?==?null)
????????????????????e.value?=?value;
????????????????afterNodeAccess(e);
????????????????return?oldValue;
????????????}
沒有什么使我停留——除了目的，縱然岸旁有玫瑰、有綠蔭、有寧靜的港灣，我是不系之舟。
推薦閱讀：