建站
咨詢
售后
建站咨詢
新聞中心
[[415781]] 本文轉(zhuǎn)載自微信公眾號(hào)「Java時(shí)間屋」，作者Jack佳。轉(zhuǎn)載本文請(qǐng)聯(lián)系Java時(shí)間屋公眾號(hào)。
創(chuàng)新互聯(lián)一直秉承“誠信做人，踏實(shí)做事”的原則，不欺瞞客戶，是我們最起碼的底線！ 以服務(wù)為基礎(chǔ)，以質(zhì)量求生存，以技術(shù)求發(fā)展，成交一個(gè)客戶多一個(gè)朋友！為您提供成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)頁設(shè)計(jì)、微信平臺(tái)小程序開發(fā)、成都網(wǎng)站開發(fā)、成都網(wǎng)站制作、成都軟件開發(fā)、重慶App定制開發(fā)是成都本地專業(yè)的網(wǎng)站建設(shè)和網(wǎng)站設(shè)計(jì)公司，等你一起來見證！
- 1.HashMap的數(shù)據(jù)結(jié)構(gòu):
- 2.HashMap的hash函數(shù)設(shè)計(jì):
- 3.Java1.8的Java1.7對(duì)比:
- 3.1 擾動(dòng)的次數(shù)減少:
- 3.2 結(jié)構(gòu)變化:
- 3.3 插入變化:
- 3.4 擴(kuò)容的變化:
- 3.5 擴(kuò)容的時(shí)間變化:
- 4.HashTable和Collections.synchronizedMap、以及ConcurrentHashMap可以實(shí)現(xiàn)線程安全的Map原理:
- 5.Map集合的順序：
前言
HashMap是java面試的時(shí)候最常問的問題，其中牽扯的知識(shí)點(diǎn)很多，很適合考察面試的基礎(chǔ)，我反正面試很多家這個(gè)問題確實(shí)是必問，不準(zhǔn)備一番還真不好回答好。
1.HashMap的數(shù)據(jù)結(jié)構(gòu):
JDK1.8:數(shù)組+鏈表/紅黑樹 數(shù)據(jù)結(jié)構(gòu)原理：鏈表長度>8&數(shù)組大小>=64=》轉(zhuǎn)為紅黑樹存儲(chǔ);紅黑樹節(jié)點(diǎn)個(gè)數(shù)<6轉(zhuǎn)為鏈表。tips：為什么不是小于8是為了防止頻繁的結(jié)構(gòu)轉(zhuǎn)換增加開銷。那為啥是8呢?發(fā)生hash碰撞的幾率8次的概率為百萬分之6，夠了。HashMap的數(shù)據(jù)插入原理：
重點(diǎn)說明：上面計(jì)算數(shù)組位置的方法是：通過 (n - 1) & hash計(jì)算應(yīng)當(dāng)存放在數(shù)組中的下標(biāo) index ;叫做位運(yùn)算為啥(n-1)更接近于取模，為啥采用位運(yùn)算是因?yàn)樾矢?，不存在二進(jìn)制和十進(jìn)制的轉(zhuǎn)換。這里在補(bǔ)充一點(diǎn)HashMap初始化數(shù)組大小的問題，HashMap數(shù)組初始化大小為16，為啥呢?理論上來說2的整數(shù)次冪都可以，但是如果是2,4或者8就會(huì)有點(diǎn)小，添加不了多少數(shù)據(jù)就會(huì)擴(kuò)容，影響性能，如果是32或者更大，就會(huì)浪費(fèi)空間。所以16是一個(gè)經(jīng)驗(yàn)值保留下來的。
2.HashMap的hash函數(shù)設(shè)計(jì):
在HashMap中，首先是通過key的hashcode(32位的int值)然后讓hashcode的高16位和低16位進(jìn)行異或操作。為啥這樣設(shè)計(jì)：1.上面的hash函數(shù)也叫擾動(dòng)函數(shù)，主要考慮盡可能降低hash碰撞，越分散越好。
2.算法一定要盡可能的高效，因?yàn)檫@是高頻操作，因此采用位運(yùn)算。
3.因?yàn)閔ashcode的范圍是int類型，大概40億的映射空間,如果只是hashcode，很少會(huì)出現(xiàn)碰撞，但是數(shù)組和內(nèi)存是發(fā)放不下的，初始大小才16的數(shù)組只能進(jìn)行取模運(yùn)算/位運(yùn)算來達(dá)到目的。
HashMap的數(shù)組長度要取2的整數(shù)冪，這樣數(shù)組長度-1剛好"低位掩碼",加上hash函數(shù)(擾動(dòng)函數(shù))降低碰撞。
3.Java1.8的Java1.7對(duì)比:
3.1 擾動(dòng)的次數(shù)減少:
java1.8跟java1.7在這里的區(qū)別就hash函數(shù)里面是java8只擾動(dòng)了一次，為了效率。java7在這里擾動(dòng)了四次。
3.2 結(jié)構(gòu)變化:
1.7里面的數(shù)組+鏈表===》數(shù)組+鏈表或紅黑樹。為什么這樣做，前者的查詢效率是n后者的查詢效率是log2(n),所有當(dāng)鏈表數(shù)據(jù)量大的時(shí)候會(huì)有效率問題。
3.3 插入變化:
鏈表的插入方式從頭插法改成了尾插法，簡單來說就是1.7中是往前面插入，1.8中是往后插入，這樣做的目的是為了防止擴(kuò)容的時(shí)候死循環(huán)。
3.4 擴(kuò)容的變化:
擴(kuò)容的時(shí)候1.7是重新hash定位新數(shù)組的位置，1.8則是采用更簡單的邏輯判斷，位置不變或索引+舊容量大小。為什么1.8能這樣，計(jì)算數(shù)組的位置的掩碼僅僅只是高位多了一個(gè)1。
3.5 擴(kuò)容的時(shí)間變化:
在插入時(shí)，1.7先判斷是否需要擴(kuò)容再插入，1.8是插入以后再判斷是不是需要擴(kuò)容
4.HashTable和Collections.synchronizedMap、以及ConcurrentHashMap可以實(shí)現(xiàn)線程安全的Map原理:
我們都知道的是HashMap是線程不安全的，1.7版本的時(shí)候會(huì)產(chǎn)生死循環(huán)、數(shù)據(jù)丟失、數(shù)據(jù)覆蓋的問題，1.8中解決了其中的兩個(gè)問題，仍然會(huì)有數(shù)據(jù)覆蓋的問題，就是多線程并發(fā)操作下的值覆蓋。如果業(yè)務(wù)場景中需要線程安全，就要使用線程安全的Map類，一般我們使用的是ConcurrentHashMap。
ConcurrentHashMap：使用的分段鎖，降低鎖粒度，提高并發(fā)度和效率。1.8相對(duì)1.7也是提升了效率，成員變量之間使用了volatile修飾，避免了指令重排，保持內(nèi)存可見。采用的CAS和synchronized結(jié)合實(shí)現(xiàn)賦值操作，只會(huì)鎖住當(dāng)前操作索引節(jié)點(diǎn)。
HashTable：直接在操作方法上synchronized關(guān)鍵字，鎖住整個(gè)數(shù)組，效率會(huì)很低。SynchronizedMap：內(nèi)部實(shí)現(xiàn)的對(duì)象鎖實(shí)現(xiàn)。效率比HashTable會(huì)高點(diǎn)。
5.Map集合的順序：
HashMap里面是無序的，所以只能循環(huán)遍歷。LinkedHashMap：有序map，內(nèi)部維護(hù)了一個(gè)單鏈表。單鏈表的before和after使其具有了有序的特性。TreeMap:內(nèi)部通過Comprator比較器實(shí)現(xiàn)了排序。
總結(jié)
我上面的論述也是參考的網(wǎng)上我認(rèn)為不錯(cuò)的針對(duì)HashMap的講解，然后加入了我自己的理解，讓大家能夠更好的理解其中的原理內(nèi)容，如果你有其他問題，歡迎關(guān)注我的公眾號(hào):Java時(shí)間屋 進(jìn)行討論。
文章標(biāo)題：HashMap面試怎么面？
文章源于：http://www.5511xx.com/article/dpodgsg.html
