Set で重複を排除｜コードで実践

Set で重複を排除とは

Java の Set を使って、コレクションから重複した要素を取り除く方法を学びます。HashSet と LinkedHashSet と TreeSet の違い、Set ならではの API を整理しよう。

Set とは ─ 重複を許さない集合

Java のコレクションフレームワークには大きく分けて 3 つの仲間がいます。順序を持つ List、キーと値のペアを管理する Map、そして今回学ぶ「重複を許さない集合」である Set です。List が「並んだ箱の列」なら、Set は「同じものを 2 個入れられない袋」と覚えるとイメージしやすいです。

例えば、アンケートに答えてくれたユーザー ID のリストを想像してみてください。[101, 102, 101, 103, 102, 104] のように、同じ ID が複数回現れることがあります。ここで知りたいのが「実際に何人が回答したか」だけなら、重複を除いた {101, 102, 103, 104} の 4 件がわかれば十分です。こういうときに活躍するのが Set です。

Set は「中身に何が入っているか」だけを管理し、「何回入れたか」「どの順番で入れたか」は基本的に気にしません。重複を意識せずに add してよい、というのは実装するうえで非常に楽です。

Set は数学の集合 (set) とほぼ同じ概念で、Set 同士を合体させる和集合、共通要素だけ残す積集合、片方から片方を引く差集合といった操作も addAll retainAll removeAll といったメソッドで素直に書けます。重複が許されない代わりに、こうした集合演算が得意というわけです。

「List か Set か迷ったら、要素の出現回数や順序が大事なら List、含まれているかどうかだけが大事なら Set を選ぶ」と覚えておくとほぼ外しません。

HashSet / LinkedHashSet / TreeSet の違い

Set は interface なので、実装クラスを選ぶ必要があります。代表的なのは 3 つで、それぞれ得意分野が違います。

HashSet — 最もよく使う実装。内部はハッシュテーブルで、追加・削除・検索が平均 O(1) と高速。ただし反復順序は保証されない
LinkedHashSet — HashSet に「挿入された順番」を覚える連結リストをくっつけたもの。速度は少し落ちるが、追加した順に取り出せる
TreeSet — 内部が Red-Black Tree (赤黒木) になっていて、要素が常にソートされた状態で保たれる。検索は O(log n)

用途の目安は次の通りです。ただ重複を排除したいだけなら HashSet、入れた順を保ちたいなら LinkedHashSet、ソート済みで取り出したいなら TreeSet を選びます。今回の課題では「重複しない要素数」を数えるだけなので HashSet が最適です。

diagram (will load when visible)

図のとおり、どの Set 実装に変換しても、要素そのものは 1, 2, 3 の 3 つにまとまります。違うのは「中での並び方」だけです。後で順序を活かしたくなったら LinkedHashSet や TreeSet に差し替えれば OK で、本体のロジックはほぼ変えなくて済みます。

add / contains / remove / size

Set で覚えるメソッドはとてもシンプルです。よく使う 4 つを並べると次のとおりです。

add(E e) — 要素を追加する。すでに含まれていれば何もせず false を返す。新しく追加できれば true
contains(Object o) — 含まれているか判定する。HashSet なら平均 O(1) で爆速
remove(Object o) — 要素を削除する。含まれていなければ false
size() — 現在の要素数を返す

コードで触ってみましょう。int を入れたいときは、Set<int> とは書けずラッパークラスの Integer を使います (int は基本型なのでジェネリクスに直接入れられない、というのが Java の制約です)。

Java

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

public class SetDemo {
    public static void main(String[] args) {
        Set<Integer> ids = new HashSet<>();
        ids.add(101);
        ids.add(102);
        ids.add(101); // 重複しているので無視される
        ids.add(103);

        System.out.println(ids.size());        // 3
        System.out.println(ids.contains(102)); // true
        ids.remove(102);
        System.out.println(ids.contains(102)); // false
    }
}

配列から重複を除いた個数を数える、という今回の課題で使うパターンは次の通りです。for で 1 件ずつ add していくだけで、Set が自動的に重複をはじいてくれます。

Java

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

