Java HashMap和 ConcurrentHashMap 熱門面試題。

??更多關(guān)于HashMap的知識點，請戳《HashMap知識點梳理、常見面試題和源碼分析》。

??HashMap的結(jié)構(gòu)無疑是Java面試中出現(xiàn)頻率最高的一道題，此題是如此之常見，每個人都應(yīng)該信手拈來，然而，能完整回答HashMap問題的人卻是寥寥無幾。

對于一位中高級java程序員而言，若對集合類的內(nèi)部原理不了解，基本上面試都會被pass掉。故，下面從面試官的角度梳理了一份精選面試題，來聊聊一位候選者應(yīng)該對HashMap了解到什么程度才算是合格。

??樓蘭胡楊希望大家不但研究過JDK中HashMap的源代碼，而且熟悉不同版本JDK中使用的優(yōu)化機制。當然了，如果具有手動實現(xiàn)HashMap的能力就更優(yōu)秀了。

在日常開發(fā)中使用過的java集合類有哪些

??一般應(yīng)聘者都會回答ArrayList，LinkedList，HashMap，HashSet等等。如果連這幾個集合類都不知道，基本上可以pass了。

談一下HashMap的特性

• HashMap初始化時使用懶加載機制，只初始化變量，未初始化數(shù)組，數(shù)組在首次添加元素時初始化。
• 存儲鍵值對，實現(xiàn)快速存取。key值不可重復(fù)，若key值重復(fù)則覆蓋。
• 鍵和值位置都可以是null，但是鍵位置只能存在唯一一個null。
• 非同步，線程不安全。
• 底層是hash表，不保證有序(比如插入的順序)。
• 鏈表長度不小于8并且數(shù)組長度大于64，才將鏈表轉(zhuǎn)換成紅黑樹，變成紅黑樹的目的是提高搜索速度，高效查詢

HashMap 的數(shù)據(jù)結(jié)構(gòu)是什么

??自Java 8 開始，哈希表結(jié)構(gòu)（鏈表散列）由數(shù)組+單鏈表+紅黑樹實現(xiàn)，結(jié)合Node數(shù)組和單鏈表的優(yōu)點。當鏈表長度不小于 8且數(shù)組長度不小于64時，鏈表轉(zhuǎn)換為紅黑樹；否則，擴容。數(shù)組是HashMap的主題，鏈表和紅黑樹主要是為了解決哈希沖突（拉鏈法解決沖突）。

單鏈表和紅黑樹相互轉(zhuǎn)換的條件是什么

??當單鏈表長度不小于8，并且桶的個數(shù)不小于64時，將單鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時間。

??同樣，后續(xù)如果由于刪除或者其它原因調(diào)整了大小，當紅黑樹的節(jié)點數(shù)不大于 6時，又會轉(zhuǎn)換為鏈表。

??hashCode 均勻分布時，TreeNode 用到的機會很小。理想情況下bin 中節(jié)點的分布遵循泊松分布，一個 bin 中鏈表長度達到 8 的概率（0.00000006）不足千萬分之一，因此將轉(zhuǎn)換的閾值設(shè)為 8。

??通常如果 hash 算法正常的話，鏈表的長度也不會很長，那么紅黑樹也不會帶來明顯的查詢時間上的優(yōu)勢，反而會增加空間負擔（TreeNode的大小大約是常規(guī)節(jié)點Node的兩倍）。所以通常情況下，并沒有必要轉(zhuǎn)為紅黑樹。

鏈表和紅黑樹相互轉(zhuǎn)換的閾值為什么是 8 和 6

??如果選擇6和8，中間有個差值7可以有效防止鏈表和紅黑樹頻繁轉(zhuǎn)換。如果一個 HashMap 不停地進行插入和刪除元素，鏈表的個數(shù)一直在 8 左右徘徊，這種情況會頻繁地進行紅黑樹和鏈表的相互轉(zhuǎn)換，效率很低。

??hashCode 均勻分布時，TreeNode 用到的機會很小。理想情況下bin 中節(jié)點的分布遵循泊松分布，一個 bin 中鏈表長度達到 8 的概率（0.00000006）不足千萬分之一，因此將轉(zhuǎn)換的閾值設(shè)為 8。

為什么要在數(shù)組長度不小于64之后，鏈表才會進化為紅黑樹

