hashMapソース分析1.8
1664 ワード
HashMap JDK 1.8のHashMap:下位実装(配列+チェーンテーブル/赤黒ツリー)
1、なぜJDK 1.8以前のチェーンテーブル設計からチェーンテーブルや赤黒ツリーの設計に変更したのですか? あるチェーンテーブルが長い場合、検索効率は低下します. クエリー効率を向上させるためにtable[index]の下のチェーンテーブルを調整します. table[index]のチェーンテーブルのノード数が比較的少ない場合(8個以内)はチェーンテーブルを保持する.8個を超える場合は、チェーン時計を赤と黒の木に変えることを考えます. TREEIFY_THRESHOLD:ツリー化しきい値,チェーンテーブルからレッドブラックツリーの臨界値に移行する.
2、いつ木化しますか? table[index]での結点数が8個になると樹化しますか? table[index]のノード数が8個に達した場合、table.lengthが64に達したかどうかを判断し、64に達していない場合は、先に拡張する.
デモ:8->9 length 16->32
MIN_TREEIFY_CAPACITY:最小ツリー容量64
3、いつツリーから->チェーンテーブル ノードを削除すると、このツリーのノード数は6個未満で、逆ツリー化され、チェーンテーブル になります. UNTREEIFY_THRESHOLD:6個
ツリーの構造は複雑すぎて、ノードが少なくなったらチェーンテーブルを使うほうがいいです.
4、putのプロセス (1)[index]の計算問題 最初のステップは、hash()関数をkeyのhashCode値で呼び出し、hash値を干渉させ、table配列のより均一な分布をもたらす. JDK 1.8におけるhash()アルゴリズムの方が最適化されている.
第2歩:hash値とtable.length-1は&演算を行い、indexが[0,length-1]の範囲内で であることを保証する.
(2)拡張問題 第1種:あるtable[index]のチェーンテーブルの個数が8個に達し、table.length<64になると、 が拡張する.第2種:size>=threshold,table[index]!=null threshold=table.length*loadFator(デフォルトDEFAULT_LOAD_FACTOR:0.75)
(3)チェーンテーブルに(key,value)を追加すると、JDK 1.8はチェーンテーブルの末尾 である.
9 ->10 length 32->64
10 ->11 length 64，table[index] Node TreeNode ，