Java コレクションアルゴリズム

Java コレクションアルゴリズムとは、java.util.CollectionsCollections クラスが提供する一連の静的メソッドで、コレクション（List、Set、Map など）に対してソート、検索、シャッフル、塗りつぶしなどの一般的な操作を実行するために使われます。

これらのアルゴリズムは JDK に組み込まれて実装されており、高度に最適化されているため、開発者はゼロから書く必要がなく、直接呼び出すだけで済みます。

Collections アルゴリズム概要

java.util.CollectionsCollections はツールクラスであり、すべてのメソッドが static です。配列を操作する Arrays ツールクラスに似ています。

次の表は、最もよく使われるコレクションアルゴリズムとその用途を示しています。

アルゴリズム分類メソッド名機能説明
ソートsort()List を昇順にソートする
シャッフルshuffle()List 内の要素の順序をランダムにシャッフルする
反転reverse()List 内の要素の順序を反転する
二分探索binarySearch()ソート済み List 内で指定された要素を二分探索する
塗りつぶし（フィル）fill()指定された要素で List 内のすべての要素を置き換える
コピーcopy()ある List の要素を別の List にコピーする
最大/最小値max() / min()コレクション内の最大または最小要素を返す
出現回数のカウントfrequency()指定された要素がコレクション内に出現する回数を返す
非交差の判定disjoint()2つのコレクションに共通要素があるかどうかを判定する
不変コレクションunmodifiableXxx()コレクションの読み取り専用ビューを返す
スレッドセーフsynchronizedXxx()スレッドセーフなコレクションのラッパーを返す

ソート（Sorting）

Collections.sort()最もよく使われるコレクションアルゴリズムで、List 内の要素を昇順に並べます。

内部では最適化されたマージソート（TimSort）を使用しており、時間計算量は O(n log n) で、性能は安定しています。

ソートの流れを次の図に示します。

入力 元のリスト 5 2 8 1 9 矢印 sort() 出力 ソート後のリスト 1 2 5 8 9 カスタムソート カスタムソート方法 自然順序 Comparable インターフェース カスタム比較器 Comparator インターフェース 逆順ソート Comparator.reverseOrder()

自然順序ソート

要素クラスがComparableインターフェースを実装すると、sort() を直接呼び出して自然順序で並べることができます。

例

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

public class SortExample {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>();
        names.add("サンプル");
        names.add("サンプル");
        names.add("apple");
        names.add("banana");

        System.out.println("ソート前: " + names);

        // 自然順序ソート（Unicode コードポイント順）
        Collections.sort(names);

        System.out.println("ソート後: " + names);
    }
}

出力結果：

排序前: [サンプル, サンプル, apple, banana]
排序后: [サンプル, apple, banana, サンプル]

カスタム Comparator ソート

Comparator を使うとComparator任意のカスタムルールでソートでき、要素クラス自体を変更する必要はありません。

例：文字列の長さでソート

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class CustomSortExample {
    public static void main(String[] args) {
        List<String> words = new ArrayList<>();
        words.add("サンプル");
        words.add("java");
        words.add("algorithm");
        words.add("C");

        System.out.println("ソート前: " + words);

        // 文字列の長さの昇順でソート
        Collections.sort(words, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return s1.length() - s2.length();
            }
        });

        System.out.println("長さでソート後: " + words);
    }
}

出力結果：

排序前: [サンプル, java, algorithm, C]
按长度排序后: [C, java, サンプル, algorithm]

Java 8+ では Lambda 式を使って簡潔に書けます：

例：Lambda 記法

// Lambda 式で長さ順にソート
Collections.sort(words, (s1, s2) -> s1.length() - s2.length());

// または Comparator.comparingInt を使用
Collections.sort(words, Comparator.comparingInt(String::length));

// 逆順ソート
Collections.sort(words, Comparator.reverseOrder());

// 長さで逆順にソート
Collections.sort(words, Comparator.comparingInt(String::length).reversed());

シャッフル（Shuffling）

Collections.shuffle()Fisher-Yates アルゴリズムを使用して、List 内の要素の順序をランダムにシャッフルします。

元のリスト A B C D shuffle() シャッフル後（ランダム） C D A B ? ? ? 説明 実行ごとに結果が異なります 固定シード shuffle(list, new Random(42)) のように固定シードを渡すと、シャッフル結果を再現できます

