14、說說resize擴(kuò)容的過程

創(chuàng)建一個新的數(shù)組，其容量為舊數(shù)組的兩倍，并重新計算舊數(shù)組中結(jié)點(diǎn)的存儲位置。結(jié)點(diǎn)在新數(shù)組中的位置只有兩種，原下標(biāo)位置或原下標(biāo)+舊數(shù)組的大小。

15、說說hashMap中g(shù)et是如何實(shí)現(xiàn)的？

對key的hashCode進(jìn)行hash值計算，與運(yùn)算計算下標(biāo)獲取bucket位置，如果在桶的首位上就可以找到就直接返回，否則在樹中找或者鏈表中遍歷找，如果有hash沖突，則利用equals方法去遍歷鏈表查找節(jié)點(diǎn)。

16、拉鏈法導(dǎo)致的鏈表過深問題為什么不用二叉查找樹代替，而選擇紅黑樹？為什么不一直使用紅黑樹？

之所以選擇紅黑樹是為了解決二叉查找樹的缺陷，二叉查找樹在特殊情況下會變成一條線性結(jié)構(gòu)（這就跟原來使用鏈表結(jié)構(gòu)一樣了，造成很深的問題），遍歷查找會非常慢。而紅黑樹在插入新數(shù)據(jù)后可能需要通過左旋，右旋、變色這些操作來保持平衡，引入紅黑樹就是為了查找數(shù)據(jù)快，解決鏈表查詢深度的問題，我們知道紅黑樹屬于平衡二叉樹，但是為了保持“平衡”是需要付出代價的，但是該代價所損耗的資源要比遍歷線性鏈表要少，所以當(dāng)長度大于8的時候，會使用紅黑樹，如果鏈表長度很短的話，根本不需要引入紅黑樹，引入反而會慢。

17、說說你對紅黑樹的了解

紅黑樹是一種自平衡的二叉查找樹，是一種高效的查找樹。

紅黑樹通過如下的性質(zhì)定義實(shí)現(xiàn)自平衡：

• 節(jié)點(diǎn)是紅色或黑色。
• 根是黑色。
• 所有葉子都是黑色（葉子是NIL節(jié)點(diǎn)）。
• 每個紅色節(jié)點(diǎn)必須有兩個黑色的子節(jié)點(diǎn)。（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點(diǎn)。）
• 從任一節(jié)點(diǎn)到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)（簡稱黑高）。

18、JDK8中對HashMap做了哪些改變？

1.在java 1.8中，如果鏈表的長度超過了8，那么鏈表將轉(zhuǎn)換為紅黑樹。（桶的數(shù)量必須大于64，小于64的時候只會擴(kuò)容）

2.發(fā)生hash碰撞時，java 1.7 會在鏈表的頭部插入，而java 1.8會在鏈表的尾部插入

3.在java 1.8中，Entry被Node替代(換了一個馬甲)。

19、HashMap 中的 key 我們可以使用任何類作為 key 嗎？

平時可能大家使用的最多的就是使用 String 作為 HashMap 的 key，但是現(xiàn)在我們想使用某個自定 義類作為 HashMap 的 key，那就需要注意以下幾點(diǎn)：

• 如果類重寫了 equals 方法，它也應(yīng)該重寫 hashCode 方法。

• 類的所有實(shí)例需要遵循與 equals 和 hashCode 相關(guān)的規(guī)則。

• 如果一個類沒有使用 equals，你不應(yīng)該在 hashCode 中使用它。

• 咱們自定義 key 類的最佳實(shí)踐是使之為不可變的，這樣，hashCode 值可以被緩存起來，擁有

  更好的性能。不可變的類也可以確保 hashCode 和 equals 在未來不會改變，這樣就會解決與可變相關(guān)的問題了。

20、HashMap 的長度為什么是 2 的 N 次方呢？

為了能讓 HashMap 存數(shù)據(jù)和取數(shù)據(jù)的效率高，盡可能地減少 hash 值的碰撞，也就是說盡量把數(shù) 據(jù)能均勻的分配，每個鏈表或者紅黑樹長度盡量相等。我們首先可能會想到 % 取模的操作來實(shí)現(xiàn)。下面是回答的重點(diǎn)喲：

