一、HashMap的底層數(shù)據(jù)結(jié)構(gòu)

HashMap作為開發(fā)中常用的數(shù)據(jù)結(jié)構(gòu)，也是面試中經(jīng)常被問的知識(shí)點(diǎn)，因此作為開發(fā)者應(yīng)該盡可能多的理解其底層的數(shù)據(jù)結(jié)構(gòu)。

創(chuàng)建一個(gè)HashMap很簡(jiǎn)單，假設(shè)創(chuàng)建一個(gè)人員畢業(yè)院校的HashMap

Map<String, String> map = new HashMap<>();
map.put(”張三”: “南京大學(xué)”);
map.put(“李四”, “西北工業(yè)大學(xué)”);

你可能以為數(shù)據(jù)是這樣存儲(chǔ)的：

{
        “張三”:  “南京大學(xué)”,
        “李四”: ”西北工業(yè)大學(xué)”
}

但其實(shí)它的底層是數(shù)組，是這樣存儲(chǔ)的：

[<”張三”, “南京大學(xué)”>, <”李四”,”西北工業(yè)大學(xué)”>]

但元素并不是順序放入數(shù)組的，它的計(jì)算方式是：對(duì)key值計(jì)算出一個(gè)hash值，然后用這個(gè)hash值對(duì)數(shù)組長(zhǎng)度取模，根據(jù)取模計(jì)算結(jié)果定位到數(shù)組的位置。

假設(shè)數(shù)組長(zhǎng)度是16，對(duì)”張三”的hash取模計(jì)算結(jié)果是4，那么它就放在數(shù)組的第5個(gè)位置上。實(shí)際的存儲(chǔ)大約是這樣：

[<>, <>, <>, <>, <”張三”, “南京大學(xué)”>, <>, <>, <”李四”,”西北工業(yè)大學(xué)”>, <>, <>, <>, <>, <>, <>, <>, <>]

取出元素的計(jì)算過程類似，比如map.get(“張三”)，先對(duì)”張三”計(jì)算出一個(gè)hash值，然后用這個(gè)hash值對(duì)數(shù)組長(zhǎng)度取模，根據(jù)模計(jì)算結(jié)果定位到數(shù)組中的位置，將該位置的元素取出。

二、JDK1.8對(duì)HashMap算法的優(yōu)化

1、對(duì)尋址算法的優(yōu)化

由hash值對(duì)數(shù)組長(zhǎng)度n取模運(yùn)算，改為hash值與數(shù)組長(zhǎng)度n減1進(jìn)行與運(yùn)算，即hash&(n-1)。這兩者在數(shù)學(xué)上，計(jì)算結(jié)果是等價(jià)的，但從計(jì)算機(jī)角度來說，后者的運(yùn)算性能要比前者高很多。

2、對(duì)hash算法的優(yōu)化

不是直接用hashcode值進(jìn)行運(yùn)算，而是使用了新的算法，以下是jdk1.8的一段源碼：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode() ^ (h >>> 16));
}

hashCode()的返回值是一個(gè)32位整數(shù)，這個(gè)算法的意思就是用hashCode()值右移16位后的值與hashCode()原值進(jìn)行異或運(yùn)算。由于右移16位后左側(cè)補(bǔ)0，而與0異或的結(jié)果是原值，所以hashCode()的高16位不變，因此此運(yùn)算相當(dāng)于hashCode()將的高16位與低16位進(jìn)行異或運(yùn)算。

例如：假設(shè)有如下一個(gè)key值

假設(shè)數(shù)組長(zhǎng)度是16，它的計(jì)算過程如下：

那么為什么要進(jìn)行這樣的計(jì)算呢？

這是因?yàn)?，?shù)組長(zhǎng)度一般比較小，因此，它的高16位一般都是0。0與任何數(shù)進(jìn)行與運(yùn)算，結(jié)果都是0，因此key值的高16位相當(dāng)于沒起作用，因?yàn)榻Y(jié)果都一樣，實(shí)際上就只看低16位的計(jì)算結(jié)果，這樣就增加了計(jì)算結(jié)果重復(fù)的概率。從而增加了hash沖突。改與以上優(yōu)化算法，讓高16位也參與了進(jìn)來，就能一定程度上減少這種沖突。

三、HashMap如何解決hash碰撞問題

無(wú)論hash算法如何優(yōu)化，對(duì)不同的key算出來的hash值是有可能相同的，這種情況叫hash碰撞或者h(yuǎn)ash沖突。