??如果在數(shù)組比較小時出現(xiàn)紅黑樹結(jié)構(gòu)，反而會降低效率，而紅黑樹需要通過左旋、右旋和變色操作來保持平衡。同時數(shù)組長度小于64時，搜索時間相對要快些，總之是為了加快搜索速度，提高性能。

??Java 8 以前HashMap的實現(xiàn)是數(shù)組+鏈表，即使哈希函數(shù)取得再好，也很難達到元素百分百均勻分布。當HashMap中有大量的元素都存放在同一個桶中時，這個桶下有一條長長的鏈表，此時HashMap就相當于單鏈表，假如單鏈表有n個元素，遍歷的時間復(fù)雜度就從O（1）退化成O（n），完全失去了它的優(yōu)勢。為了解決此種情況，Java 8中引入了紅黑樹（查找的時間復(fù)雜度為O（logn））。

HashMap 的容量如何確定

??容量就是HashMap中的數(shù)組大小，是由 capacity 這個參數(shù)確定的。默認是16，也可以構(gòu)造時傳入，最大限制是1<<30；

??HashMap采用懶加載機制，也就是說在執(zhí)行new HashMap()的時候，構(gòu)造方法并沒有在構(gòu)造HashMap實例的同時也初始化實例里的數(shù)組。那么什么時候才去初始化數(shù)組呢？答案是只有在第一次需要用到這個數(shù)組的時候才會去初始化它，就是在你往HashMap里面put元素的時候。

loadFactor 是什么

??loadFactor 是裝載因子，主要目的是用來確認table 數(shù)組是否需要動態(tài)擴展，默認值是0.75，比如table 數(shù)組大小為 16，裝載因子為 0.75 時，threshold 就是12，當 table 的實際大小超過 12 時，table就需要動態(tài)擴容。

??空間換時間：如果希望加快Key查找的時間，還可以進一步降低加載因子，加大初始容量大小，以降低哈希沖突的概率。

??性能分析：空桶太多會浪費空間，如果使用的太滿則會嚴重影響操作的性能。

HashMap使用了哪些方法來有效解決哈希沖突

??1、使用鏈地址法（使用散列表）來鏈接擁有相同hash值的數(shù)據(jù)。

??2、使用2次擾動函數(shù)（hash函數(shù)）降低哈希沖突的概率，使得數(shù)據(jù)分布更均勻。

??3、引入紅黑樹進一步降低遍歷的時間復(fù)雜度。

為什么數(shù)組長度要保證為2的冪次方

??只有當數(shù)組長度為2的冪次方時，h&(length-1)才等價于h%length，即實現(xiàn)了key的定位，2的冪次方也可以減少哈希沖突次數(shù)，提高HashMap的查詢效率。

??如果 length 為 2 的次冪 則 length-1 轉(zhuǎn)化為二進制必定是 11111……的形式，在于 h 的二進制與操作效率會非常的快，而且空間不浪費；如果 length 不是 2 的次冪，比如 length 為 15，則 length - 1 為 14，對應(yīng)的二進制為 1110，在于 h 與操作，最后一位都為 0 ，而 0001，0011，0101，1001，1011，0111，1101 這幾個位置永遠都不能存放元素了，空間浪費相當大，更糟的是這種情況中，數(shù)組可以使用的位置比數(shù)組長度小了很多，這意味著進一步增加了碰撞的幾率，減慢了查詢的效率！這樣就會造成空間的浪費。

為什么是兩次擾動

??加大哈希值低位的隨機性，使得分布更均勻，從而提高數(shù)組下標位置的隨機性和均勻性，最終減少哈希沖突。兩次就夠了，已經(jīng)達到了高位和低位同時參與運算的目的。

數(shù)組擴容機制是什么

??擴容方法是resize()方法。

• 默認是空數(shù)組，初始化的容量是16，即桶的個數(shù)默認為16；
• 當總元素個數(shù)超過容量??加載因子時，進行數(shù)組擴容；
• 創(chuàng)建一個新的數(shù)組，其大小為舊數(shù)組大小的兩倍，并重新計算舊數(shù)組中結(jié)點的存儲位置。
• 結(jié)點在新數(shù)組中的位置只有兩種，原下標位置或原下標+舊數(shù)組的大小。

??擴容帶來的危害：在數(shù)據(jù)量很大的情況下擴容將會帶來性能的損失，在性能要求很高的地方，這種損失可能很致命。擴容太頻繁就會導(dǎo)致內(nèi)存抖動問題，增加瞬間的內(nèi)存消耗和性能消耗，因此在創(chuàng)建HashMap的時候，如果能預(yù)知初始數(shù)據(jù)量的大小，在構(gòu)造的時候可以設(shè)置初始容量，也可以設(shè)置擴容因子。