例

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

public class ShuffleExample {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        for (int i = 1; i <= 10; i++) {
            numbers.add(i);
        }

        System.out.println("元のリスト: " + numbers);

        // ランダムに順序をシャッフル
        Collections.shuffle(numbers);
        System.out.println("1回目のシャッフル: " + numbers);

        Collections.shuffle(numbers);
        System.out.println("2回目のシャッフル: " + numbers);
    }
}

出力結果：

原始列表: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
第一次混排: [7, 3, 9, 1, 5, 10, 8, 2, 4, 6]
第二次混排: [4, 10, 1, 8, 6, 3, 2, 9, 5, 7]

二分探索（Binary Search）

Collections.binarySearch()ソート済み List 内で二分探索アルゴリズムを使用して目的の要素を特定します。

時間計算量は O(log n) で、線形走査の O(n) よりはるかに優れています。

重要な前提：List が昇順にソート済みである必要があります。そうでないと結果は不定です。

例

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

public class BinarySearchExample {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        numbers.add(10);
        numbers.add(30);
        numbers.add(20);
        numbers.add(50);
        numbers.add(40);

        // 事前にソートが必要
        Collections.sort(numbers);
        System.out.println("ソート後のリスト: " + numbers);

        // 二分探索：戻り値はインデックス（>= 0 なら見つかった）
        int index = Collections.binarySearch(numbers, 30);
        System.out.println("30 のインデックス位置: " + index);

        // 存在しない要素を探すと：戻り値は負の値 = -(挿入ポイント) - 1
        int notFound = Collections.binarySearch(numbers, 25);
        System.out.println(25 の戻り値（存在しない）: + notFound);
        // 挿入ポイント = -(notFound + 1) = 2、インデックス 2 に挿入すべき
    }
}

出力結果：

排序后列表: [10, 20, 30, 40, 50]
30 的索引位置: 2
25 的返回值（不存在）: -3

binarySearch() は要素が見つからない場合、負の値を返します。その式は-(挿入ポイント) - 1挿入ポイントとは、その要素が存在する場合に配置されるべきインデックスです。この設計の巧妙な点は、要素が存在すれば非負のインデックスを返し、存在しなければ必ず負の値を返すため、曖昧さが生じないことです。

最大値と最小値

Collections.max()とCollections.min()コレクション内から、自然順序または指定された比較器による最大/最小要素を返します。

例

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class MaxMinExample {
    public static void main(String[] args) {
        List<String> words = new ArrayList<>();
        words.add("サンプル");
        words.add("algorithm");
        words.add("java");
        words.add("code");

        // 自然順序（辞書順）で最大と最小を取得
        String maxWord = Collections.max(words);
        String minWord = Collections.min(words);
        System.out.println("辞書順で最大: " + maxWord);
        System.out.println("辞書順で最小: " + minWord);

        // 文字列の長さで最大と最小を取得
        String longest = Collections.max(words,
            Comparator.comparingInt(String::length));
        String shortest = Collections.min(words,
            Comparator.comparingInt(String::length));
        System.out.println("長さが最大: " + longest);
        System.out.println("長さが最小: " + shortest);
    }
}

出力結果：

字典序最大: サンプル
字典序最小: algorithm
长度最长: algorithm
长度最短: code

出現回数のカウントと非交差の判定

Collections.frequency()指定された要素がコレクション内に出現する回数をカウントします。

Collections.disjoint()2つのコレクションに共通要素がまったくないかどうかを判定します。

例

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

