JavaのSetで重複を許さない仕組みとは？HashSetの内部構造を徹底解説

1. JavaのSetインターフェースと重複禁止の基本

1. JavaのSetインターフェースと重複禁止の基本

Javaのコレクションフレームワークにおいて、Setは非常に重要な役割を果たします。最大の特徴は「重複する要素を保持できない」という点です。これは、データベースの一意制約や、ユーザーIDの管理、アンケートの回答者の重複チェックなど、実務でも頻繁に利用される機能です。

代表的な実装クラスにはHashSet、LinkedHashSet、TreeSetなどがあります。初心者の方がまず覚えるべきはHashSetです。これは要素の順序を保証しない代わりに、高速な処理が可能というメリットがあります。重複要素を追加しようとした場合、プログラムは例外を投げるのではなく、単に追加処理を失敗（戻り値としてfalseを返す）させるだけで、元のデータは維持されます。

2. 重複要素を追加した時の実際の挙動を確認しよう

2. 重複要素を追加した時の実際の挙動を確認しよう

まずは、実際に同じ文字列を二度追加しようとしたときに、Javaのプログラムがどのように動くのかをコードで見てみましょう。このサンプルでは、プログラミング言語の名前をセットに格納していきます。

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

public class SetDuplicateExample {
    public static void main(String[] args) {
        Set<String> languages = new HashSet<>();

        // 要素の追加
        languages.add("Java");
        languages.add("Python");
        
        // 重複する要素「Java」を再度追加してみる
        boolean isAdded = languages.add("Java");

        System.out.println("3回目の追加に成功したか: " + isAdded);
        System.out.println("現在のセットの中身: " + languages);
        System.out.println("要素の数: " + languages.size());
    }
}

実行結果は以下のようになります。3回目の追加では、すでに「Java」が存在するため追加に失敗していることが分かります。

3回目の追加に成功したか: false
現在のセットの中身: [Java, Python]
要素の数: 2

3. 内部で活躍するhashCodeメソッドの役割

3. 内部で活躍するhashCodeメソッドの役割

なぜSetは一瞬で重複を見つけられるのでしょうか？その秘密は「ハッシュ値」にあります。JavaのすべてのオブジェクトはObjectクラスから継承したhashCode()メソッドを持っています。要素が追加されるとき、Setはこのハッシュ値を計算し、どこにデータを格納するかを決めます。

ハッシュ値とは、オブジェクトの情報を元に生成された「背番号」のような数値です。全く同じ内容のオブジェクトであれば、原則として同じハッシュ値を返します。Setはこの番号をインデックスとして利用するため、膨大なデータの中からでも一瞬で「同じ番号のデータが既にいないか」をチェックできるのです。これが、ArrayListのように端から順番に探すよりも圧倒的に速い理由です。

4. equalsメソッドによる最終確認のステップ

4. equalsメソッドによる最終確認のステップ

ハッシュ値が同じであれば即座に重複とみなされるわけではありません。実は、異なるデータでも偶然同じハッシュ値になってしまう「ハッシュ衝突」という現象が起こり得ます。そのため、Setは次の二段階で重複をチェックしています。

• ステップ1： hashCode()の結果を比較する。違えば別物と判断。
• ステップ2： ハッシュ値が同じ場合、equals()メソッドで内容を詳細に比較する。

この二重のチェックがあるおかげで、正確に重複を排除できるのです。自作のクラスをSetに入れたい場合は、この両方のメソッドを正しくオーバーライド（再定義）することが必須となります。片方だけでは、Setは正しく重複を判断できません。

5. 自作クラスをSetで扱う場合の注意点

5. 自作クラスをSetで扱う場合の注意点

初心者の方がよく躓くのが、自分で作ったクラス（UserクラスやItemクラスなど）をSetに入れた時に、中身が同じなのに重複とみなされないケースです。デフォルトでは、インスタンスの「メモリ上の住所」が異なれば別物と判定されてしまうからです。

以下のコードは、社員情報を管理するクラスで、IDが同じなら同一人物とみなすための実装例です。

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

class Employee {
    int id;
    String name;

    Employee(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee employee = (Employee) o;
        return id == employee.id;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }

