文章目錄

• • • • • 1.HashMap的底層數據結構？
        • 2.為啥需要鏈表，鏈表又是怎么樣子的呢？
        • 3.新的Entry節點在插入鏈表的時候，是怎么插入的么？
        • 4.Java7中的HashMap和Java8中的HashMap的區別？
        • 5.java8之后為啥改為尾部插入呢？
        • 6.為啥會線程不安全？
        • 7.有什么線程安全的類代替么?
        • 8.那你知道ConcurrentHashMap的分段鎖的實現原理嗎？
        • 9.默認初始化大小是多少？為啥是這么多？為啥大小都是2的冪？
        • 10.HashMap的擴容方式？負載因子是多少？為什是這么多？
        • 11.HashMap是怎么處理hash碰撞的？
        • 12.提到HashMap的初始化，那HashMap怎么設定初始容量大小的嗎？
        • 13.你了解HashMap在JDK8中的數據插入原理嗎？
        • 14.HashMap的哈希函數怎么設計的？
        • 15.為什么這么設計Hash函數？
        • 16.為什么采用hashcode的高16位和低16位異或能降低hash碰撞？hash函數能不能直接用key的hashcode？
        • 17.JDK8對hash函數做了優化，JDK8還有別的優化嗎？
        • 18.你分別跟我講講為什么要做這幾點優化？
        • 19.HashMap內部節點是有序的嗎？
        • 20.那有沒有有序的Map？
        • 21.跟我講講LinkedHashMap怎么實現有序的？

1.HashMap的底層數據結構？

HashMap是我們非常常用的數據結構，由數組和鏈表組合構成的數據結構。數組里面每個地方都存了Key-Value這樣的實例，在Java7叫Entry在Java8中叫Node。因為他本身所有的位置都為null，在put插入的時候會根據key的hash去計算一個index值。

Java 7 中的HashMap的底層是一個數組+鏈表的設計，每個hash值的第一個值放在數組里，之后經過hash運算得到相同的hash值鎖定數組下標，數組中的每一個元素都是一個單向鏈表（碰撞，列表）

2.為啥需要鏈表，鏈表又是怎么樣子的呢？

我們都知道數組長度是有限的，在有限的長度里面我們使用哈希，哈希本身是通過Hash函數計算出來的，結果就存在概率性，兩個不同的key，hash有一定的概率會一樣，那就形成了鏈表。每一個節點都會保存自身的hash、key、value、以及下個節點。

3.新的Entry節點在插入鏈表的時候，是怎么插入的么？

java8之前是頭插法，就是說新來的值會取代原有的值，原有的值就順推到鏈表中去，因為寫這個代碼的作者認為后來的值被查找的可能性更大一點，提升查找的效率。但是，在java8之后，都用尾部插入了

4.Java7中的HashMap和Java8中的HashMap的區別？

Java 7 中的HashMap的底層是一個數組+鏈表的設計，每個hash值的第一個值放在數組里，之后經過hash運算得到相同的hash值鎖定數組下標，數組中的每一個元素都是一個單向鏈表（碰撞，列表）

5.java8之后為啥改為尾部插入呢？

在插入時采用尾插法（1.7是頭插法），在并發場景下導致鏈表成環的問題。而在jdk1.8中采用尾插入法，在擴容時會保持鏈表元素原本的順序，就不會出現鏈表成環的問題了。


什么是頭插法和尾插法

頭插法帶來的環狀

6.為啥會線程不安全？

通過源碼看到put/get方法都沒有加同步鎖，多線程情況最容易出現的就是：無法保證上一秒put的值，下一秒get的時候還是原值，所以線程安全還是無法保證。

7.有什么線程安全的類代替么?

Java中有HashTable、Collections.synchronizedMap、以及ConcurrentHashMap可以實現線程安全的Map。

HashTable是直接在操作方法上加synchronized關鍵字，鎖住整個數組，粒度比較大。

Collections.synchronizedMap是使用 Collections集合工具的內部類，通過傳入Map封裝出一個SynchronizedMap對象，內部定義了一個對象鎖，方法內通過對象鎖實現。

ConcurrentHashMap使用分段鎖，降低了鎖粒度，讓并發度大大提高。