為什么要重新Hash,直接復(fù)制過去不好嗎

??哈希函數(shù)中，包括對數(shù)組長度取模，故長度擴大以后，哈希函數(shù)也隨之改變。

談一下hashMap中put是如何實現(xiàn)的

??1.基于key的hashcode值計算哈希值（與Key.hashCode的高16位做異或運算）
??2.如果散列表為空時，調(diào)用resize()初始化散列表
??3.如果沒有發(fā)生哈希碰撞(hash值相同)，直接添加元素到散列表中去
??4.如果發(fā)生了哈希碰撞，進行三種判斷
????4.1:若key地址相同或者equals后內(nèi)容相同，則替換舊值
????4.2:如果是紅黑樹結(jié)構(gòu)，就調(diào)用樹的插入方法
????4.3：鏈表結(jié)構(gòu)，循環(huán)遍歷直到鏈表中某個節(jié)點為空，尾插法進行插入，插入之后判斷鏈表是否樹化：當鏈表長度不小于 8且數(shù)組長度不小于64時，鏈表轉(zhuǎn)換為紅黑樹。
??5.如果桶滿了，即元素個數(shù)大于閾值，則resize進行擴容

??hashCode 是定位的，用于確認數(shù)組下標；equals是定性的，比較兩者是否相等。

hashMap中g(shù)et函數(shù)是如何實現(xiàn)的

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

Java 7 與 Java 8 中，HashMap的區(qū)別

??1.數(shù)據(jù)結(jié)構(gòu)不同 Java 7采用Entry數(shù)組+單鏈表的數(shù)據(jù)結(jié)構(gòu)，而java 8 采用Node數(shù)組+單鏈表+紅黑樹，把時間復(fù)雜度從O（n）變成O（logN），提高了效率。這是Java 7與Java 8中HashMap實現(xiàn)的最大區(qū)別。

??1.hash沖突解決方案不同 發(fā)生hash沖突時，在Java 7中采用頭插法，新元素插入到鏈表頭中，即新元素總是添加到數(shù)組中，舊元素移動到鏈表中。 Java 8會優(yōu)先判斷該節(jié)點的數(shù)據(jù)結(jié)構(gòu)式是紅黑樹還是鏈表，如果是紅黑樹，則在紅黑樹中插入數(shù)據(jù)；如果是鏈表，則采用尾插法，將數(shù)據(jù)插入到鏈表的尾部，然后判斷是否需要轉(zhuǎn)成紅黑樹。

??鏈表插入元素時，Java 7用的是頭插法，而Java 8及之后使用的都是尾插法，那么他們?yōu)槭裁匆@樣做呢？因為JDK1.7是用單鏈表進行的縱向延伸，當采用頭插法時會容易出現(xiàn)逆序且環(huán)形鏈表死循環(huán)問題。但是在JDK1.8之后是因為加入了紅黑樹使用尾插法，能夠避免出現(xiàn)逆序且鏈表死循環(huán)的問題。
頭插法優(yōu)點: resize后transfer數(shù)據(jù)時不需要遍歷鏈表到尾部再插入；最近put的可能等下就被get，頭插遍歷到鏈表頭就匹配到了。

??2.擴容機制不同 Java 7:在擴容resize（）過程中，采用單鏈表的頭插入方式，在線程下將舊數(shù)組上的數(shù)據(jù) 轉(zhuǎn)移到 新數(shù)組上時，容易出現(xiàn)死循環(huán)。此時若（多線程）并發(fā)執(zhí)行 put（）操作，一旦出現(xiàn)擴容情況，則容易出現(xiàn)環(huán)形鏈表，從而在獲取數(shù)據(jù)、遍歷鏈表時形成死循環(huán)（Infinite Loop），即死鎖的狀態(tài)。

??Java 8:由于 Java 8 轉(zhuǎn)移數(shù)據(jù)操作 = 按舊鏈表的正序遍歷鏈表、在新鏈表的尾部依次插入，所以不會出現(xiàn)鏈表 逆序、倒置的情況，故不容易出現(xiàn)環(huán)形鏈表的情況。

??3. 擴容后存放位置不同 java 7 受rehash影響，java 8 調(diào)整后是原位置 or 原位置+舊容量。