    @Override
    public String toString() {
        return "Employee{id=" + id + ", name='" + name + "'}";
    }
}

public class CustomObjectSet {
    public static void main(String[] args) {
        Set<Employee> staff = new HashSet<>();
        staff.add(new Employee(101, "田中"));
        staff.add(new Employee(101, "佐藤")); // IDが同じなので重複とみなされる

        System.out.println("登録スタッフ数: " + staff.size());
        for (Employee e : staff) {
            System.out.println(e);
        }
    }
}

実行結果を確認すると、名前が違ってもIDが同じであれば同一とみなされ、佐藤さんは追加されていないことがわかります。

登録スタッフ数: 1
Employee{id=101, name='田中'}

6. HashSetの裏側ではHashMapが動いている？

6. HashSetの裏側ではHashMapが動いている？

驚くべきことに、JavaのHashSetのソースコードを覗いてみると、その内部ではHashMapが利用されています。HashSetに追加した要素は、実はHashMapの「キー」として保存されているのです。Mapのキーも重複が許されないという性質を持っているため、その機能をそのまま流用しているわけです。

HashMapの「値」の部分には、PRESENTと呼ばれるダミーのオブジェクトが共通して入れられています。このように、既存の完成された仕組みを再利用することで、信頼性の高いコレクション機能が提供されています。Javaの設計の美しさを感じる部分ですね。

7. 大量データを扱う時のSetのパフォーマンス

7. 大量データを扱う時のSetのパフォーマンス

リスト（ArrayList）とセット（HashSet）の最大の違いは、検索や重複チェックのスピードです。ArrayListで重複チェックをしようとすると、要素が1万個あれば最大1万回の比較が必要になりますが、HashSetであればハッシュ値を使ってほぼ一瞬で場所を特定できます。このため、データ量が増えれば増えるほど、Setの優位性が際立ってきます。

以下のコードは、数値の重複を排除する簡単な例です。ループ処理の中で頻繁に重複確認が必要な場合は、リストではなくセットを選択するのが鉄則です。

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

public class PerformanceTip {
    public static void main(String[] args) {
        List<Integer> sourceList = List.of(1, 2, 3, 1, 2, 4, 5);
        
        // リストから重複を取り除く最も簡単な方法
        Set<Integer> uniqueNumbers = new HashSet<>(sourceList);
        
        System.out.println("元のリスト: " + sourceList);
        System.out.println("重複排除後: " + uniqueNumbers);
    }
}

元のリスト: [1, 2, 3, 1, 2, 4, 5]
重複排除後: [1, 2, 3, 4, 5]

8. 順序を保持したい場合のLinkedHashSet

8. 順序を保持したい場合のLinkedHashSet

HashSetの弱点は、要素を取り出す際の順番がバラバラになることです。もし「重複はさせたくないけれど、追加した順番は守りたい」という要望があるなら、LinkedHashSetを使いましょう。これはハッシュテーブルと連結リストを組み合わせた構造になっており、重複禁止という特性を維持しつつ、順序性も保証してくれます。

使い方はHashSetと全く同じで、宣言するクラス名を変えるだけです。用途に合わせて適切なSetを選択できるようになると、中級者への道が開けてきます。

9. 重複チェックを応用した便利な使い方

9. 重複チェックを応用した便利な使い方

Setは単にデータを保存するだけでなく、ロジックの簡略化にも使えます。例えば「入力されたリストの中に重複があるかどうか」を判定したい場合、リストのサイズと、そのリストを元に作ったSetのサイズを比較するだけで、ループを回さずに一撃で判定が可能です。このように、データ構造の特性を理解することで、コードはよりシンプルで読みやすくなります。

JavaのSetは、モダンな開発において欠かせないツールです。内部での「ハッシュ値比較」と「equals比較」の二段構えを意識しながら、日々のコーディングに役立ててください。

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

public class CheckDuplicate {
    public static void main(String[] args) {
        List<String> inputs = Arrays.asList("りんご", "みかん", "りんご");
        
        Set<String> set = new HashSet<>(inputs);
        
        if (inputs.size() != set.size()) {
            System.out.println("重複が含まれています！");
        } else {
            System.out.println("すべてユニークな値です。");
        }
    }
}

重複が含まれています！