noyu38 資料置き場

Appearance

Java講座: データ構造(コレクションフレームワーク) ​

コレクションとは、「データの集合を表現する仕組み」のことです。プログラミング経験者にはデータ構造と呼んだほうがわかりやすいかもしれません。
Javaにおけるコレクションを操作するためのクラス/インターフェースのことをコレクションフレームワークと呼び、java.utilパッケージで提供されています。

「データの集合を表現する方法なら、配列があるじゃないか」と思った人もいるかもしれません。が、配列は機能がかなり限られており、状況に応じて柔軟に構造を操作することができません。例えば、配列は一度サイズを決めたらそれを後から変更することすらできません。
開発を行う際にデータの集合を操作したいと思ったら、まずはこのコレクションフレームワークを利用することを筆者はおすすめします。

代表的なコレクション ​

コレクションフレームワークの代表的なインターフェースとして、List、Set、Map、Queueがあります。しかし、これらはあくまでインターフェースであり、実装クラスは別にあります。 各インターフェースごとに複数の実装クラスが提供されていますが、よく使うのは以下の4つだと思います。

インターフェース実装クラス
ListArrayList
SetHashSet
MapHashMap
Queue (+ Stack )ArrayDeque

インターフェースについてはまだよくわからないと思いますが、実装するときには以下の構文にならって書けばOKです。

java
インターフェース型<要素型> 変数名 = new 実装クラス名<>();

例えば、String型の可変長配列を作りたいと思った場合にはこのように書きます。

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

コレクションの初期化時の注意点 ​

コレクションで扱える要素はラッパークラスのオブジェクトに限ります。
例えば、int型のArrayListを作りたいときにList<int> list = new ArrayList<>()と書くとエラーになります。このような場合にはintのラッパークラスであるIntegerを使い、List<Integer> list = new ArrayList<>()と書くようにしましょう。

ArrayList ​

ArrayListは可変長配列です。これまでに解説した普通の配列は一度初期化したらサイズの変更ができませんでしたが、ArrayListはデータの追加に合わせて自動的にサイズを変化させることができます。

ArrayListの操作 ​

以下のメソッドを用いることでArrayListの操作(要素の取得、追加、削除等)をすることができます。

メソッド概要
get(int index)index番目の要素を取得
getFirst()最初の要素を取得
getLast()最後の要素を取得
size()リストの要素数を取得
add([int index], E e)要素eをindex番目に追加(indexは省略可能。省略した場合、末尾に追加される)
addFirst(E e)先頭に要素を追加
addLast(E e)末尾に要素を追加
set(int index, E e)index番目の要素を書き換え
remove(int index)index番目の要素を削除
remove(Object o)指定した要素を削除
removeFirst()先頭の要素を削除
removeLast()末尾の要素を削除
clear()すべての要素を削除
contains(Object o)指定の要素を含むかどうか(返り値はboolean)
indexOf(Object o)指定の要素の位置を検索
isEmpty()リストが空か

サンプルプログラム ​

java
import java.util.List;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        
        List<String> shoppingList = new ArrayList<>();
        
        shoppingList.add("りんご");
        shoppingList.add("牛乳");
        shoppingList.add("パン");
        System.out.println("現在のリスト: " + shoppingList);
        
        System.out.println("全部で " + shoppingList.size() + " 個です。");
        
        for (int i = 0; i < shoppingList.size(); i++) {
            System.out.println(i + "番目: " + shoppingList.get(i));
        }
        
        shoppingList.set(1, "豆乳");
        System.out.println("牛乳を豆乳に変更しました: " + shoppingList);
        
        
        shoppingList.remove(0);
        System.out.println("りんごを削除しました: " + shoppingList);
        
        for (int i = 0; i < shoppingList.size(); i++) {
            System.out.println(i + "番目: " + shoppingList.get(i));
        }
    }
}

HashSet ​

HashSetは、数学の「集合」を扱うためのデータ構造です。最大の特徴は 「要素の重複を許さない」ことと、「要素の順番（追加した順番）が保証されない」 ことです。

例えば、大量のデータの中から「重複を省いた一覧を作りたい」場合や、「特定のデータがすでに存在するかを高速にチェックしたい」場面で役立ちます。

HashSetの操作 ​

