SetとHashSet

Setは重複のないコレクションです。このレッスンでは、Setの使用方法と重複排除の原則を学びます。

Setインターフェースの特徴

特徴	説明
順序なし	固定の順序がない（HashSet）
重複不可	自動的に重複を排除
インデックスなし	インデックスでアクセスできない

HashSet

HashSetはHashMapベースで、最も一般的に使用されるSet実装です。

HashSetの作成

JAVA

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

Set<String> set1 = new HashSet<>();
Set<String> set2 = new HashSet<>(100);  // 指定容量
Set<String> set3 = new HashSet<>(set1);  // 他のコレクションから作成

基本操作

JAVA

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

public class HashSetDemo {
    public static void main(String[] args) {
        Set<String> set = new HashSet<>();
        
        // 要素を追加
        set.add("Alice");
        set.add("Bob");
        set.add("Charlie");
        set.add("Alice");  // 重複、追加されない
        System.out.println("Set: " + set);  // [Alice, Bob, Charlie]（順序なし）
        
        // チェック
        System.out.println("サイズ: " + set.size());  // 3
        System.out.println("Aliceを含む: " + set.contains("Alice"));  // true
        System.out.println("空か: " + set.isEmpty());  // false
        
        // 削除
        set.remove("Bob");
        System.out.println("削除後: " + set);
        
        // 走査
        for (String name : set) {
            System.out.println(name);
        }
    }
}

重複排除の原則

HashSetはhashCodeとequalsを使用して要素が重複しているかどうかを判断します。

重複排除フロー

TEXT

1. 要素のhashCodeを計算
2. hashCodeが異なる → 重複ではない
3. hashCodeが同じ → equalsを呼び出し
4. equalsがtrueを返す → 重複
5. equalsがfalseを返す → 重複ではない（ハッシュ衝突）

例：カスタムオブジェクトの重複排除

JAVA

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

public class Student {
    private String name;
    private int age;
    
    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
    
    // hashCodeとequalsをオーバーライドする必要がある
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return age == student.age && Objects.equals(name, student.name);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
    
    @Override
    public String toString() {
        return name + "(" + age + ")";
    }
    
    public static void main(String[] args) {
        Set<Student> set = new HashSet<>();
        set.add(new Student("Alice", 20));
        set.add(new Student("Bob", 22));
        set.add(new Student("Alice", 20));  // 重複、追加されない
        
        System.out.println("サイズ: " + set.size());  // 2
        System.out.println("Set: " + set);
    }
}

▶ 試してみよう

⚠️ 重要: HashSetにカスタムオブジェクトを格納する場合、hashCodeとequalsメソッドをオーバーライドする必要があります。otherwise 重複排除が正しく機能しません。

TreeSet

TreeSetは赤黒木ベースで、要素が自動的にソートされます。

特徴

特徴	説明
順序あり	自然順序またはカスタム順序でソート
重複不可	自動的に重複を排除
インデックスなし	インデックスでアクセスできない

例：TreeSet

JAVA

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

public class TreeSetDemo {
    public static void main(String[] args) {
        // 自然順序
        Set<Integer> numbers = new TreeSet<>();
        numbers.add(3);
        numbers.add(1);
        numbers.add(4);
        numbers.add(1);  // 重複、追加されない
        numbers.add(5);
        System.out.println("順序付き集合: " + numbers);  // [1, 3, 4, 5]
        
        // 文字列の順序
        Set<String> names = new TreeSet<>();
        names.add("Charlie");
        names.add("Alice");
        names.add("Bob");
        System.out.println("順序付き名前: " + names);  // [Alice, Bob, Charlie]
    }
}

▶ 試してみよう

カスタム順序

JAVA

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

public class CustomSortDemo {
    public static void main(String[] args) {
        // 長さでソート
        Set<String> words = new TreeSet<>(Comparator.comparingInt(String::length));
        words.add("Hello");
        words.add("Hi");
        words.add("Java");
        words.add("Go");
        System.out.println("長さ順: " + words);  // [Go, Hi, Java, Hello]
    }
}

LinkedHashSet

LinkedHashSetは挿入順序を維持します。

特徴

特徴	説明
順序あり	挿入順に要素を格納
重複不可	自動的に重複を排除

例：LinkedHashSet

JAVA

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

public class LinkedHashSetDemo {
    public static void main(String[] args) {
        Set<String> set = new LinkedHashSet<>();
        set.add("Charlie");
        set.add("Alice");
        set.add("Bob");
        System.out.println("順序付き集合: " + set);  // [Charlie, Alice, Bob]
    }
}

▶ 試してみよう

集合演算

和集合

JAVA

Set<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3));
Set<Integer> set2 = new HashSet<>(Arrays.asList(3, 4, 5));

Set<Integer> union = new HashSet<>(set1);
union.addAll(set2);
System.out.println("和集合: " + union);  // [1, 2, 3, 4, 5]

積集合

JAVA

Set<Integer> intersection = new HashSet<>(set1);
intersection.retainAll(set2);
System.out.println("積集合: " + intersection);  // [3]

差集合

JAVA

Set<Integer> diff = new HashSet<>(set1);
diff.removeAll(set2);
System.out.println("差集合: " + diff);  // [1, 2]

Setの比較

特徴	HashSet	TreeSet	LinkedHashSet
順序	順序なし	ソート済み	挿入順
実装	HashMap	赤黒木	リンクリスト + HashMap
パフォーマンス	O(1)	O(log n)	O(1)
null	1つ許可	許可しない	1つ許可

選択ガイド

ニーズ	選択
順序を気にしない	HashSet
ソートが必要	TreeSet
挿入順序を維持	LinkedHashSet

例：重複排除の練習

JAVA

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

public class RemoveDuplicates {
    // 方法1：Setによる重複排除
    public static <T> List<T> removeDuplicates1(List<T> list) {
        return new ArrayList<>(new LinkedHashSet<>(list));
    }
    
    // 方法2：Streamによる重複排除
    public static <T> List<T> removeDuplicates2(List<T> list) {
        return list.stream().distinct().collect(Collectors.toList());
    }
    
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("Alice");
        list.add("Bob");
        list.add("Alice");
        list.add("Charlie");
        list.add("Bob");
        
        System.out.println("元のリスト: " + list);
        System.out.println("重複排除後: " + removeDuplicates1(list));
    }
}

❓ よくある質問

Q SetとListのどちらを選ぶべきですか？

A 重複排除が必要な場合はSetを使用し、順序付きで重複を許可する場合はListを使用します。

Q TreeSetのソートルールは？

A デフォルトは自然順序（Comparable）です。Comparatorでカスタマイズできます。

Q HashSetはなぜ高速なのですか？

A HashMapベースで、hashCodeを使用して直接検索し、O(1)の時間複雑度を持ちます。

📖 まとめ

Setは重複なし：HashSetは順序なし、TreeSetはソート済み、LinkedHashSetは挿入順を維持
重複排除はhashCodeとequalsメソッドに依存
集合演算：和集合（addAll）、積集合（retainAll）、差集合（removeAll）

📝 演習

重複排除: Listから重複を削除し、元の順序を維持
積集合: 2つのSetの積集合を見つける
ソート: TreeSetを使用して文字列を長さでソート

次のレッスン

次のレッスンでは、MapとHashMapを学びます — キーと値のペアコレクション。