Collectionの活用 その２ リストの初期サイズ

今回もArrayListについてです。
リストを生成するとき、以下のようにコンストラクタの引数に初期サイズ（int型）を与えることができます。

List<String> list = new ArrayList<String>(100);

この初期サイズって別に設定しなくても要素の追加はできるので、わざわざ設定する必要はあるのでしょうか。

ネットから拾い集めた情報を元に整理したところ、以下の結論に至りました。

①あらかじめリストのサイズがわかっている場合
②リストのサイズが動的に変化し、最大要素数が少ない場合（1000要素以下くらい?）
③リストのサイズが動的に変化し、最大要素数が多い場合
①、③⇒初期サイズを指定する
②⇒初期サイズを指定しない（ただし、最大要素数と最小要素数の差が小さい場合は設定する）

上記を説明するためには、ArrayListの仕組みを理解しておく必要があります。
ArrayListは内部で配列を生成しており、
リストに要素が追加される際に配列のサイズが足りない場合配列を拡張する処理を行っています。

ArrayListの実装は以下の通りです。
１．初期サイズが指定された場合そのサイズの配列を生成。
　　初期サイズが指定されていない場合、初期サイズ10の配列を生成。
２．要素がaddされる際に配列のサイズが足りない場合、以下の手順で配列を拡張します。
　(1)サイズの大きい配列（サイズは↓）を新たに生成
　　int newCapacity = oldCapacity + (oldCapacity >> 1);　・・・（※）
　(2)古い配列から新しい配列に全要素をコピー
※「>>」はシフト演算子（ビット演算子）

どうやらArrayListの初期サイズは上記の配列拡張処理よるパフォーマンスの低下を防ぐために設定するみたいです。
また、配列生成時に初期サイズ分のメモリ領域を確保するため、
無駄に大きいサイズを指定するとこの分のメモリ領域が無駄になってしまいます。

リストに追加する要素の数があらかじめ分かっている場合、
初期サイズを設定することで、配列の拡張を防いでかつ無駄なメモリ容量を食わずに済みます。

リストに追加する要素の数が場合によって変化する場合はどうかというと、
例えば条件によってリストに1000件要素を追加する場合と1件しか追加しない場合があるとして、
初期サイズを1000に設定したにも関わらず1要素しか追加しなかった場合、
用意したメモリ領域がほとんど無駄になってしまいます。
1000件の要素を追加する条件だったとしても、
配列拡張処理の処理時間なんて気にするほどの処理時間ではないので、
メモリ容量を優先して②の結論としました。
要素のサイズが10000を超えてくると、
さすがに処理時間を気にせざるを得なくなるので、③の結論としています。

システムの性能を意識したコーディングをする場合は参考にしてみてください。

（豆知識）
HashMapの実態も実は配列です。ハッシュコードをキー値と紐付けて配列から値を取ってくる仕組みのようです。
HashMapのデフォルト初期サイズは16で、
ArrayListと同様にインスタンス化の際に引数に初期サイズを指定することができます。