取余（%）操作中如果除數(shù)是 2 的冪次，則等價于與其除數(shù)減一的與（&）操作（也就是說 hash % length == hash &(length - 1) 的前提是 length 是 2 的 n 次方）。并且，采用二進(jìn) 制位操作 & ，相對于 % 能夠提高運(yùn)算效率。

這就是為什么 HashMap 的長度需要 2 的 N 次方了。

21、HashMap，LinkedHashMap，TreeMap 有什么區(qū)別？

• LinkedHashMap是繼承于HashMap，是基于HashMap和雙向鏈表來實(shí)現(xiàn)的。
• HashMap無序；LinkedHashMap有序，可分為插入順序和訪問順序兩種。如果是訪問順序，那put和get操作已存在的Entry時，都會把Entry移動到雙向鏈表的表尾(其實(shí)是先刪除再插入)。
• LinkedHashMap存取數(shù)據(jù)，還是跟HashMap一樣使用的Entry[]的方式，雙向鏈表只是為了保證順序。
• LinkedHashMap是線程不安全的。

22、說說什么是 fail-fast？

fail-fast 機(jī)制是 Java 集合（Collection）中的一種錯誤機(jī)制。當(dāng)多個線程對同一個集合的內(nèi)容進(jìn)行 操作時，就可能會產(chǎn)生 fail-fast 事件。

例如：當(dāng)某一個線程 A 通過 iterator 去遍歷某集合的過程中，若該集合的內(nèi)容被其他線程所改變 了，那么線程 A 訪問集合時，就會拋出 ConcurrentModificationException 異常，產(chǎn)生 fail-fast 事 件。這里的操作主要是指 add、remove 和 clear，對集合元素個數(shù)進(jìn)行修改。

解決辦法

建議使用“java.util.concurrent 包下的類”去取代“java.util 包下的類”?？梢赃@么理解：在遍歷之前，把 modCount 記下來 expectModCount，后面 expectModCount 去 和 modCount 進(jìn)行比較，如果不相等了，證明已并發(fā)了，被修改了，于是拋出 ConcurrentModificationException 異常。

23、HashMap 和 HashTable 有什么區(qū)別？

①、HashMap 是線程不安全的，HashTable 是線程安全的；

②、由于線程安全，所以 HashTable 的效率比不上 HashMap；

③、HashMap最多只允許一條記錄的鍵為null，允許多條記錄的值為null，而 HashTable不允許；

④、HashMap 默認(rèn)初始化數(shù)組的大小為16，HashTable 為 11，前者擴(kuò)容時，擴(kuò)大兩倍，后者擴(kuò)大兩倍+1；

⑤、HashMap 需要重新計算 hash 值，而 HashTable 直接使用對象的 hashCode；

24、HashMap 是線程安全的嗎？

不是，在多線程環(huán)境下，1.7 會產(chǎn)生死循環(huán)、數(shù)據(jù)丟失、數(shù)據(jù)覆蓋的問題，1.8 中會有數(shù)據(jù)覆蓋的問題，以 1.8 為例，當(dāng) A 線程判斷 index 位置為空后正好掛起，B 線程開始往 index 位置的寫入節(jié)點(diǎn)數(shù)據(jù)，這時 A 線程恢復(fù)現(xiàn)場，執(zhí)行賦值操作，就把 A 線程的數(shù)據(jù)給覆蓋了；還有++size 這個地方也會造成多線程同時擴(kuò)容等問題。

25、如何規(guī)避 HashMap 的線程不安全？

