1、HashMap 的數(shù)據(jù)結(jié)構(gòu)？

哈希表結(jié)構(gòu)（鏈表散列：數(shù)組+鏈表）實(shí)現(xiàn)，結(jié)合數(shù)組和鏈表的優(yōu)點(diǎn)。當(dāng)鏈表長度超過 8 時(shí)，鏈表轉(zhuǎn)換為紅黑樹。

transient Node<K,V>[] table;

2、HashMap 的工作原理？

HashMap 底層是 hash 數(shù)組和單向鏈表實(shí)現(xiàn)，數(shù)組中的每個(gè)元素都是鏈表，由 Node 內(nèi)部類（實(shí)現(xiàn) Map.Entry接口）實(shí)現(xiàn)，HashMap 通過 put & get 方法存儲(chǔ)和獲取。

存儲(chǔ)對(duì)象時(shí)，將 K/V 鍵值傳給 put() 方法：

調(diào)用 hash(K) 方法計(jì)算 K 的 hash 值，然后結(jié)合數(shù)組長度，計(jì)算得數(shù)組下標(biāo)；

調(diào)整數(shù)組大?。ó?dāng)容器中的元素個(gè)數(shù)大于 capacity * loadfactor 時(shí)，容器會(huì)進(jìn)行擴(kuò)容resize 為 2n）；

• 如果 K 的 hash 值在 HashMap 中不存在，則執(zhí)行插入，若存在，則發(fā)生碰撞；
• 如果 K 的 hash 值在 HashMap 中存在，且它們兩者 equals 返回 true，則更新鍵值對(duì)；
• 如果 K 的 hash 值在 HashMap 中存在，且它們兩者 equals 返回 false，則插入鏈表的尾部（尾插法）或者紅黑樹中（樹的添加方式）。（JDK 1.7 之前使用頭插法、JDK 1.8 使用尾插法）（注意：當(dāng)碰撞導(dǎo)致鏈表大于 TREEIFY_THRESHOLD = 8 時(shí)，就把鏈表轉(zhuǎn)換成紅黑樹）

獲取對(duì)象時(shí)，將 K 傳給 get() 方法：

• 調(diào)用 hash(K) 方法（計(jì)算 K 的 hash 值）從而獲取該鍵值所在鏈表的數(shù)組下標(biāo)；
• 順序遍歷鏈表，equals()方法查找相同 Node 鏈表中 K 值對(duì)應(yīng)的 V 值。

hashCode 是定位的，存儲(chǔ)位置；equals是定性的，比較兩者是否相等。

3、當(dāng)兩個(gè)對(duì)象的 hashCode 相同會(huì)發(fā)生什么？

因?yàn)?hashCode 相同，不一定就是相等的（equals方法比較），所以兩個(gè)對(duì)象所在數(shù)組的下標(biāo)相同，"碰撞"就此發(fā)生。又因?yàn)?HashMap 使用鏈表存儲(chǔ)對(duì)象，這個(gè) Node 會(huì)存儲(chǔ)到鏈表中。

4、你知道 hash 的實(shí)現(xiàn)嗎？為什么要這樣實(shí)現(xiàn)？

JDK 1.8 中，是通過 hashCode() 的高 16 位異或低 16 位實(shí)現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度，功效和質(zhì)量來考慮的，減少系統(tǒng)的開銷，也不會(huì)造成因?yàn)楦呶粵]有參與下標(biāo)的計(jì)算，從而引起的碰撞。

5、為什么要用異或運(yùn)算符？

保證了對(duì)象的 hashCode 的 32 位值只要有一位發(fā)生改變，整個(gè) hash() 返回值就會(huì)改變。盡可能的減少碰撞。

6、HashMap 的 table 的容量如何確定？

loadFactor 是什么？該容量如何變化？這種變化會(huì)帶來什么問題？

table 數(shù)組大小是由 capacity 這個(gè)參數(shù)確定的，默認(rèn)是16，也可以構(gòu)造時(shí)傳入，最大限制是1<<30；