兩個(gè)不同的元素不可能放到數(shù)組的同一個(gè)位置。HashMap的解決方法是，在這個(gè)位置放一個(gè)鏈表，鏈表里可以存多個(gè)元素，將相同hash值的元素都存放到這個(gè)鏈表中。當(dāng)通過get方法讀取數(shù)據(jù)時(shí)，當(dāng)定位到這個(gè)位置發(fā)現(xiàn)是個(gè)鏈表，就對(duì)這個(gè)鏈表進(jìn)行遍歷查詢，找到需要的元素。

鏈表遍歷查詢的時(shí)間復(fù)雜度是O(N)，當(dāng)鏈表比較長(zhǎng)時(shí)，也就是hash沖突比較多時(shí)，性能比較差。因此HashMap對(duì)此做了優(yōu)化，當(dāng)達(dá)到一定條件時(shí)，就會(huì)將鏈表轉(zhuǎn)為紅黑樹。紅黑樹遍歷查詢的時(shí)間復(fù)雜度是O(logN)，性能有很大提升。

在JDK1.8之后，HashMap中的鏈表在同時(shí)滿足以下兩個(gè)條件時(shí)，將會(huì)轉(zhuǎn)化為紅黑樹(即自平衡的排序二叉樹)：

1. 條件一：數(shù)組 arr[i] 處存放的鏈表長(zhǎng)度大于8；

2. 條件二：數(shù)組長(zhǎng)度大于64。

滿足以上兩個(gè)條件，數(shù)組 arr[i] 處的鏈表將自動(dòng)轉(zhuǎn)化為紅黑樹，其他位置如 arr[i+1] 處的數(shù)組元素仍為鏈表，不受影響。

四、HashMap如何進(jìn)行擴(kuò)容

HashMap底層是數(shù)組，當(dāng)數(shù)組滿了之后，它就會(huì)自動(dòng)進(jìn)行擴(kuò)容，變成一個(gè)更大的數(shù)組，擴(kuò)容方式就是2倍擴(kuò)容，數(shù)量直接翻倍。由于數(shù)組長(zhǎng)度變了，而數(shù)組長(zhǎng)度是參與hash運(yùn)算的，因此擴(kuò)容后需要重新進(jìn)行hash運(yùn)算，這就可能會(huì)產(chǎn)生內(nèi)容的變化。比如原來有hash沖突需要產(chǎn)生鏈表，但re-hash運(yùn)算后沒有沖突了，不需要鏈表了?；蛘吣硞€(gè)位置的鏈表里有三個(gè)元素，進(jìn)行re-hash運(yùn)算后，可能變成了兩個(gè)。

五、ConcurrentHashMap實(shí)現(xiàn)線程安全的底層原理

ConcurrentHashMap是線程安全的HashMap，兩者都繼承自AbstractMap。在需要線程安全的場(chǎng)合操作HashMap需要使用synchronized關(guān)鍵字加鎖，性能很低。而ConcurrentHashMap本身就是線程安全，無(wú)需再加synchronized關(guān)鍵字，且已經(jīng)做了優(yōu)化，可以直接使用。

ConcurrentHashMap的數(shù)據(jù)結(jié)構(gòu)與HashMap基本相同，底層都是數(shù)組。JDK1.7以前采用的是分段加鎖，底層不是一個(gè)數(shù)組，而是分成多個(gè)數(shù)組。寫數(shù)據(jù)時(shí)內(nèi)部還是加鎖的，但是只對(duì)所在段的數(shù)組加鎖，不同段的操作互不影響，所以·可以并行操作，提高了性能。

JDK1.8以后進(jìn)一步優(yōu)化和改進(jìn)，和HashMap一樣使用一個(gè)大數(shù)組的形式。但對(duì)某個(gè)元素進(jìn)行put操作時(shí)，使用的是CAS操作，這樣如果有多個(gè)線程操作這個(gè)位置的元素，同一時(shí)刻只有一個(gè)會(huì)成功。因此大多數(shù)情況下都是無(wú)鎖操作，性能很高。只有對(duì)于有hash沖突而采用鏈表+紅黑樹進(jìn)行處理的位置進(jìn)行操作時(shí)，ConcurrentHashMap內(nèi)部才需要對(duì)這個(gè)位置進(jìn)行synchronized加鎖處理。

到此這篇關(guān)于HashMap底層數(shù)據(jù)結(jié)構(gòu)詳細(xì)解析的文章就介紹到這了,更多相關(guān)HashMap數(shù)據(jù)結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論