單線程條件下，為避免出現(xiàn)ConcurrentModificationException，需要保證只通過HashMap本身或者只通過Iterator去修改數(shù)據(jù)，不能在Iterator使用結(jié)束之前使用HashMap本身的方法修改數(shù)據(jù)。因?yàn)橥ㄟ^Iterator刪除數(shù)據(jù)時，HashMap的modCount和Iterator的expectedModCount都會自增，不影響二者的相等性。如果是增加數(shù)據(jù)，只能通過HashMap本身的方法完成，此時如果要繼續(xù)遍歷數(shù)據(jù)，需要重新調(diào)用iterator()方法從而重新構(gòu)造出一個新的Iterator，使得新Iterator的expectedModCount與更新后的HashMap的modCount相等。

多線程條件下，可使用兩種方式：

• Collections.synchronizedMap方法構(gòu)造出一個同步Map
• 直接使用線程安全的ConcurrentHashMap。

26、HashMap 和 ConcurrentHashMap 的區(qū)別？

1. 都是 key-value 形式的存儲數(shù)據(jù)；

2. HashMap 是線程不安全的，ConcurrentHashMap 是 JUC 下的線程安全的；

3. HashMap 底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組 + 鏈表（JDK 1.8 之前）。JDK 1.8 之后是數(shù)組 + 鏈表 + 紅黑 樹。當(dāng)鏈表中元素個數(shù)達(dá)到 8 的時候，鏈表的查詢速度不如紅黑樹快，鏈表會轉(zhuǎn)為紅黑樹，紅 黑樹查詢速度快；

4. HashMap 初始數(shù)組大小為 16（默認(rèn)），當(dāng)出現(xiàn)擴(kuò)容的時候，以 0.75 * 數(shù)組大小的方式進(jìn)行擴(kuò) 容；

5. ConcurrentHashMap 在 JDK 1.8 之前是采用分段鎖來現(xiàn)實(shí)的 Segment + HashEntry， Segment 數(shù)組大小默認(rèn)是 16，2 的 n 次方；JDK 1.8 之后，采用 Node + CAS + Synchronized 來保證并發(fā)安全進(jìn)行實(shí)現(xiàn)。

27、為什么 ConcurrentHashMap 比 HashTable 效率要高？

HashTable：使用一把鎖（鎖住整個鏈表結(jié)構(gòu)）處理并發(fā)問題，多個線程競爭一把鎖，容易阻塞；

ConcurrentHashMap：

• JDK 1.7 中使用分段鎖（ReentrantLock + Segment + HashEntry），相當(dāng)于把一個 HashMap 分成多個段，每段分配一把鎖，這樣支持多線程訪問。鎖粒度：基于 Segment，包含多個 HashEntry。
• JDK 1.8 中使用CAS + synchronized + Node + 紅黑樹。鎖粒度：Node（首結(jié)點(diǎn)）（實(shí)現(xiàn) Map.Entry<K,V>）。鎖粒度降低了。

28、說說 ConcurrentHashMap中 鎖機(jī)制

JDK 1.7 中，采用分段鎖的機(jī)制，實(shí)現(xiàn)并發(fā)的更新操作，底層采用數(shù)組+鏈表的存儲結(jié)構(gòu)，包括兩個核心靜態(tài)內(nèi)部類 Segment 和 HashEntry。

①、Segment 繼承 ReentrantLock（重入鎖） 用來充當(dāng)鎖的角色，每個 Segment 對象守護(hù)每個散列映射表的若干個桶；

②、HashEntry 用來封裝映射表的鍵-值對；

③、每個桶是由若干個 HashEntry 對象鏈接起來的鏈表

JDK 1.8 中，采用Node + CAS + Synchronized來保證并發(fā)安全。取消類 Segment，直接用 table 數(shù)組存儲鍵值對；當(dāng) HashEntry 對象組成的鏈表長度超過 TREEIFY_THRESHOLD 時，鏈表轉(zhuǎn)換為紅黑樹，提升性能。底層變更為數(shù)組 + 鏈表 + 紅黑樹。

29、在 JDK 1.8 中，ConcurrentHashMap 為什么要使用內(nèi)置鎖 synchronized 來代替重入鎖 ReentrantLock？

①、粒度降低了；

②、JVM 開發(fā)團(tuán)隊沒有放棄 synchronized，而且基于 JVM 的 synchronized 優(yōu)化空間更大，更加自然。