我們一般都會使用HashTable或者ConcurrentHashMap，但是因為前者的并發度的原因基本上沒啥使用場景了，所以存在線程不安全的場景我們都使用的是ConcurrentHashMap。

HashTable我看過他的源碼，很簡單粗暴，直接在方法上鎖，并發度很低，最多同時允許一個線程訪問，ConcurrentHashMap就好很多了，1.7和1.8有較大的不同，不過并發度都比前者好太多了。

8.那你知道ConcurrentHashMap的分段鎖的實現原理嗎？

ConcurrentHashMap成員變量使用volatile 修飾，免除了指令重排序，同時保證內存可見性，另外使用CAS操作和synchronized結合實現 賦值操作，多線程操作只會鎖住當前操作索引的節點。 如下圖，線程A鎖住A節點所在鏈表，線程B鎖住B節點所在鏈表，操作互不干涉。

9.默認初始化大小是多少？為啥是這么多？為啥大小都是2的冪？

是16，因為在使用不是2的冪的數字的時候，Length-1的值是所有二進制位全為1，這種情況下，index的結果等同于HashCode后幾位的值。 只要輸入的HashCode本身分布均勻，Hash算法的結果就是均勻的。 這是為了實現均勻分布。

10.HashMap的擴容方式？負載因子是多少？為什是這么多？

capacity：當前數組容量，始終保持 $2^n$，可以擴容，擴容后數組大小為當前的 2 倍。

loadFactor：負載因子，默認為 0.75。

threshold：擴容的閾值，等于 capacity * loadFactor。

Java 8 中的HashMap的底層是數組+鏈表+紅黑樹的方式實現。

改進的是在數據量較大的情況下（Java8 中，當鏈表中的元素超過了 8 個以后，會將鏈表轉換為紅黑樹）單向鏈表的時間復雜是O(N)，采用紅黑樹將時間復雜度降到O(logN)。

那么， 如果我們在刪除容器中的元素的時候，刪到多少才使得紅黑樹的存儲結構轉為鏈表呢？答案是6

也就是說，在JDK8之后，創建HashMap對象=>添加數組中同一個位置元素超過8個=>該位置鏈表轉為紅黑樹=>刪除數組中同一個位置元素少于6個=>該位置紅黑樹轉為列表。

最小樹形化容量閾值：即 當哈希表中的容量 > 該值時，才允許樹形化鏈表 （即 將鏈表 轉換成紅黑樹）， 否則，若桶內元素太多時，則直接擴容，而不是樹形化。為了避免進行擴容、樹形化選擇的沖突，這個值不能小于 4 * TREEIFY_THRESHOLD。

也就是說，當數組中某個桶中的元素大于8，小于64時，使用容量進行兩倍擴容（其實就是用擴容代替鏈表轉紅黑樹操作）。當數組中某個桶中的元素大于8且大于64時，鏈表轉紅黑樹操作。

hashMap并不是在鏈表元素個數大于8就一定會轉換為紅黑樹，而是先考慮擴容，擴容達到默認限制后才轉換

hashMap的紅黑樹不一定小于等于6的時候就會轉換為鏈表，而是只有在resize的時候才會根據 UNTREEIFY_THRESHOLD（6） 進行轉換

11.HashMap是怎么處理hash碰撞的？

Java中HashMap是利用“拉鏈法”處理HashCode的碰撞問題。

在調用HashMap的put方法或get方法時，都會首先調用hashcode方法，去查找相關的key，當有沖突時，再調用equals方法。hashMap基于hasing原理，我們通過put和get方法存取對象。

當我們將鍵值對傳遞給put方法時，他調用鍵對象的hashCode()方法來計算hashCode，然后找到bucket（哈希桶）位置來存儲對象。當獲取對象時，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象。

HashMap使用鏈表來解決碰撞問題，當碰撞發生了，對象將會存儲在鏈表的下一個節點中。hashMap在每個鏈表節點存儲鍵值對對象。當兩個不同的鍵卻有相同的hashCode時，他們會存儲在同一個bucket位置的鏈表中。

鍵對象的equals()來找到鍵值對。

12.提到HashMap的初始化，那HashMap怎么設定初始容量大小的嗎？

一般如果new HashMap() 不傳值，默認大小是16，負載因子是0.75， 如果自己傳入初始大小k，初始化大小為大于k的2的整數次方，例如如果傳10，大小為16

