14,、說說resize擴容的過程

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

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

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

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

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

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

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

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

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

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

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

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,，那就需要注意以下幾點：

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

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

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

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

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

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

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

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

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

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

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

22、說說什么是 fail-fast,？

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

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

解決辦法

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

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

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

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

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

④、HashMap 默認初始化數(shù)組的大小為16,，HashTable 為 11,，前者擴容時,，擴大兩倍,，后者擴大兩倍+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é)點數(shù)據(jù),，這時 A 線程恢復(fù)現(xiàn)場,，執(zhí)行賦值操作，就把 A 線程的數(shù)據(jù)給覆蓋了,；還有++size 這個地方也會造成多線程同時擴容等問題,。

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

單線程條件下,，為避免出現(xiàn)ConcurrentModificationException，需要保證只通過HashMap本身或者只通過Iterator去修改數(shù)據(jù),，不能在Iterator使用結(jié)束之前使用HashMap本身的方法修改數(shù)據(jù),。因為通過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ù)達到 8 的時候,，鏈表的查詢速度不如紅黑樹快,，鏈表會轉(zhuǎn)為紅黑樹，紅 黑樹查詢速度快,；

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

5. ConcurrentHashMap 在 JDK 1.8 之前是采用分段鎖來現(xiàn)實的 Segment + HashEntry,， Segment 數(shù)組大小默認是 16，2 的 n 次方,；JDK 1.8 之后,，采用 Node + CAS + Synchronized 來保證并發(fā)安全進行實現(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é)點）（實現(xiàn) Map.Entry<K,V>）,。鎖粒度降低了,。

28、說說 ConcurrentHashMap中 鎖機制

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

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

②、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ā)團隊沒有放棄 synchronized,，而且基于 JVM 的 synchronized 優(yōu)化空間更大，更加自然,。

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

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

①,、重要的常量：　　

private transient volatile int sizeCtl; 　　

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

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

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

②,、數(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() 方法來進行初始化；　　

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

3. 如果需要擴容,，就先進行擴容；　　

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

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

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

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

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

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

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

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

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

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

參考：http:///gFInl

總結(jié)

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

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

——魯迅