java HashMapのキャパシティ拡張の詳細とサンプルコード

HashMapの拡張

前書き：

HashMapのsizeが容量*ロードファクター)のとき、拡張操作がトリガーされます。これは非常にコストがかかる操作です。

なぜ拡張が必要なのか?HashMapのデフォルトの容量は16、HashMapに要素が追加されると、ハッシュ衝突の確率が高くなり、各バケットに対応するリストが長くなるため、

これにより、クエリ性能に影響を与えます。なぜなら、要素を見つけるまで、リストを巡回し、オブジェクトが一致するかどうかを比較する必要があるからです。

クエリ性能を向上させるために、拡張を行い、ハッシュ衝突を減らし、要素のkeyができるだけ均等に分布するようにします。

拡張の基本

ロードファクターのデフォルト値は0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;

容量のデフォルト値は16

 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // =16

HashMapは、作成時に容量とロードファクターを指定できるコンストラクタを提供します。

 public HashMap(int initialCapacity, float loadFactor)

デフォルトでは、HashMapのsizeが16*0.75=12のこと

同時に、各Entry（またはバケット）に少なくとも1つの要素が含まれている場合、拡張が行われます。

 if ((size >= threshold) && (null != table[bucketIndex])) {
      resize(2 * table.length);
      hash = (null != key) ? hash(key) : 0;
      bucketIndex = indexFor(hash, table.length);
}

拡張する際には、コンテナの容量が倍になります

 resize(2 * table.length);

拡張する際には要素の配列インデックスを再計算する必要があります

1、新しいEntry配列を再割り当て
2、元の要素の新しい配列でのインデックスを再計算(リソース消費が多い)

ご読読ありがとうございます。皆様のサポートに感謝します。