HashMap7淺析

一、概述

  HashMap,基於哈希結構的Map接口的一個實現,無序,允許null鍵值對,線程不安全的。可以使用集合工具類Collections中的synchronizedMap方法,去創建一個線程安全的集合map。

  在jdk1.7中,HashMap主要是基於 數組+鏈表 的結構實現的。鏈表的存在主要是解決 hash 衝突而存在的。插入數據的時候,計算key的hash值,取得存儲的數組下標,如果衝突已有元素,則會在衝突地址上生成個鏈表,再通過key的比較,鏈表是否已存在,存在則覆蓋,不存在則鏈表上添加。這種方式,如果存在大量衝突的時候,會導致鏈表過長,那麼直接導致的就是犧牲了查詢和添加的效率。所以在jdk1.8版本之後,使用的就是 數組 + 鏈表 + 紅黑樹,當鏈表長度超過 8(實際加上初始的節點,整個有效長度是 9) 的時候,轉為紅黑樹存儲。

  本文中內容,主要基於jdk1.7版本,單線程環境下使用的HahsMap沒有啥問題,但是當在多線程下使用的時候,則可能會出現併發異常,具體表象是CPU會直線上升100%。下面是主要介紹相關的存取以及為什麼會出現線程安全性問題。

二、結構

  

  HashMap默認初始化size=16的哈希數組,然後通過計算待存儲的key的hash值,去計算得到哈希數組的下標值,然後放入鏈表中(新增節點或更新)。鏈表的存在即是解決hash衝突的。

三、源碼實現分析

  1、存儲具體數據的table數組:

      

    Entry為HashMap中的靜態內部類,其具體結構如下圖

      

    key、value屬性就是存儲鍵值對的,next則是指向鏈表的下一個元素節點。

     2、 默認初始化方法:

    

    默認構造方法,不對table進行初始化new(真正初始化動作放在put中,後面會看到),只是設置參數的默認值,hashmap長度和table長度初始化成DEFAULT_INITIAL_CAPACITY(16),加載因子loadFactor默認DEFAULT_LOAD_FACTOR(0.75f,至於為什麼是0.75,這個可以參見 )。

    加載因子:默認情況下,16*0.75=12,也就是在存儲第13個元素的時候,就會進行擴容(jdk1.7的threshold真正計算放在第一次初始化中,後面會再提及)。此元素的設置,直接影響到的是key的hash衝突問題。

  3、put方法

 public V put(K key, V value) {
   
if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value); int hash = hash(key); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; }

  3.1、EMPTY_TABLE是HashMap中的一個靜態的空的Entry數組,table也是HashMap的一個屬性,默認就是EMPTY_TABLE(這兩句可參見上面源碼),table就是我們真正數據存儲使用的。
  3.2、前面提及,無參構造的時候,並未真正完成對HashMap的初始化new操作,而僅僅只是設置幾個常量,所以在第一次put數據的時候,table是空的。則會進入下面的初始化table方法中。

if (table == EMPTY_TABLE) {
    inflateTable(threshold);
}

private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);

    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); //計算加載因子,默認情況下結果為12
    table = new Entry[capacity];  //真正的初始化table數組
    initHashSeedAsNeeded(capacity);
}

  3.3、key的null判斷

if (key == null)
    return putForNullKey(value);

private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

  具體步驟解析:

    1、key為null,取出table[0]的鏈表結構Enrty,如果取出的元素不為null,則對其進行循環遍歷,查找其中是否存在key為null的節點元素。

       2、如果存在key == null的節點,則使用新的value去更新節點的oldValue,並且將oldValue返回。

    3、如果不存在key == null的元素,則執行新增元素addEntry方法:

      (1)判斷是否需要擴容,size為當前數組table中,已存放的Entry鏈表個數,更直接點說,就是map.size()方法的返回值。threshold上面的真正初始化HashMap的時候已經提到,默認情況下,計算得到 threshold=12。若同時滿足  (size >= threshold) && (null != table[bucketIndex]) ,則對map進行2倍的擴容,然後對key進行重新計算hash值和新的數組下標。

      (2)創建新的節點原色createEntry方法,首先獲取table數組中下標為bucketIndex的鏈表的表頭元素,然後新建個Entry作為新的表頭,並且新表頭其中的next指向老的表頭數據。

  3.4、key不為null的存儲  
    原理以及過程上通key==null的大體相同,只不過,key==null的時候,固定是獲取table[0]的鏈表進行操作,而在不為key != null的時候,下標位置是通過
  int hash = hash(key); int i = indexFor(hash, table.length); 計算得到的

  static int indexFor(int h, int length) {
        // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

  很清晰的就能看明白,先計算key的hash,然後與當前table的長度進行相與,這樣計算得到待存放數據的下標。得到下標后,過程就與key==null一致了,遍歷是否存在,存在則更新並返回oldVlaue,不存在則新建Entry。

  4、get方法

 public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }
    如果key == null,則調用getForNullKey方法,遍歷table[0]處的鏈表。