Listと似ている部分も多いですが、インデックス（何番目か）を指定して取得・操作するメソッド（getなど）はありません。

メソッド概要
add(E e)要素を追加(すでに同じ要素が存在する場合はfalseを返す)
remove(Object o)指定した要素を削除
contains(Object o)指定の要素を含むかどうか
size()要素数を取得
isEmpty()集合が空か
clear()すべての要素を削除

サンプルプログラム ​

java
import java.util.Set;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        
        Set<String> names = new HashSet<>();
        
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");
        System.out.println("現在のセット: " + names);
        
        boolean isAdded = names.add("Alice"); // すでに存在するので追加されないはず
        System.out.println("Aliceは追加された？: " + isAdded);
        System.out.println("重複追加後のセット: " + names);
        
        if (names.contains("Bob")) {
            System.out.println("Bobはセットに含まれています。");
        }
        
        names.remove("Bob");
        System.out.println("Bob削除後のセット: " + names);
    }
}

HashMap ​

HashMapは、 キー（Key）と値（Value） のペアでデータを管理するデータ構造です。 「出席番号」と「生徒の名前」、「商品名」と「価格」など、何かを見出し（キー）にしてデータ（値）を保存・検索したい場合に使います。

理解が難しいかもしれないため詳しく解説します。例えば、ある生徒の情報を管理したい場合、配列で管理しようとしたらどうなるでしょう？
[18歳, 田中太朗, 静岡大学, 静岡県浜松市中央区〇〇町××-△]のようなリストで管理しても、どの要素がなんの情報なのかが分かりにくいです。

一方で、このように管理できたらどうでしょうか？

txt
[
    "年齢": "18歳",
    "氏名": "田中太朗",
    "大学名": "静岡大学",
    "住所": "静岡県浜松市中央区〇〇町××-△"
]

これはあくまでイメージなので実際には少し違いますが、年齢が18で、名前が田中太朗で⋯といったふうに管理できればわかりやすいですよね。このようなデータ構造を表現できるのがHashMapです。

なお、キーの重複は許されません（同じキーを追加すると、値が上書きされます）。

初期化する際は、キーと値それぞれの型を指定する必要があります。 例：Map<String, Integer> map = new HashMap<>();
（キーが文字列、値が整数）

HashMapの操作 ​

メソッド概要
put(K key, V value)キーと値のペアを追加(すでにキーが存在する場合は値を上書き)
get(Object key)指定したキーに対応する値を取得
remove(Object key)指定したキーとその値を削除
containsKey(Object key)指定したキーが存在するか
containsValue(Object value)指定した値が存在するか
keySet()登録されているすべてのキーをSetとして取得
values()登録されているすべての値をコレクションとして取得
entrySet()すべてのペアを取得
size()ペアの数を取得
clear()すべてのペアを削除

サンプルプログラム ​

java
import java.util.Map;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        
        Map<String, Integer> itemPrices = new HashMap<>();
        
        itemPrices.put("りんご", 150);
        itemPrices.put("バナナ", 100);
        itemPrices.put("みかん", 80);
        System.out.println("現在の価格表: " + itemPrices);
        
        System.out.println("りんごの価格は " + itemPrices.get("りんご") + " 円です。");
        
        itemPrices.put("バナナ", 120);
        System.out.println("バナナを値上げしました: " + itemPrices);
        
        if (itemPrices.containsKey("ぶどう")) {
            System.out.println("ぶどうは売っています。");
        } else {
            System.out.println("ぶどうは売っていません。");
        }
        
        for (String item : itemPrices.keySet()) {
            System.out.println(item + " : " + itemPrices.get(item) + "円");
        }
    }
}

ArrayDeque ​

ArrayDequeは、データの両端（先頭と末尾）に対して要素の追加や削除を効率的に行えるデータ構造（両端キュー：Deque）です。 キュー（先入れ先出し：FIFO）やスタック（後入れ先出し：LIFO） の振る舞いを実現したい場合に使用します。

  • キュー (Queue) のイメージ: レジの順番待ち。最初に並んだ人が最初に案内される。

  • スタック (Stack) のイメージ: 机に積んだ本や、ブラウザの「戻る」ボタン。最後に置いた（開いた）ものが最初に取り出される。

インターフェースはDequeを指定するのが一般的です。

ArrayDequeの操作 ​

