Java HashSet: 重複しない値、メンバーシップ、集合演算

集合は重複しない値を格納する

HashSet（java.util から）は、それぞれの値を最大で1回だけ保持するコレクションです。HashMap のようにキーと値が対になることはなく、ただ異なる要素の入った袋があるだけです。その唯一の仕事は、ある問いに素早く答えることです:「これはこの中にありますか?」

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

public class Main {
    public static void main(String[] args) {
        Set<String> tags = new HashSet<>();
        tags.add("java");
        tags.add("backend");
        tags.add("java");   // 重複 - 無視される

        System.out.println(tags.contains("java"));     // true
        System.out.println(tags.contains("frontend")); // false
        System.out.println(tags.size());               // 2
    }
}

型パラメータは1つ、<ElementType> です。ArrayList や HashMap と同じく、変数の型は通常 Set インターフェースにして、HashSet を生成します。

add は値が新しかったかどうかを返す

add は値を格納するだけではありません。集合が実際に変化したかどうかを示す boolean を返します。すでに存在する値を追加すると false を返し、集合はそのまま変わりません。

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

public class Main {
    public static void main(String[] args) {
        Set<Integer> seen = new HashSet<>();

        System.out.println(seen.add(7));  // true  - 7 は新しかった
        System.out.println(seen.add(7));  // false - すでにある
        System.out.println(seen);
    }
}

この戻り値は本当に便利です。if (!seen.add(x)) { /* x は重複 */ } と書けば、処理を進めながら1行で重複を検出できます。

リストから重複を取り除く

集合は重複を拒否するので、コレクションを重複除去する最も速い方法は、それを集合に放り込むことです。HashSet のコンストラクタは、他の任意のコレクションを受け取ります:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>(List.of("Ada", "Boris", "Ada", "Chen", "Boris"));

        Set<String> unique = new HashSet<>(names);
        System.out.println(unique);          // 各名前を1回ずつ
        System.out.println(unique.size());   // 3

        // List に戻したい?
        List<String> deduped = new ArrayList<>(unique);
        System.out.println(deduped.size());  // 3
    }
}

これは初心者が集合に手を伸ばす最も一般的な理由です。ただし、この往復で元の順序が失われることだけは知っておいてください。順序が重要なら LinkedHashSet を使います（後述）。

contains、remove、size

日常的な操作は、他のコレクションのものと同じです:

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

public class Main {
    public static void main(String[] args) {
        Set<String> tags = new HashSet<>();
        tags.add("java");
        tags.add("backend");
        tags.add("api");

        System.out.println(tags.contains("api"));  // true
        System.out.println(tags.size());           // 3

        tags.remove("backend");
        System.out.println(tags.contains("backend")); // false

        tags.clear();
        System.out.println(tags.isEmpty());         // true
    }
}

ArrayList に対する大きな利点は contains です。リストは答えを出すために全要素をたどる必要があります（O(n)）。一方 HashSet はほぼ一直線に答えへ到達します（おおよそ O(1)）。ループの中で list.contains(...) を呼んでいる自分に気づいたら、たいていそれが集合に切り替える合図です。

集合演算: 和・積・差

集合は組み合わせるときに真価を発揮します。どれがどれかさえ分かれば、メソッドはほぼ普通の言葉のように読めます:

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

public class Main {
    public static void main(String[] args) {
        Set<Integer> a = new HashSet<>(Set.of(1, 2, 3, 4));
        Set<Integer> b = new HashSet<>(Set.of(3, 4, 5, 6));

        Set<Integer> union = new HashSet<>(a);
        union.addAll(b);            // どちらかの集合に含まれるすべて
        System.out.println(union);  // 1 2 3 4 5 6

        Set<Integer> intersection = new HashSet<>(a);
        intersection.retainAll(b);  // 両方に含まれるものだけ
        System.out.println(intersection); // 3 4

        Set<Integer> difference = new HashSet<>(a);
        difference.removeAll(b);    // a にあって b にないもの
        System.out.println(difference);   // 1 2
    }
}

重要な落とし穴: addAll、retainAll、removeAll は 呼び出した集合そのものを書き換えます。各例でまず a を新しい HashSet にコピーしているのはそのためです。さもないと元の集合を壊してしまいます。結果ごとに新しい集合を作りましょう。

HashSet は順序を保たない

HashMap と同様に、HashSet は反復順序を一切保証せず、実行ごとに順序が変わることもあります。予測可能性が必要なら:

• LinkedHashSet は挿入順、つまり要素を追加した順序を保ちます。
• TreeSet は要素を自然順序（または指定した Comparator）でソートして保ちます。

import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Set<String> insertion = new LinkedHashSet<>();
        insertion.add("gamma");
        insertion.add("alpha");
        insertion.add("beta");
        System.out.println(insertion);  // [gamma, alpha, beta]

        Set<String> sorted = new TreeSet<>(insertion);
        System.out.println(sorted);      // [alpha, beta, gamma]
    }
}

3つとも Set インターフェースを実装しているので、これらを切り替えるのはコンストラクタの1行を変えるだけです。

要素はハッシュ可能でなければならない

HashSet は内部で HashMap に支えられているので、同じルールが当てはまります。要素をハッシュ化して位置を特定するため、要素の hashCode() と equals() が整合していなければなりません。String や Integer のような組み込み型はすでにこれを正しく満たしており、だからこそ上で重複した "java" 文字列が正しくまとめられたのです。自作クラスのインスタンスを格納する場合は、equals と hashCode の両方をオーバーライドしてください。さもないと、意味上「等しい」2つのオブジェクトが別物として扱われ、contains や重複除去が静かに失敗します。

次へ: コレクションの反復処理

これで3つの主力コレクション - ArrayList、HashMap、HashSet - に出会いました。それぞれ少しずつ違う方法でたどることになり、微妙な落とし穴もあります（ループ中にコレクションを変更する、など）。次はそれらをまとめて、for-each ループ、イテレータ、forEach を使ってコレクションをきれいに反復処理する方法を扱います。