建站
咨詢
售后
建站咨詢
新聞中心
[[415781]] 本文轉(zhuǎn)載自微信公眾號「Java時間屋」，作者Jack佳。轉(zhuǎn)載本文請聯(lián)系Java時間屋公眾號。
創(chuàng)新互聯(lián)一直秉承“誠信做人，踏實做事”的原則，不欺瞞客戶，是我們最起碼的底線！ 以服務(wù)為基礎(chǔ)，以質(zhì)量求生存，以技術(shù)求發(fā)展，成交一個客戶多一個朋友！為您提供成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計、成都網(wǎng)頁設(shè)計、微信平臺小程序開發(fā)、成都網(wǎng)站開發(fā)、成都網(wǎng)站制作、成都軟件開發(fā)、重慶App定制開發(fā)是成都本地專業(yè)的網(wǎng)站建設(shè)和網(wǎng)站設(shè)計公司，等你一起來見證！
- 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)更接近于取模，為啥采用位運算是因為效率高，不存在二進制和十進制的轉(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位進行異或操作。為啥這樣設(shè)計：1.上面的hash函數(shù)也叫擾動函數(shù)，主要考慮盡可能降低hash碰撞，越分散越好。
2.算法一定要盡可能的高效，因為這是高頻操作，因此采用位運算。
3.因為hashcode的范圍是int類型，大概40億的映射空間,如果只是hashcode，很少會出現(xiàn)碰撞，但是數(shù)組和內(nèi)存是發(fā)放不下的，初始大小才16的數(shù)組只能進行取模運算/位運算來達到目的。
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)上我認為不錯的針對HashMap的講解，然后加入了我自己的理解，讓大家能夠更好的理解其中的原理內(nèi)容，如果你有其他問題，歡迎關(guān)注我的公眾號:Java時間屋 進行討論。
網(wǎng)站標(biāo)題：HashMap面試怎么面？
標(biāo)題網(wǎng)址：http://www.dlmjj.cn/article/dpodgsg.html