loadFactor 是裝載因子，主要目的是用來確認(rèn)table 數(shù)組是否需要?jiǎng)討B(tài)擴(kuò)展，默認(rèn)值是0.75，比如table 數(shù)組大小為 16，裝載因子為 0.75 時(shí)，threshold 就是12，當(dāng) table 的實(shí)際大小超過 12 時(shí)，table就需要?jiǎng)討B(tài)擴(kuò)容；

擴(kuò)容時(shí)，調(diào)用 resize() 方法，將 table 長度變?yōu)樵瓉淼膬杀叮ㄗ⒁馐?table 長度，而不是 threshold）；

如果數(shù)據(jù)很大的情況下，擴(kuò)展時(shí)將會(huì)帶來性能的損失，在性能要求很高的地方，這種損失很可能很致命。

7、HashMap中put方法的過程？

答：“調(diào)用哈希函數(shù)獲取Key對(duì)應(yīng)的hash值，再計(jì)算其數(shù)組下標(biāo)；

如果沒有出現(xiàn)哈希沖突，則直接放入數(shù)組；如果出現(xiàn)哈希沖突，則以鏈表的方式放在鏈表后面；

如果鏈表長度超過閥值( TREEIFY THRESHOLD==8)，就把鏈表轉(zhuǎn)成紅黑樹，鏈表長度低于6，就把紅黑樹轉(zhuǎn)回鏈表;

如果結(jié)點(diǎn)的key已經(jīng)存在，則替換其value即可；

如果集合中的鍵值對(duì)大于12，調(diào)用resize方法進(jìn)行數(shù)組擴(kuò)容。”

8、數(shù)組擴(kuò)容的過程？

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

9、為什么不一直使用紅黑樹？

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

之所以選擇紅黑樹是為了解決二叉查找樹的缺陷，二叉查找樹在特殊情況下會(huì)變成一條線性結(jié)構(gòu)（這就跟原來使用鏈表結(jié)構(gòu)一樣了，造成很深的問題），遍歷查找會(huì)非常慢。

而紅黑樹在插入新數(shù)據(jù)后可能需要通過左旋，右旋、變色這些操作來保持平衡，引入紅黑樹就是為了查找數(shù)據(jù)快，解決鏈表查詢深度的問題，我們知道紅黑樹屬于平衡二叉樹，但是為了保持“平衡”是需要付出代價(jià)的，但是該代價(jià)所損耗的資源要比遍歷線性鏈表要少，所以當(dāng)長度大于8的時(shí)候，會(huì)使用紅黑樹，如果鏈表長度很短的話，根本不需要引入紅黑樹，引入反而會(huì)慢。

10、說說你對(duì)紅黑樹的見解？

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

11、jdk8中對(duì)HashMap做了哪些改變？

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

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

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

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

LinkedHashMap 保存了記錄的插入順序，在用 Iterator 遍歷時(shí)，先取到的記錄肯定是先插入的；遍歷比 HashMap 慢；

TreeMap 實(shí)現(xiàn) SortMap 接口，能夠把它保存的記錄根據(jù)鍵排序（默認(rèn)按鍵值升序排序，也可以指定排序的比較器）

13、HashMap & TreeMap & LinkedHashMap 使用場(chǎng)景？

一般情況下，使用最多的是 HashMap。

HashMap：在 Map 中插入、刪除和定位元素時(shí)；

TreeMap：在需要按自然順序或自定義順序遍歷鍵的情況下；

LinkedHashMap：在需要輸出的順序和輸入的順序相同的情況下。

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

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

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

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

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

HashMap 需要重新計(jì)算 hash 值，而 HashTable 直接使用對(duì)象的 hashCode

15、Java 中的另一個(gè)線程安全的與 HashMap 極其類似的類是什么？

同樣是線程安全，它與 HashTable 在線程同步上有什么不同？

ConcurrentHashMap 類（是 Java并發(fā)包 java.util.concurrent 中提供的一個(gè)線程安全且高效的 HashMap 實(shí)現(xiàn)）。

HashTable 是使用 synchronize 關(guān)鍵字加鎖的原理（就是對(duì)對(duì)象加鎖）；

而針對(duì) ConcurrentHashMap，在 JDK 1.7 中采用 分段鎖的方式；JDK 1.8 中直接采用了CAS（無鎖算法）+ synchronized。

