HashMap作為我們熟悉的一種集合，可以說是面試必考題。簡單的使用，再到原理、數(shù)據(jù)結(jié)構(gòu)，還可以延伸到并發(fā)，可以說，就一個(gè)HashMap，能聊半個(gè)小時(shí)。

1.能說一下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è)鏈表，插入沖突的元素

• 如果鏈表長度>8&數(shù)組大小>=64，鏈表轉(zhuǎn)為紅黑樹

• 如果紅黑樹節(jié)點(diǎn)個(gè)數(shù)<6 ，轉(zhuǎn)為鏈表

2.你對(duì)紅黑樹了解多少？為什么不用二叉樹/平衡樹呢？

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

1. 每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色；

2. 根節(jié)點(diǎn)永遠(yuǎn)是黑色的；

3. 所有的葉子節(jié)點(diǎn)都是是黑色的（注意這里說葉子節(jié)點(diǎn)其實(shí)是圖中的 NULL 節(jié)點(diǎn)）；

4. 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)一定都是黑色；

5. 從任一節(jié)點(diǎn)到其子樹中每個(gè)葉子節(jié)點(diǎn)的路徑都包含相同數(shù)量的黑色節(jié)點(diǎn)；

之所以不用二叉樹：

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

之所以不用平衡二叉樹：

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

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

紅黑樹有兩種方式保持平衡：旋轉(zhuǎn)和染色。

• 旋轉(zhuǎn)：旋轉(zhuǎn)分為兩種，左旋和右旋

• 染?：

4.HashMap的put流程知道嗎？

先上個(gè)流程圖吧:

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

2. 判斷tab是否位空或者長度為0，如果是則進(jìn)行擴(kuò)容操作。

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


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

4. 判斷tab[i]是否為樹節(jié)點(diǎn)，否則向鏈表中插入數(shù)據(jù)，是則向樹中插入節(jié)點(diǎn)。

5. 如果鏈表中插入節(jié)點(diǎn)的時(shí)候，鏈表長度大于等于8，則需要把鏈表轉(zhuǎn)換為紅黑樹。treeifyBin(tab, hash);

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

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

先看流程圖：

HashMap的查找就簡單很多：

1. 使用擾動(dòng)函數(shù)，獲取新的哈希值

2. 計(jì)算數(shù)組下標(biāo)，獲取節(jié)點(diǎn)

3. 當(dāng)前節(jié)點(diǎn)和key匹配，直接返回

4. 否則，當(dāng)前節(jié)點(diǎn)是否為樹節(jié)點(diǎn)，查找紅黑樹

5. 否則，遍歷鏈表查找

6.HashMap的哈希/擾動(dòng)函數(shù)是怎么設(shè)計(jì)的?

HashMap的哈希函數(shù)是先拿到 key 的hashcode，是一個(gè)32位的int類型的數(shù)值，然后讓hashcode的高16位和低16位進(jìn)行異或操作。

這么設(shè)計(jì)是為了降低哈希碰撞的概率。

7.為什么哈希/擾動(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 億長度的數(shù)組，內(nèi)存是放不下的。

假如 HashMap 數(shù)組的初始大小才 16，就需要用之前需要對(duì)數(shù)組的長度取模運(yùn)算，得到的余數(shù)才能用來訪問數(shù)組下標(biāo)。

源碼中模運(yùn)算就是把散列值和數(shù)組長度 - 1 做一個(gè) "與&" 操作，位運(yùn)算比取余 % 運(yùn)算要快。

順便說一下，這也正好解釋了為什么 HashMap 的數(shù)組長度要取 2 的整數(shù)冪。因?yàn)檫@樣（數(shù)組長度 - 1）正好相當(dāng)于一個(gè) “低位掩碼”。與?操作的結(jié)果就是散列值的高位全部歸零，只保留低位值，用來做數(shù)組下標(biāo)訪問。以初始長度 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ī)性。而且混合后的低位摻雜了高位的部分特征，這樣高位的信息也被變相保留下來。

8.為什么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中去

我們可以簡單看看HashMap的擴(kuò)容機(jī)制，HashMap中的元素在超過負(fù)載因子*HashMap大小時(shí)就會(huì)產(chǎn)生擴(kuò)容。

9.如果初始化HashMap，傳一個(gè)17的值new HashMap<>，它會(huì)怎么處理？

簡單來說，就是初始化時(shí)，傳的不是2的倍數(shù)時(shí)，HashMap會(huì)向上尋找離得最近的2的倍數(shù)，所以傳入14，但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。

• 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容量的過程：

10.你還知道哪些哈希函數(shù)的構(gòu)造方法呢？

HashMap里哈希構(gòu)造函數(shù)的方法叫：

• 除留取余法：H（key)=key%p（p<=N）,關(guān)鍵字除以一個(gè)不大于哈希表長度的正整數(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ù)相同的幾段，然后把它們的疊加和作為映射的位置

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

我們到現(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)去。