③、在大量的數(shù)據(jù)操作下，對于 JVM 的內(nèi)存壓力，基于 API 的 ReentrantLock 會開銷更多的內(nèi)存。

30、能對ConcurrentHashMap 做個簡單介紹嗎？

①、重要的常量：　　

private transient volatile int sizeCtl; 　　

當(dāng)為負(fù)數(shù)時，-1 表示正在初始化，-N 表示 N - 1 個線程正在進(jìn)行擴(kuò)容；　　

當(dāng)為 0 時，表示 table 還沒有初始化；　　

當(dāng)為其他正數(shù)時，表示初始化或者下一次進(jìn)行擴(kuò)容的大小。

②、數(shù)據(jù)結(jié)構(gòu)：　　

Node 是存儲結(jié)構(gòu)的基本單元，繼承 HashMap 中的 Entry，用于存儲數(shù)據(jù)； 

TreeNode 繼承 Node，但是數(shù)據(jù)結(jié)構(gòu)換成了二叉樹結(jié)構(gòu)，是紅黑樹的存儲結(jié)構(gòu)，用于紅黑樹中存儲數(shù)據(jù)；　　

TreeBin 是封裝 TreeNode 的容器，提供轉(zhuǎn)換紅黑樹的一些條件和鎖的控制。

③、存儲對象時（put() 方法）：　　

1. 如果沒有初始化，就調(diào)用 initTable() 方法來進(jìn)行初始化；　　

2. 如果沒有 hash 沖突就直接 CAS 無鎖插入；　　

3. 如果需要擴(kuò)容，就先進(jìn)行擴(kuò)容；　　

4. 如果存在 hash 沖突，就加鎖來保證線程安全，兩種情況：一種是鏈表形式就直接遍歷到尾端插入，一種是紅黑樹就按照紅黑樹結(jié)構(gòu)插入；　　

5. 如果該鏈表的數(shù)量大于閥值 8，就要先轉(zhuǎn)換成紅黑樹的結(jié)構(gòu)，break 再一次進(jìn)入循環(huán) 　　

6. 如果添加成功就調(diào)用 addCount() 方法統(tǒng)計 size，并且檢查是否需要擴(kuò)容。

④、擴(kuò)容方法 transfer()：默認(rèn)容量為 16，擴(kuò)容時，容量變?yōu)樵瓉淼膬杀??！　elpTransfer()：調(diào)用多個工作線程一起幫助進(jìn)行擴(kuò)容，這樣的效率就會更高。

⑤、獲取對象時（get()方法）：　　

1. 計算 hash 值，定位到該 table 索引位置，如果是首結(jié)點(diǎn)符合就返回；　　

2. 如果遇到擴(kuò)容時，會調(diào)用標(biāo)記正在擴(kuò)容結(jié)點(diǎn) ForwardingNode.find()方法，查找該結(jié)點(diǎn)，匹配就返回；　　

3. 以上都不符合的話，就往下遍歷結(jié)點(diǎn)，匹配就返回，否則最后就返回 null。

31、熟悉ConcurrentHashMap 的并發(fā)度嗎？

程序運(yùn)行時能夠同時更新 ConccurentHashMap 且不產(chǎn)生鎖競爭的最大線程數(shù)。默認(rèn)為 16，且可以在構(gòu)造函數(shù)中設(shè)置。當(dāng)用戶設(shè)置并發(fā)度時，ConcurrentHashMap 會使用大于等于該值的最小2冪指數(shù)作為實(shí)際并發(fā)度（假如用戶設(shè)置并發(fā)度為17，實(shí)際并發(fā)度則為32）。

參考：http:///gFInl

總結(jié)

好了，就寫這么多了，文章中很多已經(jīng)不是HashMap知識點(diǎn)了，但，面試很有可能會問這些知識點(diǎn)，多準(zhǔn)備點(diǎn)也算是有備無患。

所謂天才，只不過是把別人喝咖啡的功夫都用在工作上了。

——魯迅