一、HashMap的底層數(shù)據結構

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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位后左側補0，而與0異或的結果是原值，所以hashCode()的高16位不變，因此此運算相當于hashCode()將的高16位與低16位進行異或運算。

例如：假設有如下一個key值

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

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

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

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

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

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

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

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

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

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

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

四、HashMap如何進行擴容

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

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

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

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

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

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

最新評論