用途に合わせて、使い分けるメソッドが異なります。

キュー（FIFO）として使う場合の代表的なメソッド

メソッド概要
offer(E e)末尾に要素を追加（順番待ちの列に並ぶ）
poll()先頭の要素を取得し、削除する（列の先頭の人が呼ばれて列から抜ける）
peek()先頭の要素を取得するが、削除はしない（列の先頭の人を確認する）

スタック（LIFO）として使う場合の代表的なメソッド

メソッド概要
push(E e)先頭に要素を追加（本を上に積む）
pop()先頭の要素を取得し、削除する（一番上の本を取る）
peek()先頭の要素を取得するが、削除はしない（一番上の本を確認する）

サンプルプログラム ​

java
import java.util.Deque;
import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) {
        
        Deque<String> queue = new ArrayDeque<>();
        
        queue.offer("Alice");
        queue.offer("Bob");
        queue.offer("Charlie");
        System.out.println("現在の列: " + queue);
        
        System.out.println("呼ばれた人: " + queue.poll());
        System.out.println("現在の列: " + queue);
        
        
        Deque<String> stack = new ArrayDeque<>();
        
        stack.push("1ページ目");
        stack.push("2ページ目");
        stack.push("3ページ目");
        System.out.println("現在の履歴: " + stack);
        System.out.println("先頭を削除します: " + stack.pop()); 
        System.out.println("現在の履歴: " + stack);
    }
}

問題を解いてみよう ​

Listが明確に利用できる問題は見つけられませんでした⋯

Set ​

https://atcoder.jp/contests/abc089/tasks/abc089_b
https://atcoder.jp/contests/abc073/tasks/abc073_c

Map ​

https://atcoder.jp/contests/abc231/tasks/abc231_b
https://atcoder.jp/contests/abc261/tasks/abc261_c

Deque ​

https://atcoder.jp/contests/abc043/tasks/abc043_b
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_az?lang=ja

余談 ​

ArrayListのソート ​

Collections.sort()メソッドでソートできます。

java
List<Integer> list = new ArrayList<>();
list.add(3);
list.add(1);
list.add(5);
list.add(4);
list.add(2);
Collections.sort(list);
System.out.println(list);
Collections.sort(list, Collections.reverseOrder()); // 降順にソート
System.out.println(list);

JavaのHashSetはソートされない ​

見出しのとおりです。JavaのHashSetは要素の追加・削除時にソートが行われません。HashSetは内部的にはハッシュ化によってデータを保存しているためです。そのため、要素の追加・削除・検索を $O(1)$ で処理可能です。バカ速いってことだけ理解できればOKです。C++ のunordered_setと同じですね。

しかしこれだけでは不便なので、ソートを自動で行ってくれるTreeSetも用意されています。こちらは二分木構造(実際には赤黒木構造)で実装されています。C++ のsetと一緒ですね。こちらは要素の追加・削除・検索に $O(logn)$ かかります。

また、値の追加順序が保持されるLinkedHashSetというクラスもありますが、まあいいでしょう。

JavaのHashMapのキーはソートされない ​

Setと一緒です。キーでソートしてほしかったらTreeMapを使用しましょう。

あとついでに、Javaには C++ におけるmultisetが標準で存在しません。TreeMapを使って代用するか、Googleが提供しているGuavaという外部ライブラリのTreeMultiSetを使用してください。

優先度付きキュー ​

PriorityQueueは優先度が付与されたキューです。この説明ではわかりにくいかもしれませんが、要は要素の追加・削除時に自動で要素がソートされるキューです。

しかし、ここで競プロerは気をつけてください！JavaのPriorityQueueのデフォルト実装は最小ヒープです。つまりデフォルトで昇順にソートされます。
降順にソートしてほしい場合は、Queue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder())のように宣言してください。(java.util.Collectionsのインポートが必要です)

型推論 ​

Javaには型推論といった機能があり、varという修飾子を使うことで初期化時の型宣言をサボることができます。詳しくはこのページを見るとわかりやすいと思います。

これを利用すると、コレクションの初期化サボることが可能です。例えば

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

と書いていたプログラムは、varを使うと

java
var list = new ArrayList<String>();

と書けます。しかし、この書き方をする場合には、右辺の<>の中に必ず扱いたいデータの型を書くようにしてください。