Java中HashMap詳解

HashMap詳細解析

• ​​HashMap的工作方式​​
• ​​HashMap的實作原理​​
• ​​HashMap的資料結構​​
• ​​HashMap構造函數​​
• ​​HashMap重要方法​​
• • ​​hash(K)​​
  • ​​put(K, V)​​
  • ​​resize()​​
  • ​​treeifyBin()​​
  • ​​get(K)​​
• ​​Hash沖突​​
• ​​HashMap總結​​
• ​​HashMap中MAXIMUM_CAPACITY設定為1<<30​​
• ​​HashMap中容量設定為2的整數幂次方​​
• ​​HashMap中的負載因子設定為0.75​​
• ​​HashMap中的元素盡量使用疊代器Iterator周遊​​
• ​​HashMap的使用特點​​

HashMap的工作方式

• HashMap在Map.Entry靜态内部類實作中存儲key-value對
• HashMap使用雜湊演算法,在put() 和get() 方法中,使用了hashCode() 和equals() 方法
• • 通過傳遞key-value對調用put() 方法時 ,HashMap使用key hashCode() 和雜湊演算法找到存儲key-value對的索引 .Entry存儲在LinkedList中,如果存在Entry, 會使用equals() 方法來檢查傳遞的key是否存在.如果存在,就會覆寫value. 如果不存在,就會建立一個新的Entry來儲存
  • 通過傳遞key調用get() 方法時,再次使用key hashCode() 方法來找到數組中的索引,然後使用equals() 方法找出正确的Entry并傳回Entry的值

HashMap的實作原理

• Java中的資料結構映射定義了接口java.util.Map, 接口有以下四個常用的實作類:
• • HashMap:
  • • HashMap根據鍵的hashCode值存儲資料,通常可以根據鍵的hashCode值直接定位到鍵對應的值,進而具有很快的通路速度
    • HashMap中周遊的順序是不确定的
    • HashMap中最多隻允許一條資料的鍵為null, 可以允許多條資料的值為null
    • HashMap是線程不安全的.在同一時刻允許多個線程同時寫入HashMap, 這樣就會導緻資料的不一緻
    • HashMap如果想要滿足線程安全,可以使用Collections的synchronizedMap() 方法使得HashMap具有線程安全性,或者使用ConcurrentHashMap
  • Hashtable:
  • • Hashtable和HashMap類似,隻是Hashtable繼承自Dictionary類
    • Hashtable中的鍵和值都不能為null
    • Hashtable是線程安全的.在同一時刻隻允許一個線程寫入Hashtable. 但是Hashtable的并發性不如引入了分段鎖的ConcurrentHashMap
    • • Hashtable是通過為方法添加synchronized鎖實作線程安全的
      • ConcurrentHashMap是由Segment資料結構和HashEntry資料結構組成的
      • • Segment是一種可重入鎖ReentrantLock, 在ConcurrentHashMap中作為鎖
        • HashEntry用于存儲鍵值對資料
        • • 一個ConcurrentHashMap包含一個Segment數組 .Segment的資料結構和HashMap類似,是一種數組和連結清單的結構
          • 一個Segment中包含一個HashEntry數組.每個HashEntry是一個連結清單結構的元素
          • 一個Segment守護一個HashEntry數組中的元素
          • HashEntry中的資料進行修改時,必須首先獲得HashEntry對應的Segment鎖
      • 分段鎖:
      • • 分段鎖的含義就是用到哪一部分就鎖定哪一部分
        • 分段鎖就是将整個Map劃分成N個Segment, 在進行put() 和get() 操作時,根據鍵的hashCode值尋找到應該使用哪個Segment. 這個Segment做到了類似HashTable的線程安全
      • ConcurrentHashMap中的鍵和值都不能為null
    • 不建議使用HashTable, 在不需要線程安全的場景中,可以使用HashMap. 在需要線程安全的場景中,可以使用ConcurrentHashMap
  • LinkedHashMap:
  • • LinkedHashMap是HashMap的一個子類
    • LinkedHashMap中儲存了資料的插入順序.使用Iterator周遊LinkedHashMap時,首先得到的資料一定是首先插入的
    • LinkedHashMap中可以使用帶參的構造函數來按照通路次序進行排序
  • TreeMap:
  • • TreeMap實作了SortedMap接口
    • TreeMap可以将儲存的資料按照鍵來進行排序.預設是按照鍵值進行升序排序,也可以指定排序的比較器.使用Iterator周遊TreeMap時,得到的資料時排序後的資料
    • 如果需要使用排序的映射,建議使用TreeMap. 使用TreeMap時,鍵必須實作Comparable接口或者是在構造TreeMap時傳入自定義的Comparator, 否則會在運作時抛出java.lang.ClassCastException異常

      