public class Solution {
    public static int uniqueCount(int[] arr) {
        Set<Integer> seen = new HashSet<>();
        for (int n : arr) {
            seen.add(n);
        }
        return seen.size();
    }
}

空配列 [] を渡しても、for のループ自体が回らないので seen.size() は 0 になり、自然と正しく動きます。場合分けを書かなくて済むのも Set のいいところです。

List との違い

List と Set の違いを表で整理すると次の通りです。

重複の扱い — List は許す、Set は許さない
順序 — List は挿入順を保つ、HashSet は保たない
インデックスアクセス — List は get(i) で取れる、Set は取れない
検索 — List は O(n)、HashSet は平均 O(1)
主な用途 — List は並び順が大事なデータ、Set は集合演算や重複排除

「あるか / ないか」を頻繁にチェックするなら、たとえ重複が無いデータでも Set を選んだほうが速いです。List.contains は要素数に比例して遅くなりますが、HashSet.contains は要素数が増えてもほぼ一定の速さです。

よくある間違い

Set を使い始めたばかりの人がハマりがちな落とし穴を 3 つ紹介します。

HashSet の順序を期待してしまう — HashSet は要素の並びを保証しません。for で回したときの順番がプログラムを再起動したら変わる、ということも普通に起きます。順序が大事なら LinkedHashSet か TreeSet を使いましょう
equals / hashCode の実装を忘れる — 自作クラスを HashSet に入れるときは、equals と hashCode を両方ともオーバーライドする必要があります。片方だけだと「同じはずの 2 つが別物扱いされる」事故が起きます
null の扱いを誤解する — HashSet と LinkedHashSet は null を 1 個だけ入れられます。TreeSet は null を入れようとすると NullPointerException で落ちます。Set ならどれでも同じ、と思い込まないようにしましょう

自作クラスの equals だけ書いて hashCode を書き忘れる、というのは本当によくあるバグです。IDE の「自動生成」機能で必ずペアで作るクセを付けておくと安全です。

配列を Set に変える便利な書き方として Set.of(...) や new HashSet<>(Arrays.asList(arr)) もありますが、Set.of は不変 (immutable) な集合を作るので、あとから add しようとすると例外が出ます。「読むだけ」なら Set.of、「足したり消したり」したいなら new HashSet<>() と使い分けましょう。

やってみよう

それでは実際に今回の課題に挑戦してみましょう。

右側のエディタを開く
import java.util.HashSet; と import java.util.Set; を一番上に書く
uniqueCount メソッドの中で Set<Integer> を作って、for ループで配列の各要素を add する
最後に return seen.size(); する
「実行」ボタンを押して、テストが全部緑になることを確認する

動いたら、ぜひ HashSet を LinkedHashSet や TreeSet に置き換えても同じ結果になることを試してみてください。実装を切り替えても呼び出し側のコードが一切変わらない、というのが Java のコレクションフレームワークの美しい設計です。さらに余裕があれば、String[] を受け取るバージョンに書き換えてみたり、重複している要素そのものをリストアップする版を自作してみたりすると、Set への理解が一段深まります。

よくある質問

Q. set とリストはどう違いますか？

A. set は重複を持たない集合で、要素の追加と存在確認が O(1) と高速です。リストは順序付きで重複を許し、要素の前後関係が意味を持つ場面で使います。重複除去や「含まれているか」判定の高速化が必要なら set が圧倒的に有利です。

Q. set の順序は保証されますか？

A. set は順序が保証されません。順序を保ったまま重複を除去したい場合は dict.fromkeys(items) を使う（Python）か、Set + 配列の組み合わせで管理してください。順序付きで集合演算したい場面は意外と多いので覚えておくと便利です。

Q. set 同士の積集合・和集合はどう書きますか？

A. a & b で積集合、a | b で和集合、a - b で差集合になります。リスト同士の共通要素を求めたいときは set(a) & set(b) で O(n) に高速化できます。文字列もイテラブルなので set('abc') & set('bcd') → {'b', 'c'} のように使えます。

次のレッスン

次は Collections クラスの便利メソッド で、Collections クラスの便利メソッドを学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

Set の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. Set とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

Set で重複を排除