女性向けエンジニアスクール
3秒でわかる
ハッシュ表を使って重複のない集合を保つデータ構造。含まれるかどうかの判定が件数によらず速く、重複除去や既読の記録に向きます。
もう少し詳しく
どういうものか
HashSetは、値のハッシュ値を使って要素を格納する集合です。同じ値は1つしか保持せず、並び順は保証されません。追加、削除、含まれるかの判定がいずれも平均で O(1)、つまり要素が100万件あっても1件のときとほぼ同じ速さで終わります。Javaの java.util.HashSet、Pythonの set、JavaScriptの Set が同じ役割を担います。
なぜ必要か
配列に対する含まれるかの判定は、先頭から順に比べるので要素数に比例して遅くなります。1万件のリストに対して1万回の判定を行うと1億回の比較になり、体感できるほど待たされます。ハッシュ表は値そのものから格納位置を計算するため、比較の回数が件数に依存しません。重複の除去、既読の記録、参加者の名簿といった「あるかどうか」を何度も問う処理は、集合に置き換えるだけで実行時間が桁で変わります。
具体例
Set<String> visited = new HashSet<>();
for (String url : urls) {
if (!visited.add(url)) { // add は初回だけ true を返す
continue; // 2回目以降はスキップ
}
crawl(url);
}
Set<String> a = new HashSet<>(List.of("x", "y", "z"));
Set<String> b = new HashSet<>(List.of("y", "z", "w"));
a.retainAll(b); // 積集合 [y, z]つまずきやすいところ
自作クラスを入れるときは equals と hashCode の両方を実装する必要があります。片方だけだと、中身が同じオブジェクトが別物として2件入ってしまいます。この2つは必ず対で上書きします。次に多いのが、集合へ入れたあとに要素の中身を書き換える誤りです。ハッシュ値が変わってしまい、格納位置と計算結果がずれて、入れたはずの要素が見つからなくなります。集合に入れる値は変更しない前提で扱います。並び順が要るなら LinkedHashSet、整列した状態が要るなら TreeSet を選びます。
似た用語との違い
| 構造 | 特徴 |
|---|---|
| HashSet | 重複なし、順序なし、判定が平均 O(1) |
| LinkedHashSet | 挿入順を保つ集合 |
| TreeSet | 常に整列、操作は O(log n) |
| HashMap | キーに値を紐づける。集合はその値を捨てた形 |
順序を気にしないなら HashSet が最も速く、迷ったときの既定の選択肢になります。
