各コレクションの特徴
・参考
コレクションクラスの比較 - Javaちょこっとリファレンス
| xxxxxxxxxxx | ArrayList | LinkedList | HashMap | LinkedHashMap | TreeMap | HashSet | TreeSet |
|---|---|---|---|---|---|---|---|
| ｲﾝﾀﾌｪｰｽ | List | List | Map | Map | Map | Set | Set |
| 重複 | ○ | ○ | × | × | × | × | × |
| null可否 | ○ | ○ | ○ | ○ | × | ○ | × |
| 自動ソート | × | × | × | × | ○ | × | ○ |
| 備考 | 格納した順番が保持される |
List
List構造は要素を順番付けして管理するデータ構造。
要素が番号順に並んでいるので、要素番号を指定して取得する。O(1)
list.get(1);
要素番号がわからない時は要素の値で検索。O(n)
list.indexOf("ねこ"));
Map
Map構造はキーと値をセットにした要素を持つデータ構造。
キーの重複は不可。
キーを指定して要素を取得する。O(1)
map.getKey("a");
HashMapは検索時のアドレス特定方法が面白い↓
HashMapについてのメモ - okinawa
Set
Set構造は要素を順番付けせずに管理するデータ構造。
キーや要素番号がない。
そのため要素を1個指定して取得することができない。
要素取得にはIteratorや拡張for文を使う。
コレクションの計算量
| クラス | 追加 | 検索 | 挿入/削除 | ランダムアクセス | メモリ使用量 |
|---|---|---|---|---|---|
| ArrayList | O(n) | O(n) | O(n) | O(1) | 少ない |
| LinkedList | O(1) | O(n) | O(1) | O(n) | 中 |
| HashSet | O(1) | O(1) | O(1) | 不可能 | 多い |
| TreeSet | O(log n) | O(log n) | O(log n) | 不可能 | 不明 |
↑色々みたけど微妙に書いてることが違って正解がわからず。この表は当てになりません。
後で修正したい。
※ランダムアクセスの補足
- ランダムアクセス：アクセスする場所を特定して、そこに一発でアクセスするやり方
- シーケンシャルアクセス：端から順番に見ていきながらアクセスする場所を探すやり方
・参考
JavaでよくつかうCollection実装クラスの仕組みと特性 - Qiita
Collectionインターフェイスの計算量 - 数学/競プロメモ
計算量の目安
| 計算量の例 | 意味 | |
|---|---|---|
| O(1) | データ数によらず一定時間で処理が完了する | 小 |
| O(log N) | データ数の対数に比例して処理時間が増える | ↑ |
| O(N) | データ数に比例して処理時間が増える | ↓ |
| O(N2) | データ数の2乗に比例して処理時間が増える | 大 |
| 計算量の例 | 意味 |
|---|---|
| O(1) | ハッシュテーブルのアクセス（衝突なし） |
| O(log N) | 二分探索 |
| O(N) | ループ、線形探索 |
| O(N log N) | 標準APIが提供するソートアルゴリズム ※ |
| O(N2) | 二重ループ |
