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

前言

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

1.HashMap的數據結構:

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

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

2.HashMap的hash函數設計:

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

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

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

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

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

3.1 擾動的次數減少:

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

3.2 結構變化:

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

3.3 插入變化:

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

3.4 擴容的變化:

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

3.5 擴容的時間變化:

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

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

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

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

HashTable：直接在操作方法上synchronized關鍵字，鎖住整個數組，效率會很低。SynchronizedMap：內部實現的對象鎖實現。效率比HashTable會高點。

5.Map集合的順序：

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

總結

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