12.為什么HashMap鏈表轉(zhuǎn)紅黑樹的閾值為8呢？

樹化發(fā)生在table數(shù)組的長度大于64，且鏈表的長度大于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)。

13.擴(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)加載因子呢？

簡單來說，這是對(duì)空間成本和時(shí)間成本平衡的考慮。

在HashMap中有這樣一段注釋：

我們都知道，HashMap的散列構(gòu)造方式是Hash取余，負(fù)載因子決定元素個(gè)數(shù)達(dá)到多少時(shí)候擴(kuò)容。

假如我們設(shè)的比較大，元素比較多，空位比較少的時(shí)候才擴(kuò)容，那么發(fā)生哈希沖突的概率就增加了，查找的時(shí)間成本就增加了。

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

14.那擴(kuò)容機(jī)制了解嗎？

HashMap是基于數(shù)組+鏈表和紅黑樹實(shí)現(xiàn)的，但用于存放key值的桶數(shù)組的長度是固定的，由初始化參數(shù)確定。

那么，隨著數(shù)據(jù)的插入數(shù)量增加以及負(fù)載因子的作用下，就需要擴(kuò)容來存放更多的數(shù)據(jù)。而擴(kuò)容中有一個(gè)非常重要的點(diǎn)，就是jdk1.8中的優(yōu)化操作，可以不需要再重新計(jì)算每一個(gè)元素的哈希值。

因?yàn)镠ashMap的初始容量是2的次冪，擴(kuò)容之后的長度是原來的二倍，新的容量也是2的次冪，所以，元素，要么在原位置，要么在原位置再移動(dòng)2的次冪。

看下這張圖，n為table的長度，圖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)遷移主要邏輯：

15.jdk1.8對(duì)HashMap主要做了哪些優(yōu)化呢？為什么？

jdk1.8 的HashMap主要有五點(diǎn)優(yōu)化：

1. 數(shù)據(jù)結(jié)構(gòu)：數(shù)組 + 鏈表改成了數(shù)組 + 鏈表或紅黑樹

   原因：發(fā)生 hash 沖突，元素會(huì)存入鏈表，鏈表過長轉(zhuǎn)為紅黑樹，將時(shí)間復(fù)雜度由O(n)降為O(logn)

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

   簡單說就是插入時(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)。

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

   原因：提高擴(kuò)容的效率，更快地?cái)U(kuò)容。

4. 擴(kuò)容時(shí)機(jī)：在插入時(shí)，1.7 先判斷是否需要擴(kuò)容，再插入，1.8 先進(jìn)行插入，插入完成再判斷是否需要擴(kuò)容；

5. 散列函數(shù)：1.7 做了四次移位和四次異或，jdk1.8只做一次。

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

16.你能自己設(shè)計(jì)實(shí)現(xiàn)一個(gè)HashMap嗎？

這道題快手?？?。

不要慌，紅黑樹版咱們多半是寫不出來，但是數(shù)組+鏈表版還是問題不大的。

整體的設(shè)計(jì)：

• 散列函數(shù)：hashCode()+除留余數(shù)法

• 沖突解決：鏈地址法

• 擴(kuò)容：節(jié)點(diǎn)重新hash獲取位置

17.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 中都存在。

18.有什么辦法能解決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。

19.能具體說一下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長度是16，也就是支持16個(gè)線程的并發(fā)寫，Segment之間相互不會(huì)受到影響。

put流程

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

1. 計(jì)算hash，定位到segment，segment如果是空就先初始化

2. 使用ReentrantLock加鎖，如果獲取鎖失敗則嘗試自旋，自旋超過次數(shù)就阻塞獲取，保證一定獲取鎖成功

3. 遍歷HashEntry，就是和HashMap一樣，數(shù)組中key和hash一樣就直接替換，不存在就再插入鏈表，鏈表同樣操作

get流程

get也很簡單，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流程

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

?tab?=?initTable();


node數(shù)組初始化：

2.如果當(dāng)前數(shù)組位置是空則直接通過CAS自旋寫入數(shù)據(jù)

?

1. 如果hash==MOVED，說明需要擴(kuò)容，執(zhí)行擴(kuò)容

1. 如果都不滿足，就使用synchronized寫入數(shù)據(jù)，寫入數(shù)據(jù)同樣判斷鏈表、紅黑樹，鏈表寫入和HashMap的方式一樣，key hash一樣就覆蓋，反之就尾插法，鏈表長度超過8就轉(zhuǎn)換成紅黑樹

?

get查詢

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

20.HashMap 內(nèi)部節(jié)點(diǎn)是有序的嗎？

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

21.講講 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)按插入的順序或訪問順序排序。

22.講講 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 的比較。

23.講講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ù)返回值是否為空來判斷是否插入元素成功。

???

而在HashMap的putVal方法中，進(jìn)行了一系列判斷，最后的結(jié)果是，只有在key在table數(shù)組中不存在的時(shí)候，才會(huì)返回插入的值。

??????????