天天看點

hashmap底層原理_Java集合架構(四)搞定HashMap底層原理一、結構二、方法三、高并發下的HashMap四、優化

一、結構

hashmap底層原理_Java集合架構(四)搞定HashMap底層原理一、結構二、方法三、高并發下的HashMap四、優化

如圖所示,HashMap 底層是基于數組和連結清單實作的。其中有兩個重要的參數:

  • 容量
  • 負載因子

容量的預設大小是 16,負載因子是 0.75,當 HashMap 的 size > 16*0.75 時就會發生擴容(容量和負載因子都可以自由調整,無論是自動擴充還是手動初始化時,必須是2的幂)。

二、方法

2.1、put 方法

首先會将傳入的 Key 做 hash 運算計算出 hashcode,然後根據數組長度取模計算出在數組中的 index 下标。

由于在計算中位運算比取模運算效率高的多且Hash算法均勻分布原則,是以 HashMap 規定數組的長度為 2^n 。這樣用 2^n - 1 做位運算與取模效果一緻,并且效率還要高出許多index = HashCode(Key) & (Length - 1)。

下面我們以值為“book”的Key來示範整個過程:

1.計算book的hashcode,結果為十進制的3029737,二進制的101110001110101110 1001。

2.假定HashMap長度是預設的16,計算Length-1的結果為十進制的15,二進制的1111。

3.把以上兩個結果做與運算,101110001110101110 1001 & 1111 = 1001,十進制是9,是以 index=9。

可以說,Hash算法最終得到的index結果,完全取決于Key的Hashcode值的最後幾位。

由于數組的長度有限,是以難免會出現不同的 Key 通過運算得到的 index 相同,這種情況可以利用連結清單來解決,HashMap 會在 table[index]處形成環形連結清單,采用頭插法(不是插傳入連結表的尾部,而是頭部,因為:後插入的Entry被查找的可能性更大)将資料插入到連結清單中。

2.2、get 方法

get 和 put 類似,也是将傳入的 Key 計算出 index ,如果該位置上是一個連結清單就需要周遊整個連結清單,通過 key.equals(k) 來找到對應的元素。

周遊方式

Iterator> entryIterator = map.entrySet().iterator();  while (entryIterator.hasNext()) {   Map.Entry next = entryIterator.next();   System.out.println("key=" + next.getKey() + " value=" + next.getValue());}
           
Iterator iterator = map.keySet().iterator(); while (iterator.hasNext()){   String key = iterator.next();  System.out.println("key=" + key + " value=" + map.get(key)); }
           

強烈建議使用第一種 EntrySet 進行周遊。

第一種可以把 key value 同時取出,第二種還得需要通過 key 取一次 value,效率較低。

三、高并發下的HashMap

在并發環境下使用 HashMap 容易出現死循環。

HashMap的容量是有限的。當經過多次元素插入,使得HashMap達到一定飽和度時,Key映射位置發生沖突的幾率會逐漸提高。這時候,HashMap需要擴充它的長度,也就是進行Resize。擴容的影響因子就是Capacity(容量)、LoadFactor(加載因子),當 HashMap 的 size > 16*0.75 時就會發生擴容。

3.1、擴容

3.1.1、建立一個新的Entry數組

長度時原來的兩倍。

3.1.2、ReHash方法

/** * Transfers all entries from current table to newTable. */void transfer(Entry[] newTable, boolean rehash) {    int newCapacity = newTable.length;    for (Entry e : table) {        while(null != e) {            Entry next = e.next;            if (rehash) {                e.hash = null == e.key ? 0 : hash(e.key);            }            int i = indexFor(e.hash, newCapacity);            e.next = newTable[i];            newTable[i] = e;            e = next;        }    }}
           

并發場景發生擴容,調用 Resize() 方法裡的 Rehash() 時,容易出現環形連結清單。這樣當擷取一個不存在的 key 時,計算出的 index 正好是環形連結清單的下标時就會出現死循環,避免這種情況,通常采用ConcurrentHashMap。

hashmap底層原理_Java集合架構(四)搞定HashMap底層原理一、結構二、方法三、高并發下的HashMap四、優化

是以 HashMap 隻能在單線程中使用,并且盡量的預設容量,盡可能的減少擴容。

四、優化

在 JDK1.8 中對 HashMap 進行了優化:

當 hash 碰撞之後寫傳入連結表的長度超過了門檻值(預設為8),連結清單将會轉換為紅黑樹。

假設 hash 沖突非常嚴重,一個數組後面接了很長的連結清單,此時時間複雜度就是 O(n) 。如果是紅黑樹,時間複雜度就是 O(logn) ,大大提高了查詢效率。

hashmap底層原理_Java集合架構(四)搞定HashMap底層原理一、結構二、方法三、高并發下的HashMap四、優化

繼續閱讀