13
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@S_kamonin株式会社VISIONARY JAPAN

JavaのListとMapの種類を整理する

13
Posted at

はじめに

Javaでコレクションを使うとき、こんな疑問を持ったことはありませんか？

  • ArrayList と LinkedList ってどう違うの？
  • HashMap と LinkedHashMap と TreeMap、何を使えばいい？
  • とりあえず ArrayList と HashMap を使っているけど、それで大丈夫？

この記事では、ListとMapの主要な実装クラスの違いと使い分けを整理します。

Javaのコレクション全体像

まず、全体の構造を把握しておきましょう。

Iterable
  └── Collection
        ├── List         （順序あり・重複あり）
        │     ├── ArrayList
        │     ├── LinkedList
        │     └── Vector（古い・非推奨）
        │
        ├── Set          （順序なし・重複なし）
        │     ├── HashSet
        │     ├── LinkedHashSet
        │     └── TreeSet
        │
        └── Queue / Deque
              └── LinkedList（Dequeも実装）

Map                      （キーと値のペア）
  ├── HashMap
  ├── LinkedHashMap
  ├── TreeMap
  └── Hashtable（古い・非推奨）

この記事では List と Map に絞って解説します。

List の種類

List は順序があり、重複を許可するコレクションです。インデックス（添え字）でアクセスできます。

1. ArrayList

最もよく使われる実装クラスです。内部的には動的配列で管理しています。

List<String> list = new ArrayList<>();
list.add("田中");
list.add("佐藤");
list.add("鈴木");

System.out.println(list.get(0)); // 田中
System.out.println(list.size()); // 3

内部構造のイメージ

インデックス:  [0]    [1]    [2]    [3]    [4]  ...
データ:       田中   佐藤   鈴木   null   null  ...

配列の末尾に要素を追加するのは速いですが、容量が足りなくなると新しい配列を確保してコピーします。

得意・苦手

操作 速さ 理由
get(index) ◎ 速い インデックスで直接アクセスできる
add(末尾) ◎ 速い 末尾に追加するだけ
add(先頭・中間) △ 遅い 後ろの要素をすべてずらす必要がある
remove(先頭・中間) △ 遅い 後ろの要素をすべてずらす必要がある
contains() △ 遅い 先頭から全件走査

こんな時に使う

  • データの読み取り（get）が多い
  • 末尾への追加・削除が多い
  • 迷ったらとりあえずこれを選ぶ

2. LinkedList

内部的には双方向連結リストで管理しています。

List<String> list = new LinkedList<>();
list.add("田中");
list.add("佐藤");
list.add("鈴木");

内部構造のイメージ

[田中] ⇄ [佐藤] ⇄ [鈴木]
 前後の要素へのポインタを持つ

各要素が「前の要素」「次の要素」へのポインタを持つため、先頭・末尾への追加・削除は非常に速いです。一方、インデックスアクセスは先頭から順に辿るため遅いです。

得意・苦手

操作 速さ 理由
get(index) △ 遅い 先頭からポインタを順に辿る必要がある
add(先頭・末尾) ◎ 速い ポインタを付け替えるだけ
add(中間) ◎ 速い 前後のポインタを付け替えるだけ
remove(先頭・末尾) ◎ 速い ポインタを付け替えるだけ
メモリ △ 多い 各要素がポインタを2つ持つ

こんな時に使う

  • 先頭・末尾への追加・削除が頻繁に発生する（キュー・スタックとして使う）
  • Deque インターフェースも実装しているので、両端からの操作が必要な場合
// LinkedListはDequeとしても使える
Deque<String> deque = new LinkedList<>();
deque.addFirst("先頭");  // 先頭に追加
deque.addLast("末尾");   // 末尾に追加
deque.pollFirst();       // 先頭から取り出し

ArrayList vs LinkedList まとめ

比較項目 ArrayList LinkedList
内部構造 動的配列 双方向連結リスト
インデックスアクセス ◎ 速い △ 遅い
先頭・中間の追加・削除 △ 遅い ◎ 速い
末尾への追加 ◎ 速い ◎ 速い
メモリ効率 ◎ 良い △ 悪い（ポインタ分余分）
Dequeとして使える ✗ ✓
おすすめ度 ほとんどの場面で第一選択 先頭操作が多い場面のみ

実務のポイント： 実際には ArrayList で十分なケースがほとんどです。LinkedList が有利なのはかなり限られた場面です。

Map の種類

Map はキーと値のペアを管理するコレクションです。キーは重複できません。

1. HashMap

最もよく使われるMapの実装です。ハッシュテーブルで管理しています。

Map<String, Integer> map = new HashMap<>();
map.put("田中", 85);
map.put("佐藤", 92);
map.put("鈴木", 78);

System.out.println(map.get("田中")); // 85
System.out.println(map.containsKey("佐藤")); // true

特徴

  • キーの順序は保証されない（実行するたびに順番が変わりうる）
  • get / put / containsKey がほぼ O(1)（定数時間）で動く
  • null をキーや値として使える
// 順序が保証されない例
Map<String, Integer> map = new HashMap<>();
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);

// 出力順は実行ごとに異なる可能性がある
for (String key : map.keySet()) {
    System.out.println(key + ": " + map.get(key));
}

こんな時に使う

  • 順序が不要で、とにかく高速に検索・追加・削除したい
  • 迷ったらとりあえずこれを選ぶ

2. LinkedHashMap

HashMap に挿入順序の保持を追加したものです。内部的にはハッシュテーブル＋双方向連結リストで管理します。

Map<String, Integer> map = new LinkedHashMap<>();
map.put("田中", 85);
map.put("佐藤", 92);
map.put("鈴木", 78);

