hashMapソース分析1.8

1664 ワード

java

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

9 ->10   length 32->64

10 ->11  length    64，table[index]  Node    TreeNode  ，

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はチェーンテーブルの末尾

である.