背景
Listはよく使う。Mapもなんとなく使える。でもSetは、「重複を排除したいときだけ使うやつ」という認識で止まっていた。
先日、コードレビューで「ここはSetの方が意図が明確では」とコメントをもらったのがきっかけで、改めてSetの設計思想から見直してみた。使い方は知っていても、なぜそう設計されているかを理解できていなかった、という感じの整理記録。
SetはMapの上に成り立っている
まず、これを知ったときに少し驚いた。
HashSetの内部実装は、実はHashMapをそのまま利用している。要素をMapのキーに保存し、値にはダミーのオブジェクトを入れることで「キーの重複を許容しない」というMapの性質を流用している。TreeSetはTreeMap、LinkedHashSetはLinkedHashMapを使っている。
Setを独立したデータ構造として捉えていたが、実際にはMapのラッパー的な存在だった。この事実を知ってから、Setの各実装の性質がMapと対応づけて理解できるようになった。
3つの実装クラスの使い分け
Setの主な実装は3つある。
HashSetは、内部でハッシュテーブルを使っているため、追加・検索・削除が高速。ただし、要素の順序は保証されない。順序を気にしない場合はこれが基本の選択肢になる。
TreeSetは、木構造（赤黒木）で管理されるため、要素が自然順（昇順）に並ぶ。Comparatorを渡すことでカスタムの並び順も指定できる。ソート済みの状態を常に保ちたいときに使う。
LinkedHashSetは、HashSetと同じ速度特性を持ちながら、挿入順を維持する。「重複は排除したいが、追加した順番は保持したい」という場面に向いている。
import java.util.HashSet;
import java.util.TreeSet;
import java.util.LinkedHashSet;
// 順序なし（HashSet）
HashSet<String> hashSet = new HashSet<>();
hashSet.add("banana");
hashSet.add("apple");
hashSet.add("cherry");
System.out.println(hashSet); // 順序は不定
// 昇順（TreeSet）
TreeSet<String> treeSet = new TreeSet<>();
treeSet.add("banana");
treeSet.add("apple");
treeSet.add("cherry");
System.out.println(treeSet); // [apple, banana, cherry]
// 挿入順（LinkedHashSet）
LinkedHashSet<String> linkedSet = new LinkedHashSet<>();
linkedSet.add("banana");
linkedSet.add("apple");
linkedSet.add("cherry");
System.out.println(linkedSet); // [banana, apple, cherry]
以前は「なんとなくHashSetを使っておけばいい」という判断をしていたが、順序の保証が必要かどうかをちゃんと考えてから選ぶべきだった、と今は思う。
ループの書き方：インデックス指定ができない
Listに慣れていると、インデックスを使ったfor文を書こうとして詰まることがある。Setはインデックスアクセスをサポートしていないので、拡張for文（for-each）かIterator、またはStreamを使う必要がある。
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.stream.Collectors;
HashSet<String> set = new HashSet<>();
set.add("apple");
set.add("banana");
set.add("orange");
set.add("mango");
set.add("kiwi");
// for-each
for (String element : set) {
System.out.println(element);
}
// Iterator
Iterator<String> ite = set.iterator();
while (ite.hasNext()) {
System.out.println(ite.next());
}
// Stream（絞り込みも組み合わせられる）
Set<String> filtered = set.stream()
.filter(x -> x.length() > 4)
.collect(Collectors.toSet());
System.out.println(filtered);
余談だが、collect(Collectors.toList())に慣れすぎていて、Streamの結果をSetに戻したいときにCollectors.toSet()の存在をしばらく忘れていた。Stream APIの前の記事でも書いたが、Collectorsのバリエーションはまだ意識的に使いこなせていない部分が多い。
理解が甘かった部分：containsの速度差
ListとSetのcontainsは同じメソッド名でも、計算量が異なる。
ArrayListのcontainsはリストを先頭から順に走査するため、O(n)の時間がかかる。一方、HashSetのcontainsはハッシュ値で直接位置を特定できるため、O(1)に近い。
「重複を排除したい」という目的でSetを選んでいたが、「多数の要素から特定の値が含まれるかを頻繁に確認する」という場面でも、Setの方が適切だということを意識できていなかった。コレクションの選択を「何を入れるか」だけで決めていたのを、「どんな操作を頻繁にするか」も含めて考えるようになったのは、この整理のおかげだと思っている。
HashSetのcontainsはO(1)に近いが、ハッシュ衝突が多発する状況では性能が劣化する場合がある。一般的なユースケースでは問題にならないが、キーのhashCode実装が偏っている場合は注意が必要。
整理して気づいたこと
今回はっきりしたのは以下の3点。
- SetはMapの実装を流用して成り立っており、実装クラスの選択もMapと同じ観点で判断できる
-
HashSet・TreeSet・LinkedHashSetの違いは「順序の保証」という軸で整理できる -
containsの計算量がListとSetで異なることを意識して、コレクションを使い分けるべきだった
まだ掘り切れていないのは、equalsとhashCodeのオーバーライドがSetの動作にどう影響するか、という部分。独自クラスをSetに入れるケースで、重複判定が意図通りに動かないことがあり、その原因がはっきり説明できていない。次に機会があれば、そこを重点的に確認したいと思っている。
この記事を書いた人について
株式会社Flexibilityでエンジニアをしています。
DX推進・システム開発を軸に、エンジニアが自律的に動ける環境を大事にしている会社です。
技術的に面白いことをやっていきたい方や、働き方に柔軟さを求めている方は、
よかったら一度のぞいてみてください。
- 会社サイト: https://www.flexi-inc.com/
- Qiita Organization: https://qiita.com/organizations/flexi-inc