public class FrequencyDisjointExample {
    public static void main(String[] args) {
        List<String> items = new ArrayList<>();
        items.add("サンプル");
        items.add("java");
        items.add("サンプル");
        items.add("python");
        items.add("サンプル");

        // "サンプル" の出現回数をカウント
        int count = Collections.frequency(items, "サンプル");
        System.out.println("\"サンプル\""出現回数: " + count);

        // 2つのコレクションが非交差かどうかを判定
        List<String> groupA = new ArrayList<>();
        groupA.add("java");
        groupA.add("python");

        List<String> groupB = new ArrayList<>();
        groupB.add("C++");
        groupB.add("go");

        boolean noCommon = Collections.disjoint(groupA, groupB);
        System.out.println("groupA と groupB は非交差: " + noCommon);
    }
}

出力結果：

"サンプル" 出现次数: 3
groupA 与 groupB 不相交: true

不変コレクションとスレッドセーフなラッパー

Collections は、通常のコレクションを不変コレクションまたはスレッドセーフなコレクションにラップするメソッドを提供します。

不変コレクション（Unmodifiable）

呼び出すCollections.unmodifiableList()などのメソッドで読み取り専用ビューを作成できます。

変更操作を行うと UnsupportedOperationException がスローされます。

スレッドセーフ集合（Synchronized）

呼び出すCollections.synchronizedList()などのメソッドでスレッドセーフなラッパーを作成できます。

マルチスレッド環境では、これらのコレクションの単一メソッド呼び出しは安全ですが、複合操作には依然として外部同期が必要です。

例

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

public class WrapperExample {
    public static void main(String[] args) {
        List<String> original = new ArrayList<>();
        original.add("サンプル");
        original.add("java");

        // 不変ビューを作成
        List<String> readOnly = Collections.unmodifiableList(original);
        System.out.println("不変ビュー: " + readOnly);

        // readOnly.add("error"); // 実行すると例外がスローされる

        // 元のリストを変更すると、不変ビューにもその変更が反映される
        original.add("python");
        System.out.println("元のリスト変更後: " + readOnly);

        // スレッドセーフなラッパーを作成
        List<String> syncList = Collections.synchronizedList(
            new ArrayList<>());
        syncList.add("thread-safe");

        // 走査時は手動で同期する必要がある
        synchronized (syncList) {
            for (String item : syncList) {
                System.out.println(item);
            }
        }
    }
}

出力結果：

不可变视图: [サンプル, java]
原始修改后: [サンプル, java, python]
thread-safe

不変ビューはそのビューを介したコレクションの変更を防ぐだけで、元のコレクションは依然として変更可能です。本当に不変なコレクションが必要な場合は、Java 9+ のList.of()、Set.of()などのメソッドを使用します。

よく使うアルゴリズム操作一覧

以下に、Collections でよく使うアルゴリズムの呼び出し方と時間計算量をまとめます：

操作メソッド呼び出し時間計算量前提条件
ソートCollections.sort(list)O(n log n)要素が Comparable を実装している
カスタムソートCollections.sort(list, comp)O(n log n)Comparator を指定
反転Collections.reverse(list)O(n)无
シャッフルCollections.shuffle(list)O(n)无
二分探索Collections.binarySearch(list, key)O(log n)リストがソート済み
フィルCollections.fill(list, obj)O(n)无
コピーCollections.copy(dest, src)O(n)dest.size() >= src.size()
最大値Collections.max(coll)O(n)要素が Comparable を実装している
最小値Collections.min(coll)O(n)要素が Comparable を実装している
頻度のカウントCollections.frequency(coll, obj)O(n)无
要素の交換Collections.swap(list, i, j)O(1)インデックスが有効
ローテーションCollections.rotate(list, distance)O(n)无

注意事項

binarySearch() はソート済みのリストに対して呼び出す必要があります。ソートされていないリストの戻り値は未定義です。リストに重複する要素が含まれる場合、どれが見つかるかは保証されません。

synchronizedXxx() が返すラッパーは、単一のメソッド呼び出しレベルでのみ原子性を保証します。複合操作（例: if(!list.contains(x)) list.add(x)）には、引き続き外部の synchronized ブロックが必要です。

sort() と List.sort() の違い：

Java 8 以降、List インターフェースに sort(Comparator) デフォルトメソッドが追加されました。

list.sort(null) は自然順序でソートされ、Collections.sort(list) と同等です。

両者の基盤となる実装は同じですが、list.sort() の方が簡潔に記述できます。

性能比較のアドバイス：

データ量が少ない場合（100 要素未満）、各アルゴリズムの性能差は無視できる程度です。

データ量が多い場合、binarySearch() は indexOf() の線形探索よりもはるかに優れています。

頻繁に検索する必要がある場合は、List の代わりに HashSet の使用を検討してください。クエリの計算量は O(1) です。

その他の拡張