private V getForNullKey() {
        if (size == 0) {
            return null;
        }
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

  如果key != null,則調用getEntry,根據key計算得到在table數組中的下標,獲取鏈表Entry,然後遍歷查找元素,key相等,則返回該節點元素。

 final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

四、線程不安全分析

  上述,主要淺析了下HashMap的存取過程,HashMap的線程安全性問題主要也就是在上述的擴容resize方法上,下面來看看在高併發下,擴容后,是如何引起100%問題的。

  1、在進行新元素 put 的時候,這在上面中的3.3的代碼片段中可以查看,addEntry 添加新節點的時候,會計算是否需要擴容處理:(size >= threshold) && (null != table[bucketIndex]) 。

  2、如果擴容的話,會接下來調用 resize 方法

 void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        //關鍵性代碼,構建新hashmap並將老的數據移動過來
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

  3、其中,出現100%問題的關鍵就是上面的 transfer 方法,新建hashmap移動複製老數據

 1  void transfer(Entry[] newTable, boolean rehash) {
 2         int newCapacity = newTable.length;
 3         for (Entry<K,V> e : table) {
 4             // 遍歷老的HashMap,當遇到不為空的節點的是,進入移動方法
 5             while(null != e) {
 6                 // 首先創建個Entry節點 指向該節點所在鏈表的下一個節點數據
 7                 Entry<K,V> next = e.next;
 8                 if (rehash) {
 9                     e.hash = null == e.key ? 0 : hash(e.key);
10                 }
11               // 計算老的數據在新Hashmap中的下標位置
12                 int i = indexFor(e.hash, newCapacity);
13              // 將新HashMap中相應位置的元素,掛載到老數據的後面(不管有無數據)
14                 e.next = newTable[i];
15                 // 將新HashMap中相應位置指向上面已經成功掛載新數據的老數據
16              newTable[i] = e;
17              // 移動到鏈表節點中的下一個數據,繼續複製節點
18                 e = next;
19             }
20         }
21     }    

  問題的關鍵就在上述的14、15行上,這兩行的動作,在高併發下可能就會造成循環鏈表,循環鏈表在等待下一個嘗試 get 獲取數據的時候,就悲劇了。下面舉例模擬說說這個過程:

  (1)假設目前某個位置的鏈表存儲結構為 A -> B -> C,有兩個線程同時進行擴容操作

  (2)線程1執行到第7行 Entry<K,V> next = e.next; 的時候被掛起了,此時,線程1的 e 指向 A , next 指向的是 B

  (3)線程2執行完成了整個的擴容過程,那麼此時的鏈表結構應該是變為了 C -> B -> A

  (4)線程1喚醒繼續執行,而需要操作的鏈表實際就變成了了上述線程2完成后的 C ->B -> A,下面分為幾步去完成整個操作:

      第一次循環:

        (i)執行 e.next = newTable[i] ,將 A 的 next 指向線程1的新的HashMap,由於此時無數據,所以 e.next = null

        (ii)執行 newTable[i] = e,將線程1的新的HashMap的第一個元素指向 A 

        (iii)執行e = next,移動到鏈表中的下一個元素,也就是上面的(2)中的 線程掛起的時候的 B

      第二次循環:

        (i)執行 Entry<K,V> next = e.next,此時的 e 指向 B,next指向 A

        (ii)執行 e.next = newTable[i] ,將 B 的 next 指向線程1的新的HashMap,由於此時有數據A,所以 e.next = A

        (iii)執行 newTable[i] = e,將線程1的新的HashMap的第一個元素指向 B,此時線程1的新Hashmap鏈表結構為B -> A

        (iiii)執行e = next,移動到鏈表中的下一個元素 A

      第三次循環:

        (i)執行 Entry<K,V> next = e.next,此時的 e 指向 A,next指向 null

        (ii)執行 e.next = newTable[i] ,將 A 的 next 指向線程1的新的HashMap,由於此時有數據B,所以 e.next = B

        (iii)執行 newTable[i] = e,將線程1的新的HashMap的第一個元素指向 A ,此時線程1的新Hashmap鏈表結構為 A -> B -> A

        (iiii)執行e = next,移動到鏈表中的下一個元素,已移動到鏈表結尾,結束 while 循環,完成鏈表的轉移。

  (5)上述過程中,很顯然的,最終的鏈表結構中,出現了 A -> B -> A 的循環結構。擴容完成了,剩下的等待的是get獲取的時候, getEntry 方法中 for循環e = e.next中就永遠出不來了。

  注意:擴容過程中,newTable是每個擴容線程獨有的,共享的只是每個Entry節點數據,最終的擴容是會調用 table = newTable 賦值操作完成。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

※帶您來了解什麼是 USB CONNECTOR  ?

※自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象

※如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站,提高曝光率!!

※綠能、環保無空污,成為電動車最新代名詞,目前市場使用率逐漸普及化

※廣告預算用在刀口上,網站設計公司幫您達到更多曝光效益