• Map類都是要求映射中的鍵key是不可變對象:
• • 不可變對象就是這個對象建立後,對象的hashCode值不會改變
  • 如果對象的hashCode值發生改變,就很可能無法定位到映射的位置

HashMap的資料結構

• HashMap使用數組+連結清單+紅黑樹的資料結構存儲資料的
• HashMap的内部資料結構是一個桶數組
• • 每一個桶中存放着一個單連結清單的頭節點
  • 每一個節點中存儲着一個鍵值對Entry
• HashMap采用拉鍊法解決存在的Hash沖突問題
• • 拉鍊法: 也就是鍊位址法,是數組和連結清單的結合.在每個數組元素上都有一個連結清單結構,當資料進行Hash之後,得到數組的下标,然後将資料存放到對應下标元素的連結清單上

    

• Node:
• • Node是HashMap的一個内部類,實作了Map.Entry接口,本質上就是一個鍵值對映射

HashMap構造函數

• HashMap中有三個構造函數 : 通常情況下,使用預設的無參構造函數.在能夠預估到資料的容量時推薦使用指定容量大小的構造函數

public HashMap();

public HashMap(int initialCapacity);

public HashMap(int initialCapacity, float loadFactor);
      

• 構造函數中隻是設定了幾個參數的值,沒有對數組和連結清單進行初始化,在第一次put操作時才調用resize() 方法初始化數組tab. 這樣可以很好的節省空間
• HashMap函數構造過程:
• • 首先,在數組Node[] table中
  • • length: 初始化長度,預設為16
    • loadFactor: 負載因子,預設為0.75
    • • 預設負載因子0.75是對空間和時間效率的平衡性的選擇,不建議修改,隻有在時間和空間比較特殊的情況下才需要修改:
      • • 記憶體較多但是對時間效率要求很高: 降低負載因子loadFactor的值
        • 記憶體緊張但是對時間效率要求不高: 增加負載因子loadFactor的值,這個值可以大于1
    • threshold: HashMap中能夠容納的最大資料量的鍵值對Node個數.

    • t

      h

      r

      e

      s

      h

      o

      l

      d

      =

      l

      e

      n

      g

      t

      h

      ∗

      l

      o

      a

      d

      F

      a

      c

      t

      o

      r

      threshold = length * loadFactor

      threshold=length∗loadFactor : 定義好數組長度之後,負載因子越大,能夠容納的鍵值對個數越多

    • • threshold是對應的數組長度length和負載因子loadFactor允許的最大元素數量,超過這個數量HashMap就會重新擴容resize. 擴容後的HashMap容量是目前容量的兩倍

HashMap重要方法

hash(K)

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

• Java的HashMap中,沒有直接使用hashcode() 作為HashMap中的hash值
• HashMap中将hashcode() 的值無符号右移16位得到一個新值,然後将hashcode() 的值和這個新值進行異或運算得到最終的hash值儲存在HashMap中. 這樣可以避免哈希碰撞
• • 比如容量大小n為16時 ,n-1為15(0x1111), 散列值真正生效的隻是低4位,此時新增的鍵的hashcode() 的值如果是2,18,34這樣以16的倍數為差的等差數列時,就會産生大量的哈希碰撞

  • 使用這樣的方法,将高16位和低16位進行異或,因為大部分hashcode() 的值分布已經很均勻了,即使發生碰撞也用

    O

    (

    l

    o

    g

    n

    )

    O(logn)

    O(logn)時間複雜度的紅黑樹進行了優化.這樣通過使用異或的方法,不僅減少了系統開銷,也不會因為tab長度較小時高位沒有參與下标的運算引發哈希碰撞

put(K, V)

