初期容量と負荷係数は、HashMapパフォーマンスに影響を与える 2 つのパラメーターです。デフォルトの負荷係数 ( .75) は、時間とスペースのコストの間の適切なトレードオフを提供します。値を大きくすると、領域のオーバーヘッドが減少しますが、ルックアップ コストが増加します。
アイテムが に追加されると、そのアイテムから派生した値と のバケット サイズにHashMap基づいてバケットに割り当てられます。のバケットを識別するには、ハッシュ マップを使用していくつかの操作を実行します。hashCodeHashMapkey.hashCode()
Bucket (index) = HashMap.indexFor(HashMap.hash(key.hashCode()),
entryArray.length)
ハッシュ マップのエントリ数が負荷係数と現在の容量の積を超えると、ハッシュ マップが再ハッシュされ (内部データ構造が再構築され)、ハッシュ マップのバケット数が約 2 倍になります。
すべてを再ハッシュして新しい場所 (バケットなど) に移動すると、古い要素も再ハッシュされ、新しいハッシュ コードに従って新しいバケットに格納されます。要素を格納するために割り当てられた古い領域はガベージ コレクションされます。
サイズ変更が必要なスレッドが 2 つ同時に検出され、HashMap両方がサイズ変更を試みた場合、 で競合状態が発生する可能性がありHashMapます。
のサイズ変更のプロセスでHashMap、リンクされたリストに格納されているバケット内の要素は、新しいバケットへの移行中に順番が逆になります。これは、JavaHashMapが末尾に新しい要素を追加せず、末尾を避けるために先頭に新しい要素を追加するためです。トラバース。競合状態が発生すると、無限ループに陥ります。
次の質問があります。
- 新しいバケットへの移行中に、各バケットのリンク リストの順序が逆になるのはなぜですか?
- どのように競合状態が無限ループにつながる可能性がありますか?
- バケットの数を増やすと、ルックアップの待機時間をどのように短縮できますか?
- 同じバケットにある要素は、再ハッシュ後も同じバケットにまとめられますか?