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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

那么為什么要進行這樣的計算呢？

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

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

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

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

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

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

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

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

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

四、HashMap如何進行擴容

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

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

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

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

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

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

最新評論