// 挿入した順番で出力される
for (String key : map.keySet()) {
    System.out.println(key + ": " + map.get(key));
}
// 田中: 85
// 佐藤: 92
// 鈴木: 78

特徴

  • HashMap と同じ速さで動く（ほぼ O(1)）
  • 挿入した順番を保持する
  • HashMap よりわずかにメモリを多く使う

こんな時に使う

  • 挿入した順番を保ちながら処理したい
  • レスポンスのJSONキーを挿入順で出力したい

3. TreeMap

キーを自然順（アルファベット順・数値の昇順）でソートして管理する Mapです。内部的には**赤黒木（Red-Black Tree）**というデータ構造を使っています。

Map<String, Integer> map = new TreeMap<>();
map.put("鈴木", 78);
map.put("田中", 85);
map.put("佐藤", 92);

// キーのアルファベット順（この場合は五十音順）で出力される
for (String key : map.keySet()) {
    System.out.println(key + ": " + map.get(key));
}
// 佐藤: 92
// 鈴木: 78
// 田中: 85

特徴

  • キーが常にソートされた状態に保たれる
  • get / put が O(log n)（HashMapより遅い）
  • null キーは使えない
  • Comparable を実装した型か、Comparator を指定する必要がある
// カスタム順でソートする場合
Map<String, Integer> map = new TreeMap<>(Comparator.reverseOrder()); // 逆順
map.put("鈴木", 78);
map.put("田中", 85);
map.put("佐藤", 92);
// 田中 → 鈴木 → 佐藤 の順になる

こんな時に使う

  • キーを常にソートされた状態で管理したい
  • 範囲検索（「A以上B未満のキー」など）を行いたい
TreeMap<String, Integer> treeMap = new TreeMap<>(map);
// 特定のキー以降のエントリを取得
System.out.println(treeMap.tailMap("田中")); // {田中=85}

HashMap vs LinkedHashMap vs TreeMap まとめ

比較項目 HashMap LinkedHashMap TreeMap
内部構造 ハッシュテーブル ハッシュ＋連結リスト 赤黒木
順序 保証なし 挿入順 キーの昇順
get / put の速さ ◎ O(1) ◎ O(1) △ O(log n)
nullキー ✓ 使える ✓ 使える ✗ 使えない
メモリ効率 ◎ △（ポインタ分多い） △（ツリー構造分多い）
おすすめの場面 高速検索・順序不要 挿入順を保ちたい ソート・範囲検索

よく使う操作のチートシート

List 操作

List<String> list = new ArrayList<>(List.of("田中", "佐藤", "鈴木"));

// 追加
list.add("山田");              // 末尾に追加
list.add(0, "伊藤");          // 指定インデックスに追加

// 取得
String first = list.get(0);   // インデックスで取得

// 削除
list.remove(0);                // インデックスで削除
list.remove("佐藤");           // 値で削除

// 検索
boolean contains = list.contains("鈴木"); // 含むか確認
int index = list.indexOf("田中");         // インデックスを取得

// サイズ
int size = list.size();

// ループ
for (String name : list) {
    System.out.println(name);
}

// ソート
Collections.sort(list);                             // 自然順
list.sort(Comparator.comparingInt(String::length)); // 文字数順

Map 操作

Map<String, Integer> map = new HashMap<>();

// 追加・更新
map.put("田中", 85);

// 取得
Integer score = map.get("田中");            // nullの可能性あり
Integer score2 = map.getOrDefault("山田", 0); // なければデフォルト値

// 削除
map.remove("佐藤");

// 検索
boolean hasKey = map.containsKey("田中");
boolean hasValue = map.containsValue(85);

// ループ
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

// キーの一覧・値の一覧
Set<String> keys = map.keySet();
Collection<Integer> values = map.values();

// なければ追加
map.putIfAbsent("田中", 100); // 田中がすでにいれば何もしない

// 計算
map.merge("田中", 10, Integer::sum); // 田中のスコアに10を加算

不変（イミュータブル）なコレクションを作る

Java 9以降、List.of() や Map.of() で変更不可のコレクションを作れます。

// 変更不可なList（Java 9以降）
List<String> immutableList = List.of("田中", "佐藤", "鈴木");
// immutableList.add("山田"); // UnsupportedOperationException!

// 変更不可なMap（Java 9以降）
Map<String, Integer> immutableMap = Map.of("田中", 85, "佐藤", 92);
// immutableMap.put("鈴木", 78); // UnsupportedOperationException!

// 変更可能なコレクションに変換したい場合
List<String> mutableList = new ArrayList<>(List.of("田中", "佐藤"));

使い分けのフローチャート

コレクションを選ぶとき
│
├─ キーと値のペアで管理したい
│      │
│      ├─ 順序不要・高速重視 → HashMap
│      ├─ 挿入順を保ちたい → LinkedHashMap
│      └─ キーをソートしたい → TreeMap
│
└─ 順番のあるリストで管理したい
       │
       ├─ 通常の用途（読み取り・末尾追加多め）→ ArrayList
       └─ 先頭・末尾の追加削除が超頻繁 → LinkedList

まとめ

List

  • ArrayList：インデックスアクセスや末尾操作が速い。迷ったらこれ
  • LinkedList：先頭・末尾の追加削除が速い。キュー・スタック用途に

Map

  • HashMap：高速検索。順序不要。迷ったらこれ
  • LinkedHashMap：挿入順を保持したいときに
  • TreeMap：キーをソートしたい・範囲検索したいときに

「とりあえず ArrayList と HashMap」でも問題ない場面がほとんどですが、データ量が多かったり特定の操作が頻繁だったりするときに、今回の知識が活きてきます。

13
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
13
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?