--- title: "【Java】TreeSetの使い方とHashSetとの違い｜並び順・範囲検索・自作クラス・速度を実行結果で解説" url: "https://www.issoh.co.jp/tech/details/4046/" published: 2024-11-05 updated: 2026-11-03 categories: ["Java"] publisher: "株式会社一創" --- # 【Java】TreeSetの使い方とHashSetとの違い｜並び順・範囲検索・自作クラス・速度を実行結果で解説 JavaのTreeSet（ツリーセット）は、重複しない要素を常にソート済みで保つ`java.util.Set`の実装です。HashSet（ハッシュセット）との違いは4点に絞れます。要素の並び順、基本操作の計算量、nullの扱い、そして「同じ要素」とみなす判定の仕方です。順序が要らないならHashSet、ソート済みで保ちたい、または「50以上で最小の値」のような範囲検索をしたいならTreeSetを選びます。追加した順を保ちたいときは第3の選択肢であるLinkedHashSetです。 この記事の実行結果は、すべてJava 25（Temurin 25.0.4.1）で実際にコンパイル・実行して得たものです。2026年11月時点の最新版はJava 27（2026-09-15 GA）、長期サポート（LTS）版はJava 25（2025-09-16 GA）で、ここで扱うAPIの挙動はJava 21以降で共通です。コード例はimport（`java.util.*`と`java.math.BigDecimal`）とmainメソッドの枠を省いた断片で、同じ変数名（`scores`など）は直前のコード例の続きとして実行しています。 ## まとめ：TreeSetの使い方とHashSetとの違い - **TreeSet**：常に昇順（またはComparatorの順）で並ぶ。基本操作はlog(n)が保証される。first・pollFirst・ceiling・subSetで両端や範囲を取り出せる。重複は**compareTo（またはcompare）の結果が0かどうか**で判定する。 - **HashSet**：順序は保証されない。add・remove・containsはハッシュが適切に分散していれば定数時間。nullを1つだけ入れられる。重複はequalsとhashCodeで判定する。 - **LinkedHashSet**：追加した順を保つ。性能はHashSetよりわずかに下がる程度。Java 21からaddFirstで先頭へ移動できる。 - 自作クラスを入れるときは、Comparatorの比較キーを**要素を区別できるところまで**並べる。年齢だけで比べると、同い年の2人目はaddがfalseを返して追加されない。 - 100万件のランダムな整数でadd＋containsを実測すると、HashSet約0.6秒に対しTreeSet約3.8秒。最後に1回並べるだけなら、**HashSetに集めてから並べ替える方が約2倍速かった**。 | 項目 | HashSet | LinkedHashSet | TreeSet | | ------------------- | --------------- | --------------- | ----------------- | | 内部構造 | HashMap | ハッシュ表＋双方向リスト | TreeMap（赤黒木） | | 反復の順序 | 保証なし | 追加した順 | ソート順 | | add・contains・remove | 定数時間（平均） | 定数時間（平均） | log(n)を保証 | | null | 1つまで可 | 1つまで可 | 自然順序では不可 | | 重複の判定 | equals・hashCode | equals・hashCode | compareTo・compare | | 範囲検索 | なし | なし | ceiling・subSetなど | | 主なインターフェース | Set | SequencedSet | NavigableSet | ## HashSet・LinkedHashSet・TreeSetの並び順を同じ入力で比較 3つの実装に同じリストを渡すと、重複の「apple」はどれも1件に減りますが、取り出される順番がそれぞれ違います。 ``` List in = List.of("banana", "apple", "cherry", "date", "apple"); System.out.println(new HashSet<>(in)); System.out.println(new LinkedHashSet<>(in)); System.out.println(new TreeSet<>(in)); ``` ``` [banana, date, apple, cherry] [banana, apple, cherry, date] [apple, banana, cherry, date] ``` HashSetの反復順序は、ハッシュ値やバケット数、挿入・削除の履歴に左右され、ソート順や追加順は保証されません。[HashSetのJavadoc](https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/HashSet.html)は「時間がたっても順序が一定であることも保証しない」と明記しています（`it does not guarantee that the order will remain constant over time`）。テストで`toString()`の結果を文字列比較していると、JDKの更新やデータ件数の変化で壊れる原因になります。 ## TreeSetの使い方：作成・取り出し・範囲検索 ### 自然順序とComparatorの指定 TreeSetの実体はTreeMapで、要素はComparableの自然順序か、コンストラクタで渡したComparatorの順に並びます。数値は小さい順、文字列は辞書順です。並び順を変えたいときは`new TreeSet<>(Comparator.reverseOrder())`のようにComparatorを渡します。Comparatorのラムダ式での書き方は[Javaラムダ式の使いどころ](/tech/details/2598/)で扱っています。今のTreeSetがどちらで並んでいるかは`comparator()`で確かめられ、自然順序ならnullが返ります。 ### first・last・pollFirst・pollLastによる両端の取り出し 最小と最大はfirstとlastで読み、pollFirstとpollLastは取り出すと同時に集合から削除します。予約枠の「次の空き」を順に払い出す処理は、pollFirstを繰り返すだけで書けます。 ``` TreeSet slots = new TreeSet<>(List.of(30, 10, 20, 40)); System.out.println(slots.first() + " " + slots.last()); System.out.println(slots.pollFirst() + " " + slots.pollLast() + " " + slots); TreeSet none = new TreeSet<>(); System.out.println(none.pollFirst() + " " + none.ceiling(1)); none.first(); ``` ``` 10 40 10 40 [20, 30] null null java.util.NoSuchElementException ``` 空のTreeSetで例外になるメソッドとnullを返すメソッドが混在しています。キューのように空になるまで回す処理では、firstでなくpollFirstを使い、nullで終わりを判定します。 | 空のTreeSetでの動作 | メソッド | | ---------------------- | -------------------------------------------------- | | NoSuchElementException | first・last・getFirst・getLast・removeFirst・removeLast | | nullを返す | pollFirst・pollLast・ceiling・floor・higher・lower | | 空のビューを返す | subSet・headSet・tailSet・descendingSet | getFirstとremoveFirstはJava 21でSequencedCollectionから入ったメソッドです。[TreeSetのJavadoc](https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/TreeSet.html)はpollFirstを「`Retrieves and removes the first (lowest) element, or returns null if this set is empty`」と説明しています。 ### ceiling・floor・subSetによる範囲検索 HashSetにできずTreeSetにできることの中心が、NavigableSetの範囲検索です。「指定値以上で最小」「指定値未満で最大」を、全件を走査せずlog(n)で求められます。 ``` TreeSet scores = new TreeSet<>(List.of(10, 25, 40, 55, 70, 85, 100)); System.out.println(scores.ceiling(50)); System.out.println(scores.floor(50)); System.out.println(scores.higher(55)); System.out.println(scores.lower(55)); System.out.println(scores.subSet(40, 85)); System.out.println(scores.subSet(40, true, 85, true)); System.out.println(scores.headSet(55)); System.out.println(scores.tailSet(55)); ``` ``` 55 40 70 40 [40, 55, 70] [40, 55, 70, 85] [10, 25, 40] [55, 70, 85, 100] ``` ceilingとfloorは指定値そのものを含み、higherとlowerは含みません。引数2つの`subSet(from, to)`は「from以上to未満」で、上端を含めたいときは4引数版で`true`を渡します。ceiling・floor・higher・lowerは該当がなければnullを返すため、戻り値はIntegerで受け、intに変換する前にnullを確認してください。 ### subSetはコピーでなく元の集合のビュー subSet・headSet・tailSetが返すのは、元のTreeSetと連動するビューです。元に足した要素がビューの範囲内ならビューにも現れ、ビューの範囲外の値をビュー経由で足そうとすると例外になります。 ``` NavigableSet view = scores.subSet(40, true, 85, true); scores.add(60); System.out.println(view); view.add(5); ``` ``` [40, 55, 60, 70, 85] java.lang.IllegalArgumentException: key out of range ``` 範囲を切り出して独立に加工したいなら、`new TreeSet<>(scores.subSet(40, true, 85, true))`のようにコピーを作ります。 ### descendingSetによる降順のビュー 昇順のTreeSetを作り直さずに降順でたどるには、`descendingSet()`で逆順のビューを取ります。ビューの上では「大きい・小さい」の向きも反転するため、higherの結果が昇順のときと逆になります。 ``` TreeSet asc = new TreeSet<>(List.of(10, 20, 30, 40)); NavigableSet desc = asc.descendingSet(); System.out.println(desc); System.out.println(asc.higher(20) + " " + desc.higher(20)); asc.add(50); System.out.println(desc); ``` ``` [40, 30, 20, 10] 30 10 [50, 40, 30, 20, 10] ``` descendingSetもビューなので、元に足した50がそのまま先頭に現れます。[NavigableSetのJavadoc](https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/NavigableSet.html)は昇順の操作の方が降順より速い見込みだと書いています（`The performance of ascending operations and views is likely to be faster than that of descending ones.`）。常に降順で使うなら、最初から`Comparator.reverseOrder()`で作る方が素直です。 ## 自作クラスをTreeSetに入れる：ComparableとComparatorの書き方 ### Comparableを実装しないとClassCastException Comparableを実装していないクラスを自然順序のTreeSetに入れると、最初の1件目の追加で例外が出ます。比較できない型をTreeSetが自然順序で扱おうとしてキャストに失敗するためです。 ``` java.lang.ClassCastException: class SetDemo$NoCmp cannot be cast to class java.lang.Comparable (SetDemo$NoCmp is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap') ``` 直し方は2通りです。クラス自身にComparableを実装して自然順序を持たせるか、TreeSetのコンストラクタにComparatorを渡します。並べ方が用途ごとに変わるなら（価格順の画面と書名順の画面がある等）、クラスを変えずに済むComparatorの方が向いています。Comparatorを差し替えて振る舞いを切り替える設計は[Strategyパターン](/tech/details/10265/)そのものです。 ### 比較キー不足による追加の拒否とthenComparingでの解消 TreeSetは比較結果が0の要素を重複とみなします。そのため、比較キーが要素を区別しきれないと、別人のデータが追加されずに黙って捨てられます。年齢だけで比べるComparableを持つ[record](/tech/details/3254/)で確かめます。 ``` record Member(String name, int age) implements Comparable { @Override public int compareTo(Member o) { return Integer.compare(age, o.age); } } TreeSet ms = new TreeSet<>(); System.out.println(ms.add(new Member("佐藤", 30))); System.out.println(ms.add(new Member("鈴木", 25))); System.out.println(ms.add(new Member("田中", 30))); System.out.println(ms); ``` ``` true true false [Member[name=鈴木, age=25], Member[name=佐藤, age=30]] ``` recordのequalsはnameとageの両方を比べるので、佐藤と田中はequalsではfalseです。それでもTreeSetはcompareToの0だけを見て、田中を追加しません。HashSetなら3件入ります。 直すには、主キーで同点になったときに比べる次のキーを`thenComparing`で足します。 ``` record Book(String title, int price) {} Comparator byPrice = Comparator.comparingInt(Book::price); TreeSet a = new TreeSet<>(byPrice); TreeSet b = new TreeSet<>(byPrice.thenComparing(Book::title)); for (Book bk : List.of(new Book("Java入門", 3000), new Book("Kotlin入門", 3000), new Book("SQL入門", 2500))) { a.add(bk); b.add(bk); } System.out.println(a.size() + " " + a); System.out.println(b.size() + " " + b); ``` ``` 2 [Book[title=SQL入門, price=2500], Book[title=Java入門, price=3000]] 3 [Book[title=SQL入門, price=2500], Book[title=Java入門, price=3000], Book[title=Kotlin入門, price=3000]] ``` 価格だけのComparatorでは、同じ3,000円のKotlin入門が追加されませんでした。目安は「equalsで比べるフィールドを、Comparatorでもすべて比べる」ことです。IDのように一意な値があるなら、最後のキーにIDを置けば取りこぼしません。 ### 引き算のComparatorのオーバーフローによる並び順の崩れ `(x, y) -> x - y`という書き方は、差がintの範囲を超えると符号が反転し、並び順が壊れます。 ``` Comparator bad = (x, y) -> x - y; TreeSet t1 = new TreeSet<>(bad); t1.addAll(List.of(-2_000_000_000, 0, 2_000_000_000)); System.out.println(t1); TreeSet t2 = new TreeSet<>(Integer::compare); t2.addAll(List.of(-2_000_000_000, 0, 2_000_000_000)); System.out.println(t2); ``` ``` [2000000000, -2000000000, 0] [-2000000000, 0, 2000000000] ``` 20億から-20億を引くと40億になり、intの上限（約21.4億）を超えて負の値になるため、20億が-20億より小さいと判定されました。数値の比較には`Integer.compare`か`Comparator.comparingInt`を使います。小さな値で試したテストでは見つからないのが厄介な点です。 ## TreeSetの重複判定：compareTo・Comparatorとequalsの違い 前の章で見たとおり、Setインターフェースは重複をequalsで定義していますが、TreeSetは要素の比較をすべてcompareTo（またはcompare）で行います。[Java 25のTreeSet公式API](https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/TreeSet.html)には、次のように記載されています。 > `a TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal.` ### BigDecimalの1.0と1.00はTreeSetでは1件 標準クラスでこれが起きる代表例がBigDecimalです。`1.0`と`1.00`は数値として等しいのでcompareToは0を返しますが、スケールが違うのでequalsはfalseです。 ``` List nums = List.of(new BigDecimal("1.0"), new BigDecimal("1.00")); System.out.println(new HashSet<>(nums).size()); System.out.println(new TreeSet<>(nums).size() + " " + new TreeSet<>(nums)); ``` ``` 2 1 [1.0] ``` 同じデータをHashSetからTreeSetに移しただけで件数が変わります。金額の集計で「重複排除した件数」を数えている処理をTreeSetに置き換えると、結果が静かに変わります。 この性質は意図して使うこともできます。`String.CASE_INSENSITIVE_ORDER`を渡せば、大文字小文字を区別しない集合になります。ただし比較順序がequalsと一致しないTreeSetはSetの一般契約を満たさないため、ほかのSetとのequals比較や集合演算では結果が直感とずれます。 ``` TreeSet ci = new TreeSet<>(String.CASE_INSENSITIVE_ORDER); ci.addAll(List.of("Java", "JAVA", "java", "Kotlin")); System.out.println(ci + " contains(\"jAvA\")=" + ci.contains("jAvA")); ``` ``` [Java, Kotlin] contains("jAvA")=true ``` 最初に追加した「Java」だけが残り、後の2件はaddがfalseを返して捨てられます。 ### コピーするとComparatorが外れる：コンストラクタの選ばれ方 Comparator付きのTreeSetをコピーするとき、引数の**変数の型**によって呼ばれるコンストラクタが変わり、Comparatorが引き継がれない場合があります。 ``` TreeSet ci = new TreeSet<>(String.CASE_INSENSITIVE_ORDER); ci.addAll(List.of("Java", "Kotlin")); Set asSet = ci; TreeSet c1 = new TreeSet<>(ci); TreeSet c2 = new TreeSet<>(asSet); System.out.println(c1.contains("JAVA") + " " + (c1.comparator() != null)); System.out.println(c2.contains("JAVA") + " " + (c2.comparator() != null)); ``` ``` true true false false ``` 中身は同じオブジェクトでも、変数の型がTreeSet（SortedSetの一種）なら`TreeSet(SortedSet)`が選ばれ、Javadocのとおり「`using the same ordering as the specified sorted set`」でComparatorを引き継ぎます。SetやCollection型の変数を渡すと`TreeSet(Collection)`が選ばれ、「`sorted according to the natural ordering of its elements`」で自然順序に戻ります。メソッドの引数を`Set`で受けてからコピーするコードで起きやすいので、Comparatorを保ちたいなら`new TreeSet<>(cmp)`で作ってから`addAll`するのが確実です。 ## HashSetとは：ハッシュセットの仕組みと使い方 ### 内部はHashMap：初期容量16・負荷係数0.75とツリー化 HashSetの実体はHashMapで、要素をキーとして格納しています。引数なしのコンストラクタは初期容量16・負荷係数0.75で作られ、要素数が容量×0.75を超えると表を拡張します。`new HashSet<>(1000)`の引数は容量であって件数ではないため、1000件入れる途中で拡張が起きます。件数がわかっているなら、Java 19で追加された`HashSet.newHashSet(int)`に件数を渡すと拡張なしで収まる容量を確保できます。 同じバケットに要素が集中したときの対策もあります。HashMapのソースでは、すでに8個の要素があるバケットに9個目を追加したとき（判定の定数は`TREEIFY_THRESHOLD = 8`）、表の容量が64（`MIN_TREEIFY_CAPACITY = 64`）以上なら、そのバケットを連結リストから木構造に切り替えます。容量が64未満なら木にせず表を拡張します。hashCodeが偏っていても極端な劣化を抑える仕組みです。全要素をたどる時間は「要素数＋バケット数」に比例するため、初期容量を大きく取りすぎると反復が遅くなる点にも注意します。 ### add・contains・removeの基本と重複除去 ``` Set tags = new HashSet<>(); System.out.println(tags.add("java")); System.out.println(tags.add("java")); System.out.println(tags.contains("java")); tags.remove("java"); System.out.println(tags.isEmpty()); // 重複を除きつつ元の順番を残すならLinkedHashSet List dup = List.of(3, 1, 3, 2, 1); System.out.println(new ArrayList<>(new LinkedHashSet<>(dup))); ``` ``` true false true true [3, 1, 2] ``` addは、追加できたらtrue、すでにあればfalseを返します。「初めて見た値だけ処理する」ループでは、`if (seen.add(x))`と書けばcontainsとaddの2回の検索を1回で済ませられます。 ### HashSet追加後のhashCode変更による検索不整合 equalsとhashCodeに使うフィールドを、HashSetに入れた後で書き換えると、containsやremoveでその要素を見つけられなくなることがあります。Setのjavadocも、要素の値がequalsの比較に影響する形で変わった場合の動作は規定されていないと注意しています。 ``` class Point { int x, y; Point(int x, int y) { this.x = x; this.y = y; } @Override public boolean equals(Object o) { return o instanceof Point p && p.x == x && p.y == y; } @Override public int hashCode() { return java.util.Objects.hash(x, y); } } HashSet ps = new HashSet<>(); Point p = new Point(1, 2); ps.add(p); // hashCodeの計算に使うフィールドを書き換える p.x = 99; System.out.println(ps.contains(p)); System.out.println(ps.size()); ``` ``` false 1 ``` 要素は1件残っているのに、containsでもremoveでも届きません。Setの要素には不変のクラスを使うのが安全です。recordもフィールドは再代入できませんが、参照先のListなどは変更できるため、equalsとhashCodeに影響する状態を変えない設計（防御的コピーなど）が必要です。TreeSetでも、比較に使うフィールドを入れた後に書き換えると同じように要素を見失います。 ## TreeSetとHashSetの速度の違い：100万件で実測 HashSetの公式APIは基本操作を「ハッシュ関数が要素をバケットに適切に分散させる前提で定数時間」、TreeSetの公式APIは「log(n)の時間を保証」と書いています。比較回数を数えるComparatorで、0〜999,999を昇順に入れたTreeSetに`new Random(42)`で選んだ値で10万回containsした平均を測ると、次のとおりlog2(100万)≒19.9とほぼ一致しました。 ``` TreeSet n=1000000 contains: avg compare calls=19.33 (log2 n=19.93) ``` 次に、ランダムな整数100万件をaddしてから全件containsする処理の時間を比べました。JMHを使わない単純計測で、7回のうち最初の2回をウォームアップとして除いた5回の中央値です（Java 25.0.4.1、Intel Core i9-9880H、`-Xms2g -Xmx2g`、入力は`new Random(1)`で生成、2026-11-03計測）。 | 実装 | add＋contains 100万件（中央値） | HashSet比 | | ------------- | ----------------------- | -------- | | HashSet | 591ミリ秒 | 1.0倍 | | LinkedHashSet | 717ミリ秒 | 約1.2倍 | | TreeSet | 3,813ミリ秒 | 約6.5倍 | 計測値は環境と実行ごとにぶれるため、倍率は目安です。差が出る主な理由は、TreeSetが木を根からたどるたびにcompareToを繰り返し（上の計測ではcontains1回あたり平均約19回）、節点ごとにメモリ上の離れた場所を参照することです。自分のデータで厳密に比べるなら、ウォームアップやデッドコード除去を制御できるJMHを使います（[マイクロベンチマークの正しい測り方](/tech/details/8711/)）。 ### 最終出力時のソート：HashSet経由とTreeSet経由の比較 「重複を除いて、最後にソート済みで出力したい」場合、ランダムな整数100万件の計測では、TreeSetに1件ずつ入れるより、HashSetに集めて最後に1回並べ替える方が速くなりました。 ``` // A: HashSetに集めてから1回だけ並べ替える List sorted = new ArrayList<>(new HashSet<>(data)); Collections.sort(sorted); // B: TreeSetに1件ずつ入れる TreeSet ts = new TreeSet<>(); for (Integer v : data) ts.add(v); List sortedFromTree = new ArrayList<>(ts); ``` 7回の実行でAは1,037〜1,492ミリ秒、Bは2,649〜2,836ミリ秒でした。TreeSetが本当に必要になるのは、**追加と削除を繰り返しながら、途中で何度も最小値・最大値・範囲を問い合わせる**場合です。優先度の変わるタスク一覧や、時刻順に並ぶ予約枠の「次の空き」を探す処理が該当します。優先度のように比較に使う値を変えるときは、集合に入れたまま書き換えず、いったんremoveしてから新しい値の要素をaddし直します。 ## nullの扱い：HashSetは1つまで・TreeSetはComparator次第 HashSetとLinkedHashSetはnullを1つだけ保持できます。2回addしても1件です。TreeSetは自然順序だとnullとの比較ができず、1件目でも例外になります。 ``` java.lang.NullPointerException: Cannot invoke "java.lang.Comparable.compareTo(Object)" because "k1" is null ``` ただし「TreeSetはnullを絶対に入れられない」わけではありません。nullを扱えるComparatorを渡せば入ります。 ``` TreeSet nf = new TreeSet<>(Comparator.nullsFirst(Comparator.naturalOrder())); nf.add("b"); nf.add(null); nf.add("a"); System.out.println(nf + " first=" + nf.first()); ``` ``` [null, a, b] first=null ``` この形にすると、ceilingやpollFirstの戻り値のnullが「要素がnull」なのか「該当なし」なのか区別できなくなります。実務ではnullをSetに入れず、入口で除外する方が扱いやすくなります。 ## Java 19・21の追加API：newHashSetとSequencedSet Java 21の[JEP 431（Sequenced Collections）](https://openjdk.org/jeps/431)で、順序を持つコレクションの共通インターフェースとしてSequencedCollectionとSequencedSetが追加されました。LinkedHashSetはSequencedSetを実装し、TreeSetはSortedSetを通じてSequencedSetの一員になっています。HashSetは順序を持たないので対象外です。 ``` LinkedHashSet lhs = new LinkedHashSet<>(List.of("a", "b", "c")); lhs.addFirst("c"); System.out.println(lhs); lhs.addLast("a"); System.out.println(lhs + " reversed=" + lhs.reversed()); TreeSet ts = new TreeSet<>(List.of(3, 1, 2)); System.out.println(ts.reversed() + " getFirst=" + ts.getFirst() + " getLast=" + ts.getLast()); ts.addFirst(0); ``` ``` [c, a, b] [c, b, a] reversed=[a, b, c] [3, 2, 1] getFirst=1 getLast=3 java.lang.UnsupportedOperationException ``` LinkedHashSetでは、すでにある要素にaddFirstやaddLastを呼ぶと、その要素を先頭や末尾へ移動できます。普通のaddで入れ直しても順番は変わらない（Javadocの`encounter order is not affected if an element is re-inserted`）ので、「最近使った順」を作るならaddLastを使います。TreeSetの並び順は比較で決まるため、addFirstとaddLastは常にUnsupportedOperationExceptionを投げます。 容量の指定も変わりました。Java 19で`HashSet.newHashSet(int)`と`LinkedHashSet.newLinkedHashSet(int)`が追加され、期待する要素数を渡せば、負荷係数0.75を考慮した容量で作られます。Java 8や11のままのプロジェクトではaddFirstもnewHashSetも使えないため、[Java 8から25へ上げる手順](/column/details/2902/)を参考に移行を検討してください。 ## 複数スレッドでの利用と反復中の変更 HashSetもTreeSetも同期化されていません。複数スレッドから変更するなら、スレッドセーフな実装に切り替えます。 - 順序が不要：`ConcurrentHashMap.newKeySet()`で作るSet - ソート順と範囲検索が必要：`ConcurrentSkipListSet`（NavigableSetを実装し、ceilingなども使える） - 既存のSetを包むだけ：`Collections.synchronizedSet`／`Collections.synchronizedSortedSet`（反復時は利用側で同期が必要） 1スレッドでも、拡張for文で回しながらSet自身のremoveで要素を削除すると、多くの場合ConcurrentModificationExceptionになります。どちらの実装のイテレータもフェイルファストで、Iterator自身のremove以外による変更を検出して例外を投げるためです。 ``` HashSet cm = new HashSet<>(List.of(1, 2, 3, 4)); for (Integer i : cm) { if (i % 2 == 0) cm.remove(i); } ``` ``` java.util.ConcurrentModificationException ``` 条件に合う要素を消すなら`cm.removeIf(i -> i % 2 == 0)`と書けば安全で、結果は`[1, 3]`になります。Javadocは、この例外は必ず投げられる保証がなく、バグ検出にだけ使うべきだと書いています。例外が出なかったから正しい、とは判断できません。 ## TreeSetとHashSetの使い分けの判断基準 迷ったら、次の順で当てはまるものを選びます。 1. **複数スレッドから変更する** → ConcurrentHashMap.newKeySet() か ConcurrentSkipListSet 2. **範囲検索や「次に大きい値」を繰り返し問い合わせる、小さい順に取り出しながら減らす** → TreeSet 3. **追加した順で出力したい、テストの出力を安定させたい** → LinkedHashSet 4. **要素がenumの定数だけ** → EnumSet（定義順に並ぶ） 5. **それ以外** → HashSet。ソート済みの出力が最後に1回必要なだけなら、HashSetに集めてから`stream().sorted()`かCollections.sortで並べる TreeSetを避けるべきなのは、要素の型のcompareToがequalsと一致しない場合（BigDecimal、大文字小文字を無視するComparator、一部のフィールドだけを比べる自作Comparator）で、しかも件数や重複の判定が業務上の意味を持つ処理です。この場合はHashSetで重複を判定し、並べ替えは別に行う方が安全です。 集合演算は3つの実装で同じ書き方です。`addAll`が和集合、`retainAll`が積集合、`removeAll`が差集合で、いずれも呼び出し元のSetを書き換えるので、元を残したいならコピーしてから呼びます。重複や並び順の要件は、[フルスクラッチ開発](/service/system/fullscratch/)なら設計段階で決めておくと、後からSetの実装を差し替える手戻りを避けられます。 ## TreeSetとHashSetに関するよくある質問 ### JavaのTreeSetとは何ですか？ `java.util.TreeSet`は、重複しない要素を自然順序かComparatorの順で常にソート済みに保つSetの実装です。内部はTreeMap（赤黒木）で、add・remove・containsはlog(n)が保証され、first・ceiling・subSetなどで最小値や範囲を取り出せます。 ### HashSet（ハッシュセット）とは何ですか？ Javaの`java.util.HashSet`は、要素の重複を許さない集合を、内部のHashMapで実装したクラスです。順序は保証されず、add・remove・containsはハッシュが適切に分散していれば定数時間で動きます。nullは1つだけ入れられます。 ### TreeSetとHashSetはどちらが速いですか？ 追加と検索は、ハッシュが適切に分散していればHashSetの方が速く、100万件のランダムな整数の実測では、TreeSetはHashSetの約6.5倍の時間がかかりました。TreeSetの1回の検索は、本文の計測（100万件）で平均約19回の比較でした。ソート順や範囲検索を繰り返す処理ではこの差を払う価値があり、最後に1回並べるだけならHashSetに集めてから並べ替えます。 ### TreeSetから値を取得するにはどうすればいいですか？ SetにはListの`get(int)`に当たるメソッドがありません。TreeSetなら`first()`・`last()`・`ceiling(x)`で、最小・最大・指定値以上の最小の要素を取り出せ、取り出して削除するなら`pollFirst()`を使います。添字で取りたい場合は`new ArrayList<>(set)`でListに変換します。 ### TreeSetにnullを追加できますか？ 自然順序のTreeSetにnullをaddするとNullPointerExceptionになります。`Comparator.nullsFirst(Comparator.naturalOrder())`のようにnullを扱えるComparatorを渡せば追加できますが、ceilingやpollFirstの戻り値のnullと区別できなくなるため、nullは入れない設計をおすすめします。 ## 関連記事 - [Javaのジェネリクスとは｜型パラメータTの書き方・extendsとsuperの使い分け・型消去の制約をJDK 25で実測](/tech/details/3252/) - [Javaのレコードクラス（record）とは？使い方・コンストラクタ・継承できない理由とエラー例をJava 25で実測](/tech/details/3254/) - [Javaラムダ式の使いどころ｜Stream APIで効く場面と避ける場面をJava 25で実測](/tech/details/2598/) - [オブジェクト指向とは？三本柱の実装手順とrecord・sealedまでJavaコードで解説](/tech/details/13412/) - [Javaヒープとは？既定サイズ・-Xmx設定と「Java heap space」エラーの対処をJDK 25で実測](/tech/details/3365/) --- 出典: [【Java】TreeSetの使い方とHashSetとの違い｜並び順・範囲検索・自作クラス・速度を実行結果で解説]()（株式会社一創）