13.你了解HashMap在JDK8中的數據插入原理嗎？

14.HashMap的哈希函數怎么設計的？

hash函數是先拿到通過key 的hashcode，是32位的int值，然后讓hashcode的高16位和低16位進行異或操作。

15.為什么這么設計Hash函數？

這個也叫擾動函數，這么設計有二點原因：

一定要盡可能降低hash碰撞，越分散越好；

算法一定要盡可能高效，因為這是高頻操作, 因此采用位運算；

16.為什么采用hashcode的高16位和低16位異或能降低hash碰撞？hash函數能不能直接用key的hashcode？

因為key.hashCode()函數調用的是key鍵值類型自帶的哈希函數，返回int型散列值。

int值范圍為-2147483648~2147483647， 前后加起來大概40億的映射空間。

只要哈希函數映射得比較均勻松散，一般應用是很難出現碰撞的。

但問題是一個40億長度的數組，內存是放不下的。

因為如果HashMap數組的初始大小才16，用之前需要對數組的長度取模運算，得到的余數才能用來訪問數組下標。

源碼中模運算就是把散列值和數組長度-1做一個"與"操作，位運算比%運算要快。

bucketIndex = indexFor(hash, table.length);static int indexFor(int h, int length) {return h & (length-1); }

便說一下，這也正好解釋了為什么HashMap的數組長度要取2的整數冪。因為這樣（數組長度-1）正好相當于一個“低位掩碼”。“與”操作的結果就是散列值的高位全部歸零，只保留低位值，用來做數組下標訪問。以初始長度16為例，16-1=15。2進制表示是00000000 00000000 00001111。和某散列值做“與”操作如下，結果就是截取了最低的四位值。


HashMap與運算



HashMap碰撞

17.JDK8對hash函數做了優化，JDK8還有別的優化嗎？

1. 數組+鏈表改成了數組+鏈表或紅黑樹；
2. 鏈表的插入方式從頭插法改成了尾插法，簡單說就是插入時，如果數組位置上已經有元素，1.7將新元素放到數組中，原始節點作為新節點的 后繼節點，1.8遍歷鏈表，將元素放置到鏈表的最后；
3. 擴容的時候1.7需要對原數組中的元素進行重新hash定位在新數組的位置，1.8采用更簡單的判斷邏輯，位置不變或索引+舊容量大小;
4. 在插入時，1.7先判斷是否需要擴容，再插入，1.8先進行插入，插入完成再判斷是否需要擴容；

18.你分別跟我講講為什么要做這幾點優化？

防止發生hash沖突，鏈表長度過長，將時間復雜度由O(n)降為O(logn);

因為1.7頭插法擴容時，頭插法會使鏈表發生反轉，多線程環境下會產生環；

A線程在插入節點B，B線程也在插入，遇到容量不夠開始擴容，重新hash，放置元素，采用頭插法，后遍歷到的B節點放入了頭部，這樣形成了環，如上圖所示

擴容的時候為什么1.8 不用重新hash就可以直接定位原節點在新數據的位置呢?

這是由于擴容是擴大為原數組大小的2倍，用于計算數組位置的掩碼僅僅只是高位多了一個1，怎么理解呢？

擴容前長度為16，用于計算(n-1) & hash 的二進制n-1為0000 1111，擴容為32后的二進制就高位多了1，為0001 1111。

因為是& 運算，1和任何數 & 都是它本身，那就分二種情況，如下圖：原數據hashcode高位第4位為0和高位為1的情況；第四位高位為0，重新hash數值不變，第四位為1，重新hash數值比原來大16（舊數組的容量）
HashMap中的與運算

19.HashMap內部節點是有序的嗎？

是無序的，根據hash值隨機插入

20.那有沒有有序的Map？

LinkedHashMap 和 TreeMap

21.跟我講講LinkedHashMap怎么實現有序的？

LinkedHashMap內部維護了一個單鏈表，有頭尾節點，同時LinkedHashMap節點Entry內部除了繼承HashMap的Node屬性，還有before 和after用于標識前置節點和后置節點。可以實現按插入的順序或訪問順序排序。

總結

以上是生活随笔為你收集整理的【Java自顶向下】HashMap面试题（2021最新版）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。