• 使用put(K, V) 操作時 ,HashMap計算鍵值K的哈希值,然後将這個鍵值對Entry放入到HashMap中對應的桶bucket上
• 然後尋找以目前桶為頭結點的一個單連結清單,順序周遊單連結清單找到某個節點的Entry中的key等于給定的參數K
• 如果找到則将舊的參數值V替換為參數指定的V. 否則直接在連結清單的尾部插入一個新的Entry節點

if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
      

• HashMap中重寫equals() 方法必須也要重寫hashcode() 方法:
• • 根據hash值,定位到數組某個位置後,向位置中後面的連結清單添加元素時,判斷元素是否一樣中,首先判斷hash值是否相等,然後再判斷equals()
  • 如果隻對equals() 進行重寫,不對hashcode() 進行重寫時,依然會按照不同的兩個對象處理,是以重寫equals() 方法時必須也要重寫hashcode() 方法
• HashMap中既要判斷hash值,也要使用equals() 方法判斷:
• • HashMap中連結清單結構進行周遊判斷時,重寫的equals() 方法判斷對象是否相等的業務邏輯比較複雜,這樣下來的循環周遊判斷影響性能
  • HashMap中将hash值的判斷放在前面,隻要hash值不同,整個條件就是false, 不需要進行equals() 方法判斷對象是否相等,提升了HashMap的性能
  • HashMap中是根據hashcode() 的值定位到數組的位置的,同一個數組位置中後面的連結清單中元素的hashcode() 的值都相同.比較hashcode() 的值沒有意義,因為必定相等 .HashMap中沒有直接使用hashcode() 的值,用的是對hashcode() 的值進行移位和異或運算後的hash值,這裡比較的是元素的hash值

resize()

• 初始化HashMap時,按照門檻值threshold配置設定記憶體
• 如果HashMap中的資料記錄超過HashMap的門檻值就會進行擴容
• 擴容時,數組會采用将數組容量大小的值左移一位的算法将将數組擴容至兩倍
• 擴容時,根據資料的hash值與數組長度進行邏輯與運算,根據運算結果是否為0來決定資料是不動還是将數組索引位置變更為目前索引位置和原數組長度之和
• 擴容時不會重新計算hash值 ,key的hash值會儲存在數組位置的後面的node節點元素中

treeifyBin()

• 數組中單個連結清單長度超過8, 數組的長度超過64時才會進行連結清單結構到紅黑樹結構的轉換,否則隻是進行擴容操作
• HashMap中,使用紅黑樹結構占用空間大,盡可能不使用紅黑樹結構

get(K)

• HashMap通過計算鍵的哈希值,尋找到對應的桶bucket, 然後順序周遊桶bucket存放的單連結清單,通過比對Entry的鍵找到對應的哈希值
• 如果對應位置後面是紅黑樹結構就在紅黑樹結構中查找,如果是連結清單結構就周遊連結清單,查詢需要找的對象
• • 紅黑樹周遊的時間複雜度 :

    O

    (

    l

    o

    g

    n

    )

    O(logn)

    O(logn)

  • 連結清單周遊的時間複雜度 :

    O

    (

    n

    )

    O(n)

    O(n)

Hash沖突

• Hash沖突:
• • 因為Hash是一種壓縮映射,這樣每一個Entry節點無法對應到一個隻屬于自身的桶bucket
  • 必然會存在多個Entry共用一個桶bucket, 拉成一個鍊條的情況.這種情況就是Hash沖突
• Hash沖突存在的問題:
• • 在Hash沖突的極端情況下,某一個桶bucket後面挂着的連結清單會特别長,導緻周遊的效率很低
• Hash沖突無法完全避免,為了提高HashMap的性能,需要盡量緩解Hash沖突來縮短每個桶的外挂連結清單的長度
• • 當HashMap中存儲的Entry較多時,需要對HashMap擴容來增加桶bucket的數量
  • 這樣對後續要存儲的Entry來講,就會大大緩解Hash沖突

HashMap總結

HashMap中MAXIMUM_CAPACITY設定為1<<30

• MAXIUM_CAPACITY:
• • int類型,表示HashMap的最大容量
  • 使用 << 移位運算的結果不能超過int類型表示的最大值
  • 使用1左移 << 運算時最大隻能左移30位,否則就會溢出
• Java中的int類型占4個位元組,每個位元組占用8位,是以int類型占用32位
• Java中的int類型是有符号的,使用第1位作為符号位,此時還有31位,這時使用1左移隻能左移30位

