HashMap源碼淺析（一）

HashMap<T>

java.util.HashMap

其内部的沖突解決方案采用的是拉鍊法，故HashMap的結構表現為數組+連結清單

插入時，先根據Key的hashCode，定位到待插入的位址，若待插入的位址為空，則直接插入；若待插入的位址不為空，說明發生沖突，則用拉鍊法，将元素插入到該位址的連結清單中。

拉鍊法會導緻連結清單過深，而造成性能下降的問題，HashMap中，當連結清單長度過長時，會選擇将結構轉化成紅黑樹

• 為什麼不用二叉排序樹呢？：因為二叉排序樹在某些較壞情況下會不平衡，甚至在最壞情況下會退化成連結清單，性能仍然很低下
• 為什麼不用AVL樹呢？：AVL樹是嚴格的平衡二叉樹，當插入或删除節點時，隻要一破壞了平衡條件，就要通過旋轉來保持平衡，而旋轉操作是比較耗時的，AVL更适合插入删除較少，查詢較多的情況。在實際情況中，AVL樹用于保持平衡所付出的代價，比從中擷取的收益還大，而我們更多是追求局部的而不是全局的嚴格平衡，紅黑樹是一種弱平衡二叉樹，相同節點的情況下，紅黑樹的高度可能會大于AVL樹，相對AVL樹來說，紅黑樹的旋轉次數更少，為保持平衡而付出的性能開銷更低，紅黑樹更适用于插入，删除，查找都較多的情況

當連結清單的長度超過樹化門檻值（

TREEIFY_THRESHOLD = 8

），則把連結清單轉化為紅黑樹，若連結清單長度低于非樹化門檻值（

UNTREEIFY_THRESHOLD = 6

），則将紅黑樹重新轉化為連結清單（連結清單過長時，效率會降低，故轉化為紅黑樹關于紅黑樹）

Hash的沖突解決方案

• 開發定址法

  插入元素時，若發生沖突，則按照某種算法，向後探測，直到遇到空位為止

  • 線性探測法

    fi = ( f(key) + i ) % m 0 ≤ i ≤ m-1

    發生沖突時，依次向後探測。先探測

    T[d]

    ，接着依次探測

    T[d+1]

    ，

    T[d+2]

    ，… 直到

    T[m-1]

    缺點：會産生聚集，導緻性能下降
  • 二次探測法

    fi = ( f(key) + di ) % m 0 ≤ i ≤ m-1

    發生沖突時，依次向後探測。先探測

    T[d]

    ，接着探測

    T[d+di]

    ，

    di

    為增量序列12，22，…，q2，且

    q ≤ 1/2(m-1)

  • 僞随機探測法

    增量是個僞随機數序列

  • 再散列法

    fi = ( f(key) + i * g(key) ) % m i = 1,2...,m-1

    沖突時，采用另一個哈希函數

    g()

    ，依次向後進行探測
  注意：通過開放定址法，可能會産生堆積，并且删除時，不能直接删除，隻能添加一個删除标記，因為直接删除會導緻該位置的值是null，若存在同義詞且在該位置之後，則無法被查找到

• 拉鍊法

  将沖突的值以連結清單的形式進行追加

  注意：當連結清單過長，甚至比數組長度還長時，會大大降低查找的效率，在HashMap的實作中，當連結清單的長度大于8時，就會進行樹化，轉化為紅黑樹。并且哈希表有一個負載因子 α ，在HashMap中被設定為0.75，當哈希表的 元素數量 / 數組大小 超過這個負載因子時，就進行擴容，并且将元素rehash。采用拉鍊法解決沖突的哈希表中，α可以超過1（拉鍊法的哈希表，α其實就代表了連結清單的平均長度），而純數組的哈希表，α必定小于1

紅黑樹

紅黑樹是具備以下特征的二叉樹

• 節點是紅色或黑色
• 根節點是黑色
• 每個葉子的節點都是黑色的空節點
• 紅色節點的2個子節點必須都是黑色
• 從任意節點出發，到其的每個葉子節點的所有路徑，都包含相同數目的黑色節點

紅黑樹可以保證最長路徑不超過最短路徑的2倍

紅黑樹插入節點時，保持平衡需要做變色和旋轉等操作，具體的内容，待下次追加。

HashMap在多線程環境下，可能會出現死循環的問題，若2個線程同時調用HashMap的

resize()

方法，HashMap的

resize()

對哈希表中的連結清單， 采用的是頭插法（這樣避免了尾部周遊，即每次都需要周遊到尾部才進行插入，這樣效率會很低，也正是因為頭插法，導緻了連結清單中元素順序颠倒了，這也解釋了HashMap為什麼不保證有序），在某些條件（多線程産生條件競争）下，可能會造成環形連結清單，若此時嘗試通過一個不存在的key，去從HashMap中取值，則會造成無限循環（根據hash值去到了這個環形連結清單的桶中，會一直往下周遊，嘗試擷取到和key相等的那個Entry，而因為是環形連結清單，則會無限循環）。

在HashMap等一些線程不安全的集合類中，都會包含一個叫做

modCount

的變量，存儲的是該HashMap執行個體被修改的次數，修改包括：1. 元素數量的改變（插入/删除） 2. HashMap結構的改變（樹化）

該變量和線程安全相關。在使用

Iterator

疊代器對HashMap進行周遊時，初始化疊代器時會存儲當時的

modCount

值，如果有其他線程對該map做了修改，會導緻該map的

modCount

發生變化，疊代過程中會将存儲下來的

modCount

和map目前的

modCount

做比較，若兩者不一緻，則會抛出

ConcurrentModificationException

，這就是HashMap的fail-fast政策。

故，一般建議對線程不安全的容器進行周遊時，用疊代器。