16、HashMap & ConcurrentHashMap 的區(qū)別？

除了加鎖，原理上無太大區(qū)別。

HashMap的鍵值對(duì)允許有null，但是ConCurrentHashMap 都不允許。

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

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

ConcurrentHashMap

JDK 1.7 中使用分段鎖（ReentrantLock + Segment + HashEntry），相當(dāng)于把一個(gè) HashMap 分成多個(gè)段，每段分配一把鎖，這樣支持多線程訪問。鎖粒度：基于 Segment，包含多個(gè) HashEntry。

JDK 1.8 中使用 CAS + synchronized + Node + 紅黑樹。鎖粒度：Node（首結(jié)點(diǎn)）（實(shí)現(xiàn) Map.Entry）。鎖粒度降低了。

18、針對(duì) ConcurrentHashMap 鎖機(jī)制具體分析（JDK 1.7 VS JDK 1.8）？

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

• Segment 繼承 ReentrantLock（重入鎖） 用來充當(dāng)鎖的角色，每個(gè) Segment 對(duì)象守護(hù)每個(gè)散列映射表的若干個(gè)桶；
• HashEntry 用來封裝映射表的鍵-值對(duì)；
• 每個(gè)桶是由若干個(gè) HashEntry 對(duì)象鏈接起來的鏈表

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

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

粒度降低了；JVM 開發(fā)團(tuán)隊(duì)沒有放棄 synchronized，而且基于 JVM 的 synchronized 優(yōu)化空間更大，更加自然。在大量的數(shù)據(jù)操作下，對(duì)于 JVM 的內(nèi)存壓力，基于 API 的 ReentrantLock 會(huì)開銷更多的內(nèi)存。

• 粒度降低了；
• JVM 開發(fā)團(tuán)隊(duì)沒有放棄 synchronized，而且基于 JVM 的 synchronized 優(yōu)化空間更大，更加自然。
• 在大量的數(shù)據(jù)操作下，對(duì)于 JVM 的內(nèi)存壓力，基于 API 的 ReentrantLock 會(huì)開銷更多的內(nèi)存

20、ConcurrentHashMap 簡(jiǎn)單介紹？

重要的常量：

private transient volatile int sizeCtl;

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

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

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

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

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

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

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

存儲(chǔ)對(duì)象時(shí)（put() 方法）：

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

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

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

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

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

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

擴(kuò)容方法

transfer()：默認(rèn)容量為 16，擴(kuò)容時(shí)，容量變?yōu)樵瓉淼膬杀丁?/p>

helpTransfer()：調(diào)用多個(gè)工作線程一起幫助進(jìn)行擴(kuò)容，這樣的效率就會(huì)更高。

獲取對(duì)象時(shí)（get()方法）：

計(jì)算 hash 值，定位到該 table 索引位置，如果是首結(jié)點(diǎn)符合就返回；
如果遇到擴(kuò)容時(shí)，會(huì)調(diào)用標(biāo)記正在擴(kuò)容結(jié)點(diǎn) ForwardingNode.find()方法，查找該結(jié)點(diǎn)，匹配就返回；
以上都不符合的話，就往下遍歷結(jié)點(diǎn)，匹配就返回，否則最后就返回 null。

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

程序運(yùn)行時(shí)能夠同時(shí)更新 ConccurentHashMap 且不產(chǎn)生鎖競(jìng)爭(zhēng)的最大線程數(shù)。默認(rèn)為 16，且可以在構(gòu)造函數(shù)中設(shè)置。

當(dāng)用戶設(shè)置并發(fā)度時(shí)，ConcurrentHashMap 會(huì)使用大于等于該值的最小2冪指數(shù)作為實(shí)際并發(fā)度（假如用戶設(shè)置并發(fā)度為17，實(shí)際并發(fā)度則為32）

22、Hash沖突的幾種解決方法

22.1、開放地址法

使用開放地址法進(jìn)行建立散列表時(shí)，建表前須將表中所有單元中存儲(chǔ)的數(shù)據(jù)置空

22.1.1、線性探測(cè)法