HashMap中容量設定為2的整數幂次方

• 通過限制一個數組長度length為2的整數幂次方的數,這樣使得 (length - 1) & h 和 h % length 的結果是一緻的
• HashMap中将容量設定為2的整數幂次方主要就是為了在取模和擴容時做優化,同時減少沖突

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }
      

• tab[(n - 1) & hash] : 根據hash值快速定位到數組的位置
• • 數組tab
  • 數組長度n
  • 需要查找的key對應的值hash
  • • 因為數組長度n設定為2的整數幂次方,這樣初始情況下n-1轉換為2進制時各個位上都是1
    • 此時使用 & 與對應的值hash進行運算時的結果就和hash值一樣,也就快速定位到了數組中的位置
    • 使得數組中的資料更加分散,減少碰撞
• 如果數組長度不是設定為2的整數幂次方:
• • 數組長度在初始情況下使用n-1轉換為2進制時,存在0位,導緻很多位置無法放置元素,造成空間浪費
  • 數組的有效使用位置大量減少,增加了碰撞幾率,減慢了查詢速度

HashMap中的負載因子設定為0.75

• 泊松分布: Poisson分布.描述某段時間内,事件具體的發生機率

  P

  (

  X

  =

  k

  )

  =

  λ

  k

  k

  !

  e

  −

  λ

  ,

  k

  =

  ,

  1

  ,

  …

  (

  λ

  是

  均

  值

  ,

  k

  為

  發

  生

  次

  數

  )

  P(X=k)=\frac{\lambda^k}{k!}e^{-\lambda},k=0,1,…(\lambda是均值,k為發生次數)

  P(X=k)=k!λk​e−λ,k=0,1,…(λ是均值,k為發生次數)

  

• TreeNode占用的空間是正常節點的兩倍,是以隻有當箱子bin(數組中的一個桶)中元素的數量超過TREEIFY_THRESHOLD時才會需要使用TreeNode
• HashMap中的hash值分布比較均勻時,很少使用到TreeNode

• 在随機hashcode情況下 ,bin中節點出現的頻率遵循泊松Poisson分布,此時負載因子為 0.75, 均值

  λ

  {\lambda}

  λ 為 0.5

• 如果調整負載因子的值,均值

  λ

  {\lambda}

  λ 會出現較大偏差

• HashMap擴容到32或者64時,一個箱子bin中存儲8個資料量的機率為0.00000006. 是以當一個箱子中節點數目大于等于8個時,可以将HashMap中桶中的資料從連結清單結構轉換為樹結構存儲,效果是最好的

HashMap中的元素盡量使用疊代器Iterator周遊

• 在疊代器Iterator中使用的fail-fast政策,在周遊發生線程并發時,可以立即抛出異常
• fail-fast政策:
• • HashMap是非線程安全的
  • 使用疊代器Iterator過程中,如果其餘的線程同時也在修改HashMap, 就會立即抛出ConcurrentModificationException異常
• fail-fast政策實作:
• • fail-fast政策通過modCount實作
  • modCount記錄修改次數
  • 在疊代器初始化過程中将modCount的值指派疊代器的expectedModCount
  • 在疊代器疊代過程中,判斷modCount和expectModCount是否相等.如果不相等就說明有其餘線程對HashMap進行了修改

Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
Iterator<Map.Entry<Integer, Integer>> entries = hashMap.entrySet().iterator();
while (entries.hasNext()) {
  Map.Entry<Integer, Integer> entry = entries.next();
  System.out.println("KEY = " + entry.getKey() + ", VALUE = " + entry.getValue());
}
      

HashMap的使用特點

• HashMap中的擴容是一個特别損耗性能的操作,是以在初始化HashMap時,應該估算HashMap的大小,确定一個大緻的數值,避免在使用HashMap時頻繁初始化
• HashMap是線程不安全的,在并發的環境中建議使用ConcurrentHashMap

• Java 8中引入紅黑樹極大程度地優化了HashMap的性能.主要展現在雜湊演算法不均勻時,也就是拉鍊法中連結清單很長時,可以将連結清單轉換為紅黑樹結構,此時算法複雜度由

  O

  (

  n

  )

  O(n)

  O(n)下降為

  O

  (

  l

  o

  g

  n

  )

  O(logn)

  O(logn)