• 1.HashMap的數(shù)據(jù)結(jié)構(gòu):
• 2.HashMap的hash函數(shù)設(shè)計:
• 3.Java1.8的Java1.7對比:
  • 3.1 擾動的次數(shù)減少:
  • 3.2 結(jié)構(gòu)變化:
  • 3.3 插入變化:
  • 3.4 擴容的變化:
  • 3.5 擴容的時間變化:
• 4.HashTable和Collections.synchronizedMap、以及ConcurrentHashMap可以實現(xiàn)線程安全的Map原理:
• 5.Map集合的順序：

前言

HashMap是java面試的時候最常問的問題，其中牽扯的知識點很多，很適合考察面試的基礎(chǔ)，我反正面試很多家這個問題確實是必問，不準(zhǔn)備一番還真不好回答好。

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

JDK1.8:數(shù)組+鏈表/紅黑樹 數(shù)據(jù)結(jié)構(gòu)原理：鏈表長度>8&數(shù)組大小>=64=》轉(zhuǎn)為紅黑樹存儲;紅黑樹節(jié)點個數(shù)<6轉(zhuǎn)為鏈表。tips：為什么不是小于8是為了防止頻繁的結(jié)構(gòu)轉(zhuǎn)換增加開銷。那為啥是8呢?發(fā)生hash碰撞的幾率8次的概率為百萬分之6，夠了。HashMap的數(shù)據(jù)插入原理：

重點說明：上面計算數(shù)組位置的方法是：通過 (n - 1) & hash計算應(yīng)當(dāng)存放在數(shù)組中的下標(biāo) index ;叫做位運算為啥(n-1)更接近于取模，為啥采用位運算是因為效率高，不存在二進(jìn)制和十進(jìn)制的轉(zhuǎn)換。這里在補充一點HashMap初始化數(shù)組大小的問題，HashMap數(shù)組初始化大小為16，為啥呢?理論上來說2的整數(shù)次冪都可以，但是如果是2,4或者8就會有點小，添加不了多少數(shù)據(jù)就會擴容，影響性能，如果是32或者更大，就會浪費空間。所以16是一個經(jīng)驗值保留下來的。

2.HashMap的hash函數(shù)設(shè)計:

在HashMap中，首先是通過key的hashcode(32位的int值)然后讓hashcode的高16位和低16位進(jìn)行異或操作。為啥這樣設(shè)計：1.上面的hash函數(shù)也叫擾動函數(shù)，主要考慮盡可能降低hash碰撞，越分散越好。

2.算法一定要盡可能的高效，因為這是高頻操作，因此采用位運算。

3.因為hashcode的范圍是int類型，大概40億的映射空間,如果只是hashcode，很少會出現(xiàn)碰撞，但是數(shù)組和內(nèi)存是發(fā)放不下的，初始大小才16的數(shù)組只能進(jìn)行取模運算/位運算來達(dá)到目的。

HashMap的數(shù)組長度要取2的整數(shù)冪，這樣數(shù)組長度-1剛好"低位掩碼",加上hash函數(shù)(擾動函數(shù))降低碰撞。

3.Java1.8的Java1.7對比:

3.1 擾動的次數(shù)減少:

java1.8跟java1.7在這里的區(qū)別就hash函數(shù)里面是java8只擾動了一次，為了效率。java7在這里擾動了四次。

3.2 結(jié)構(gòu)變化:

1.7里面的數(shù)組+鏈表===》數(shù)組+鏈表或紅黑樹。為什么這樣做，前者的查詢效率是n后者的查詢效率是log2(n),所有當(dāng)鏈表數(shù)據(jù)量大的時候會有效率問題。

3.3 插入變化:

鏈表的插入方式從頭插法改成了尾插法，簡單來說就是1.7中是往前面插入，1.8中是往后插入，這樣做的目的是為了防止擴容的時候死循環(huán)。

3.4 擴容的變化:

擴容的時候1.7是重新hash定位新數(shù)組的位置，1.8則是采用更簡單的邏輯判斷，位置不變或索引+舊容量大小。為什么1.8能這樣，計算數(shù)組的位置的掩碼僅僅只是高位多了一個1。

3.5 擴容的時間變化:

在插入時，1.7先判斷是否需要擴容再插入，1.8是插入以后再判斷是不是需要擴容

4.HashTable和Collections.synchronizedMap、以及ConcurrentHashMap可以實現(xiàn)線程安全的Map原理:

我們都知道的是HashMap是線程不安全的，1.7版本的時候會產(chǎn)生死循環(huán)、數(shù)據(jù)丟失、數(shù)據(jù)覆蓋的問題，1.8中解決了其中的兩個問題，仍然會有數(shù)據(jù)覆蓋的問題，就是多線程并發(fā)操作下的值覆蓋。如果業(yè)務(wù)場景中需要線程安全，就要使用線程安全的Map類，一般我們使用的是ConcurrentHashMap。

ConcurrentHashMap：使用的分段鎖，降低鎖粒度，提高并發(fā)度和效率。1.8相對1.7也是提升了效率，成員變量之間使用了volatile修飾，避免了指令重排，保持內(nèi)存可見。采用的CAS和synchronized結(jié)合實現(xiàn)賦值操作，只會鎖住當(dāng)前操作索引節(jié)點。

HashTable：直接在操作方法上synchronized關(guān)鍵字，鎖住整個數(shù)組，效率會很低。SynchronizedMap：內(nèi)部實現(xiàn)的對象鎖實現(xiàn)。效率比HashTable會高點。

5.Map集合的順序：

HashMap里面是無序的，所以只能循環(huán)遍歷。LinkedHashMap：有序map，內(nèi)部維護了一個單鏈表。單鏈表的before和after使其具有了有序的特性。TreeMap:內(nèi)部通過Comprator比較器實現(xiàn)了排序。

總結(jié)

我上面的論述也是參考的網(wǎng)上我認(rèn)為不錯的針對HashMap的講解，然后加入了我自己的理解，讓大家能夠更好的理解其中的原理內(nèi)容，如果你有其他問題，歡迎關(guān)注我的公眾號:Java時間屋 進(jìn)行討論。