如果當(dāng)前hash值發(fā)生沖突，就在此hash值的基礎(chǔ)上加一個(gè)單位，直到不發(fā)生hash沖突。
基本思想：假設(shè)散列表 T[0，m-1],從初始地址D開始探查，則最長的探查序列為：D，D+1，D+2，…，m-1,0,1,2,…,D-1

探查結(jié)束的三種情況：

• 當(dāng)前探查的單元為空，則代表查找失敗，如果是插入的話則將key值寫入
• 當(dāng)前探查的單元有key值，則代表插入失敗，但是查找成功。
• 若探查到T[D-1]時(shí)，未發(fā)現(xiàn)空單元，也未找到key值，則表示查找失敗并且插入失敗（此時(shí)表滿）

缺點(diǎn)：

• 需要另外的程序來處理溢出的情況，一般存儲(chǔ)在一個(gè)順序表中。
• 刪除數(shù)據(jù)時(shí)，不能直接置為空，而是需要添加一個(gè)被刪除的標(biāo)記。否則會(huì)對(duì)以后的查找產(chǎn)生印象（情況1）
• 容易產(chǎn)生堆聚現(xiàn)象

22.1.2、再平方探測(cè)

如果當(dāng)前hash值發(fā)生沖突，就在此hash值的基礎(chǔ)上加一個(gè)單位的平方，如果還是沖突，就在原來的hash值減去一個(gè)單位的平方。如果還是沖突就操作兩個(gè)單位的平方，三個(gè)單位的平方等。

22.1.3、偽隨機(jī)探測(cè)

如果當(dāng)前hash值發(fā)生沖突。就用隨機(jī)函數(shù)生成一個(gè)隨機(jī)值，加在原來的hash值上，直到不發(fā)生hash沖突。

22.2、拉鏈法

通過計(jì)算出來的hash值，如果發(fā)生沖突，則用鏈表或者紅黑樹進(jìn)行存儲(chǔ)

• 在進(jìn)行插入操作的時(shí)候，會(huì)先查找所插入的元素是否已經(jīng)存在，查找次數(shù)小于等于裝載因子的大?。ㄑb填因子a = m/n. m表示要裝填的關(guān)鍵字個(gè)數(shù) n為：裝載鏈表的數(shù)組的大小，一般情況下m>n）,所以時(shí)間復(fù)雜度為O（1）
• 在進(jìn)行查詢操作的時(shí)候，和上邊的類似，時(shí)間復(fù)雜度為O（1）
• 在進(jìn)行刪除操作的時(shí)候，由于鏈表的結(jié)構(gòu)，所以時(shí)間復(fù)雜度也是O（1）
• 在取出元素的時(shí)候，如果hash值相同，會(huì)在該鏈表中通過equals（）方法進(jìn)行比對(duì)

與開放地址法相比的優(yōu)點(diǎn)：

• 處理較為簡(jiǎn)單，且無堆積現(xiàn)象，查找時(shí)間較短
• 鏈表的長度是動(dòng)態(tài)的，適合數(shù)據(jù)規(guī)模不清楚的情況
• 開放地址法為例減少hash沖突，會(huì)使得裝載因子變小，及增大散列表的規(guī)模。這種方式在數(shù)據(jù)規(guī)模較大的時(shí)候會(huì)浪費(fèi)很多空間。而使用拉鏈法則可以使裝載因子>1,節(jié)省了空間開銷。
• 刪除節(jié)點(diǎn)的效率較高

缺點(diǎn)：

指針需要額外的空間，所以當(dāng)數(shù)據(jù)規(guī)模較小的時(shí)候，可以選擇開放地址法。將節(jié)省的指針控件可以用來增加散列表的規(guī)模，是的hash沖突減少

22.3、再哈希法

對(duì)于沖突的哈希值再次進(jìn)行通過哈希函數(shù)進(jìn)行運(yùn)算，直到?jīng)]有哈希沖突

22.4、建立公共溢出區(qū)

建立公共溢出區(qū)存儲(chǔ)所有哈希沖突的數(shù)據(jù)

結(jié)束

以上就是java哈希算法HashMap經(jīng)典面試題目匯總解析的詳細(xì)內(nèi)容，更多關(guān)于java哈希算法HashMap面試題的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論