??使用HashMap時，樓蘭胡楊的一些經(jīng)驗之談：

1. 使用時設(shè)置初始值，避免多次擴容的性能消耗。
2. 使用自定義對象作為key時，需要重寫hashCode和equals方法。
   3.多線程下,使用CurrentHashMap代替HashMap。

HashMap的key一般使用什么數(shù)據(jù)類型

??String、Integer等包裝類的特性可以保證哈希值的不可更改性和計算準確性，可以有效地減少哈希碰撞的概率。

??都是final類型，即不可變類，作為不可變類天生是線程安全的。這些包裝類已重寫了equals()和hashCode()等方法，保證key的不可更改性，不會存在多次獲取哈希值時哈希值卻不相同的情況。

如果讓自己的創(chuàng)建的類作為HashMap的key，應(yīng)該怎么實現(xiàn)

??重寫hashCode()和equals()方法。

??重寫hashCode()是因為需要計算存儲數(shù)據(jù)的存儲位置，需要注意不要試圖從散列碼計算中排除掉一個對象的關(guān)鍵部分來提高性能，這樣雖然能更快但可能會導(dǎo)致更多的Hash碰撞。重寫equals()方法，需要遵守自反性、對稱性、傳遞性、一致性以及對于任何非null的引用值x，x.equals(null)必須返回false的這幾個特性，目的是為了保證key在哈希表中的唯一性。

HashMap為什么由Java 7 的頭插法改為Java 8的尾插法

??當HashMap要在鏈表里插入新的元素時，在Java 8之前是將元素插入到鏈表頭部，自Java 8開始插入到鏈表尾部（Java 8用Node對象替代了Entry對象）。Java 7 插入鏈表頭部，是考慮到新插入的數(shù)據(jù)，更可能作為熱點數(shù)據(jù)被使用，放在頭部可以減少查找時間。Java 8改為插入鏈表尾部是為了防止環(huán)化。因為resize的賦值方式，也就是使用了單鏈表的頭插入方式，同一位置上新元素總會被放在鏈表的頭部位置，在舊數(shù)組中同一條Entry鏈上的元素，通過重新計算索引位置后，有可能被放到了新數(shù)組的不同位置上。

HashMap與Hashtable的區(qū)別是什么

??HashMap與Hashtable的區(qū)別見如下表格：

不同點	HashMap	Hashtable
數(shù)據(jù)結(jié)構(gòu)	數(shù)組 + 單鏈表 + 紅黑樹	數(shù)組+鏈表
繼承的類	AbstractMap	Dictonary，但二者都實現(xiàn)了map接口
線程安全	否	是
性能搞定	高	低，因為需要保證線程安全
默認初始化容量	16	低
擴容方式	數(shù)組大小×2	數(shù)組大小×2+1
底層數(shù)組容量	一定為2的整數(shù)冪次	不要求
hash值算法	(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)	key.hashCode()
數(shù)組下標計算方法	(n-1) & hash	hash&0x7FFFFFFF%length
key-value是否允許null	是	否
是否提供contains方法	有containsvalue和containsKey方法	有contains方法方法
遍歷方式	Iterator	Iterator 和 Enumeration

??看完之后，是不是可以和面試官PK三分鐘了？更多內(nèi)容請戳《面試題:HashMap和Hashtable的區(qū)別和聯(lián)系》。

HashMap為什么線程不安全

??多線程下擴容死循環(huán)。JDK1.7中的HashMap使用頭插法插入元素，在多線程的環(huán)境下，擴容的時候有可能導(dǎo)致環(huán)形鏈表的出現(xiàn)，形成死循環(huán)。因此JDK1.8使用尾插法插入元素，在擴容時會保持鏈表元素原本的順序，不會出現(xiàn)環(huán)形鏈表的問題。

??多線程的put可能導(dǎo)致元素的丟失。多線程同時執(zhí)行put操作，如果兩個不同key計算出來的索引位置是相同的，那會造成前一個key被后一個key覆蓋，從而導(dǎo)致元素丟失。此問題在JDK1.7和JDK1.8中都存在。

??put和get并發(fā)時，可能導(dǎo)致get為null。線程1執(zhí)行put時，因為元素個數(shù)超出threshold而導(dǎo)致rehash，線程2此時執(zhí)行g(shù)et，有可能導(dǎo)致這個問題，此問題在JDK1.7和JDK1.8中都存在。

jdk8中對HashMap做了哪些改變

