List と Set の使い分けの話.
Java の List と Set の概念的な違いは「順序があるかどうか」です.
- List:順序を考慮するオブジェクトの集まり
- Set:順序を考慮しないオブジェクトの集まり
これまで,順序の有無だけで List と Set を選択していたんですが,もう1つ別の基準があることに気付きました.
- List:検索が遅い(線形探索で O(n),二分探索で O(log n))
- Set:検索が速い(常に O(1))
よって,Set と List の選択基準は次のようになります.
検索あり | 検索なし | |
順序あり | (1) List | (2) List |
順序なし | (3) Set | (4) List |
(4) が変則的ですが,これは Set の内部処理によるものです.
Set(HashSet)は内部で HashMap を使っているため,インスタンス生成時の初期値が重要になります.
- 初期容量 initialCapacity (デフォルトは16)
- 負荷係数 loadFacotr (デフォルトは0.75)
Set の要素数が initialCapacity * loadFacotr を超えるときは,リハッシュが発生します.
つまり,格納される要素数が予測できないとき Set は非効率になる可能性があるということです.
このことから,「順序がない」かつ「検索もない」ときは List を使ったほうがいいと気付きました.
(ただ,1度も検索されないコレクションというのはなかなか無い気がするので,(4) の場面は多くないかも?)