• 在java 8中，引入了紅黑樹，鏈表可以轉(zhuǎn)換為紅黑樹。
• 發(fā)生hash碰撞時，java 7 會在鏈表的頭部插入，而java 8會在鏈表的尾部插入。
• 在java 8中，Entry被Node替代(換了一個馬甲。

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

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

HashMap為什么引入紅黑樹

??Java8以前 HashMap 的實現(xiàn)是 數(shù)組+鏈表，即使哈希函數(shù)取得再好，也很難達到元素百分百均勻分布。當 HashMap 中有大量的元素發(fā)生哈希碰撞時，這些元素都被存放到同一個桶中，從而形成一條長長的鏈表，此時 HashMap 就相當于一個單鏈表，遍歷的時間復(fù)雜度會退化到O(n)，完全失去了它的優(yōu)勢。針對這種情況，JAVA 8 中引入了紅黑樹來優(yōu)化這個問題，紅黑樹的好處就是它的自平衡性，n個節(jié)點的樹的查找時間復(fù)雜度只有 O(log n)。

如果兩個鍵的哈希值相同，如何獲取值對象

??哈希值相同，通過equals比較內(nèi)容獲取值對象。

說說你對紅黑樹的見解

• 每個節(jié)點非紅即黑。
• 根節(jié)點總是黑色的。
• 如果節(jié)點是紅色的，則它的子節(jié)點必須是黑色的（反之不一定）；
• 每個葉子節(jié)點都是黑色的空節(jié)點（NIL節(jié)點）；
• 從根節(jié)點到葉節(jié)點或空子節(jié)點的每條路徑，必須包含相同數(shù)目的黑色節(jié)點（即相同的黑色高度）。

為什么是16？為什么必須是2的冪？如果輸入值不是2的冪比如10會怎么樣

??為什么槽位數(shù)必須使用2^n

①為了使得數(shù)據(jù)均勻分布，減少哈希碰撞。因為確定數(shù)組位置使用的位運算，若數(shù)據(jù)不是2的次冪則會增加哈希碰撞的次數(shù)和浪費數(shù)組空間。(PS:其實若不考慮效率，求余也可以就不用位運算了也不用長度必需為2的冪次)。

??輸入數(shù)據(jù)若不是2的冪，HashMap通過一通位移運算和或運算得到的肯定是2的冪次數(shù)，并且是離那個數(shù)最近的數(shù)字。

②等價于length取模

??當length總是2的n次方時，h& (length-1)運算等價于對length取模，也就是h%length，但是&比%具有更高的效率。位運算的運算效率高于算術(shù)運算，原因是算術(shù)運算還是會被轉(zhuǎn)化為位運算。最終目的還是為了讓哈希后的結(jié)果更均勻的分部，減少哈希碰撞，提升hashmap的運行效率。

為什么String, Interger這樣的wrapper類適合作為鍵

??String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過了，而且String最為常用。因為String是不可變的，也是final的，而且已經(jīng)重寫了equals()和hashCode()方法了。其它的wrapper類也有這個特點。不可變性是必要的，因為為了要計算hashCode()，就要防止鍵值改變，如果鍵值在放入時和獲取時返回不同的hashcode的話，那么就不能從HashMap中找到你想要的對象。不可變性還有其它的優(yōu)點如線程安全。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的，那么請這么做吧。因為獲取對象的時候要用到equals()和hashCode()方法，那么鍵對象正確的重寫這兩個方法是非常重要的。如果兩個不相等的對象返回不同的hashcode的話，那么碰撞的幾率就會小些，這樣就能提高HashMap的性能。

如果不重寫作為可以的Bean的hashCode()方法，是否會對性能帶來影響

??這個問題非常好，仁者見仁智者見智。按照我掌握的知識來說，如果一個哈希方法寫得不好，直接的影響是，在向HashMap中添加元素的時候會更頻繁地造成哈希沖突，因此最終增加了耗時。但是自從Java 8開始，這種影響不再像前幾個版本那樣顯著了，因為當哈希沖突的發(fā)生超出了一定的限度之后，鏈表將會被替換成紅黑樹，這時你仍可以得到O(logN)的開銷，優(yōu)于鏈表類的O(n)。

談一下當兩個對象的哈希值相等時會怎么樣

??會產(chǎn)生哈希碰撞，若key值相同則替換舊值，不然采用尾插法鏈接到鏈表后面，鏈表長度超過閾值8且桶的個數(shù)大于64就轉(zhuǎn)為紅黑樹存儲。

請解釋一下HashMap的參數(shù)loadFactor，它的作用是什么

??loadFactor是負載因子，表示HashMap的擁擠程度，影響hash操作到同一個數(shù)組位置的概率。默認loadFactor等于0.75，當HashMap里面容納的元素已經(jīng)達到HashMap數(shù)組長度的75%時，表示HashMap太擠了，需要擴容，在HashMap的構(gòu)造器中可以定制loadFactor。

Java 8 HashMap 擴容之后，舊元素存放位置是什么

??HashMap 在擴容的時候會創(chuàng)建一個新的 Node<K,V>[] 對象，用于存放擴容之后的鍵值對，并將舊的Node數(shù)組（其大小記作n）置空；至于舊值移動到新的節(jié)點時存放于哪個節(jié)點，是根據(jù) (e.hash & oldCap) == 0 來判斷的：
① 等于0時，則其索引位置h不變;
② 不等于0時，則其在新數(shù)組的索引位置=原索引位置+舊數(shù)組長度n。

你了解重新調(diào)整HashMap大小存在什么問題嗎

??當hashMap因為擴容而調(diào)整hashMap的大小時，會導(dǎo)致之前計算出來的索引下標無效，所以所有的節(jié)點都需要重新進行哈希運算，結(jié)果就是帶來時間上的浪費。故建議盡量避免hashMap調(diào)整大小，所以我們使用hashMap的時候要給它設(shè)置一個初始容量，此值要大于hashMap中存放的節(jié)點個數(shù)。

你知道哈希函數(shù)的實現(xiàn)嗎？為什么要這樣實現(xiàn)？還有哪些hash函數(shù)的實現(xiàn)方式

??Java 8 中使用了異或運算，通過 key的hashCode() 的高 16 位異或低 16 位實現(xiàn)：(h = k.hashCode()) ^ (h >>> 16)，此實現(xiàn)方案主要是從速度、功效和質(zhì)量三個角度來考量的，用于減少系統(tǒng)的開銷，也可以避免因為高位沒有參與下標的計算而造成哈希碰撞。

??其它實現(xiàn)方式還有平方取中法，除留余數(shù)法，偽隨機數(shù)法等。

??如果面試者的技術(shù)面比較寬，或者算法基礎(chǔ)以及數(shù)論基礎(chǔ)比較好，這個問題才可以做很好的回答。首先，hashCode()不要求唯一但是要盡可能的均勻分布，而且算法效率要盡可能的快。

??如果都結(jié)束了，不要忘了再問一句你知道hash攻擊嗎？有避免手段嗎？就看面試者對各個jdk版本對HashMap的優(yōu)化是否了解了。這就引出了另一個數(shù)據(jù)結(jié)構(gòu)紅黑樹了。可以根據(jù)崗位需要繼續(xù)考察rb-tree，b-tree，lsm-tree等常用數(shù)據(jù)結(jié)構(gòu)以及典型應(yīng)用場景。

哈希函數(shù)為什么要用異或運算符

??保證了對象的 hashCode 的 32 位值只要有一位發(fā)生改變，返回的 hash值就會改變。盡可能的減少哈希碰撞。

能否讓HashMap實現(xiàn)線程安全

??HashMap可以通過下面的語句進行同步：Collections.synchronizeMap(hashMap)。 synchronizedMap()方法返回一個SynchronizedMap類的對象，而在SynchronizedMap類中使用了synchronized來保證對Map的操作是線程安全的，故效率其實也不高。

如果多個線程操作同一個HashMap對象會產(chǎn)生哪些非正常現(xiàn)象？

??HashMap在多線程環(huán)境下操作可能會導(dǎo)致程序死循環(huán)。

??其實這已經(jīng)開始考察候選人對并發(fā)知識的掌握情況了。HashMap在resize的時候，如果多個線程并發(fā)操作如何導(dǎo)致死鎖的。面試者不一定知道，但是可以讓面試者分析。畢竟很多類庫在并發(fā)場景中不恰當使用HashMap導(dǎo)致過生產(chǎn)問題。

Java 中的另一個線程安全的、與 HashMap 極其類似的類是什么？同樣是線程安全，它與 Hashtable 在線程同步上有什么不同

??ConcurrentHashMap 類（是 Java并發(fā)包 java.util.concurrent 中提供的一個線程安全且高效的 HashMap 實現(xiàn)）。Hashtable 是使用 synchronized 關(guān)鍵字加鎖的原理（就是對對象加鎖）；而針對ConcurrentHashMap，在 JDK 7 中采用分段鎖的方式，而JDK 8 中直接采用了CAS（無鎖算法）+ synchronized。

Get方法的流程是怎樣的

??先調(diào)用Key的hashcode方法拿到對象的hash值，然后用hash值對第一維數(shù)組的長度進行取模，得到數(shù)組的下標。這個數(shù)組下標所在的元素就是第二維鏈表的表頭。然后遍歷這個鏈表，使用Key的equals同鏈表元素進行比較，匹配成功即返回鏈表元素里存放的值。

Get方法的時間復(fù)雜度是多少

??答：是O(1)。很多人在回答這道題時腦細胞會出現(xiàn)短路現(xiàn)象，開始懷疑人生。明明是O(1)啊，平時都記得牢牢的，又在質(zhì)疑由于Get方法的流程里需要遍歷鏈表，難道遍歷的時間復(fù)雜度不是O(n)么？

假如HashMap里的元素有100w個，請問鏈表的長度大概是多少

??鏈表的長度很短，相比總元素的個數(shù)可以忽略不計。這個時候小伙伴們的眼睛通常會開始發(fā)光，很童貞。作為面試官是很喜歡看到這種眼神的。我使用反射統(tǒng)計過HashMap里面鏈表的長度，在HashMap里放了100w個隨機字符串鍵值對，發(fā)現(xiàn)鏈表的長度幾乎從來沒有超過7這個數(shù)字，當我增大loadFactor的時候，才會偶爾冒出幾個長度為8的鏈表來。

請說明一下HashMap擴容的過程

??擴容需要重新分配一個新數(shù)組，新數(shù)組是老數(shù)組的2倍長，然后遍歷整個老結(jié)構(gòu)，把所有的元素挨個重新hash分配到新結(jié)構(gòu)中去。

??這個rehash的過程是很耗時的，特別是HashMap很大的時候，會導(dǎo)致程序卡頓，而2倍內(nèi)存的關(guān)系還會導(dǎo)致內(nèi)存瞬間溢出，實際上是3倍內(nèi)存，因為老結(jié)構(gòu)的內(nèi)存在rehash結(jié)束之前還不能立即回收。那為什么不能在HashMap比較大的時候擴容擴少一點呢，關(guān)于這個問題我也沒有非常滿意的答案，我只知道hash的取模操作使用的是按位操作，按位操作需要限制數(shù)組的長度必須是2的指數(shù)。另外就是Java堆內(nèi)存底層用的是TcMalloc這類library，它們在內(nèi)存管理的分配單位就是以2的指數(shù)的單位，2倍內(nèi)存的遞增有助于減少內(nèi)存碎片，減少內(nèi)存管理的負擔。

你了解Redis么，你知道Redis里面的字典是如何擴容的嗎

好，如果這道題你也回答正確了，恭喜你，毫無無疑，你是一位很有錢途的高級程序員。

HashMap & ConcurrentHashMap 的區(qū)別

??除了加鎖，原理上無太大區(qū)別。另外，HashMap 的鍵值對允許有null，但是ConCurrentHashMap 都不允許。

HashMap、LinkedHashMap和TreeMap 有什么區(qū)別

??LinkedHashMap 保存了記錄的插入順序，在用 Iterator 遍歷時，先取到的記錄肯定是先插入的；遍歷比 HashMap 慢；TreeMap 實現(xiàn) SortMap 接口，能夠把它保存的記錄根據(jù)鍵排序（默認按鍵值升序排序，也可以指定排序的比較器）。

為什么 ConcurrentHashMap 比 Hashtable 效率高

??Hashtable 使用一把鎖（鎖住整個鏈表結(jié)構(gòu)）處理并發(fā)問題，多個線程競爭一把鎖容易導(dǎo)致阻塞；而ConcurrentHashMap降低了鎖粒度。ConcurrentHashMap在JDK 7 中使用分段鎖（ReentrantLock + Segment + HashEntry），相當于把一個 HashMap 分成多個段，每段分配一把鎖，這樣支持多線程訪問。鎖粒度：基于 Segment，包含多個 HashEntry。在JDK 8 中，使用 CAS + synchronized + Node + 紅黑樹，鎖粒度為Node（首結(jié)點）（實現(xiàn) Map.Entry）。

ConcurrentHashMap 在 Java 8 中，為什么要使用內(nèi)置鎖 synchronized 來代替重入鎖 ReentrantLock

??①、粒度降低了。

??每擴容一次，ConcurrentHashMap的并發(fā)度就增加一倍。

??②、獲得JVM的支持。

??在大量的數(shù)據(jù)操作下，對于 JVM 的內(nèi)存壓力，基于 API 的 可重入鎖 ReentrantLock 會開銷更多的內(nèi)存，而且后續(xù)的性能優(yōu)化空間更小。而且JVM 開發(fā)團隊沒有放棄 synchronized，JVM能夠在運行時做出更大的優(yōu)化空間更大：鎖粗化、鎖消除、鎖自旋等等，這就使得synchronized能夠隨著JDK版本的升級而重構(gòu)代碼的前提下獲得性能上的提升。

??③、減少內(nèi)存開銷

??假如使用可重入鎖獲得同步支持，那么每個節(jié)點都需要通過繼承AQS來獲得同步支持。但并不是每個節(jié)點都需要獲得同步支持的，只有鏈表的頭結(jié)點（紅黑樹的根節(jié)點）需要同步，這無疑造成了巨大的內(nèi)存開銷。

ConcurrentHashMap 的并發(fā)度是什么

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

ConcurrentHashMap 加鎖機制

??它加鎖的場景分為兩種：

??1、沒有發(fā)生hash沖突的時候，添加元素的位置在數(shù)組中是空的，使用CAS的方式來加入元素，這里加鎖的粒度是數(shù)組中的元素。

??2、如果出現(xiàn)了hash沖突，添加的元素的位置在數(shù)組中已經(jīng)有了值，那么又存在三種情況。
????（1）key相同，則用新的元素覆蓋舊的元素。
????（2）如果數(shù)組中的元素是鏈表的形式，那么將新的元素掛載在鏈表尾部。
????（3）如果數(shù)組中的元素是紅黑樹的形式，那么將新的元素加入到紅黑樹。

??第二種場景使用的是synchronized加鎖，鎖住的對象就是鏈表頭節(jié)點（紅黑樹的根節(jié)點），加鎖的粒度和第一種情況相同。

??結(jié)論：ConcurrentHashMap分段加鎖機制其實鎖住的就是數(shù)組中的元素，當操作數(shù)組中不同的元素時，是不會產(chǎn)生競爭的。

ConcurrentHashMap 存儲對象的過程

1> 如果沒有初始化，就調(diào)用 initTable() 方法來進行初始化；
2> 如果沒有哈希沖突就直接 CAS 無鎖插入；
3> 如果需要擴容，就先進行擴容；
4> 如果存在哈希沖突，就加鎖來保證線程安全，兩種情況：一種是鏈表形式就直接遍歷到尾端插入，一種是紅黑樹就按照紅黑樹結(jié)構(gòu)插入；
5> 如果該鏈表長度大于閥值 8（且數(shù)組中元素數(shù)量大于64），就要先轉(zhuǎn)換成紅黑樹的結(jié)構(gòu)。

ConcurrentHashMap get操作需要加鎖嗎？線程安全嗎

??get 方法不需要加鎖。因為 Node 的元素 value 和指針 next 是用 volatile 修飾的，在多線程環(huán)境下線程A修改節(jié)點的 value 或者新增節(jié)點的時候是對線程B可見的。這也是它比其它并發(fā)集合比如 Hashtable、用 Collections.synchronizedMap()包裝的 HashMap 效率高的原因之一。

如何保證 HashMap 總是使? 2 的冪次作為桶的??

  /**
     \*  Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

HashSet 與 HashMap 的區(qū)別

??HashSet與HashMap的擴容機制一樣，區(qū)別見如下表格：

不同點	HashMap	HashSet
實現(xiàn)的接口	Map接口	Set接口
存儲方式	存儲鍵值對	存儲對象
存儲方法	使用put函數(shù)	使用add函數(shù)
性能高低	快，因為使用唯一的鍵來獲取對象	慢
默認初始化容量	16	低
哈希值	使用鍵對象計算哈希值	使用成員對象計算哈希值

結(jié)束語

??眼界不凡，前途無量。攻城獅們，加油吧！樓蘭胡楊祝君平步青云。

Reference

• http://www.rzrgm.cn/Young111/p/11519952.html
• https://zhuanlan.zhihu.com/p/32355676

• https://zhuanlan.zhihu.com/p/40760616