【Java】TreeSetの使い方（順序付けSet）

投稿日：2020年6月29日

TreeSetの使い方

基本的な使い方はHashSetと同じなので、以下を参照下さい。
【Java】HashSetの使い方いろいろ

TreeSetは何も指定せずにインスタンスを生成すると、Collections.sortによる順序付けがなされるSetです。
ここでは、他のSetとの違いと順序付けをどのように定義するかについて説明します。

HashSet、LinkedHashSetとの違い

Set（共通仕様）：重複をもたない値の集合
HashSet　　　：順序をもたないSet
LinkedHashSet ：挿入順を保持するSet
TreeSet　　　　：自然順序付けをもつSet。また独自の順序付けを定義可能。

TreeSetの自然順序付け

自然順序はCamparableインターフェースによって強制され、Collections.sortによる順序付けがなされます。
例えば、アルファベットを順不同で挿入しても、取り出すときは「A」から並んでいます。
数値であれば、小さい値（昇順）になっています。

これは降順にすることも可能です。
また、Comparatorを指定することで順序付けを独自に定義可能です。

実際にコードで確認します。

コードで確認

自然順序付け

PrintStream out = System.out;

// アルファベット

Set<String> alphaTree = new TreeSet<>();

alphaTree.add("B");

alphaTree.add("C");

alphaTree.add("A");

out.println("alphaTree : " + alphaTree);

// 数値

Set<Integer> numTree = new TreeSet<>();

numTree.add(new Integer(2));

numTree.add(new Integer(1));

numTree.add(new Integer(3));

out.println("numTree : " + numTree);

// 実行結果

alphaTree : [A, B, C]

numTree : [1, 2, 3]

アルファベットを「B→C→A」と挿入しても、取り出す際には「A→B→C」となっています。
また、数値も同様に「2→1→3」と挿入しても、「1→2→3」となっています。

降順

次は降順にする方法です。

PrintStream out = System.out;

// 降順

out.println("reverse alphaTree : " + alphaTree.stream()

.sorted(Comparator.reverseOrder())

.collect(Collectors.toList()));

out.println("reverse numTree : " + numTree.stream()

.sorted(Comparator.reverseOrder())

.collect(Collectors.toList()));

// 実行結果

reverse alphaTree : [C, B, A]

reverse numTree : [3, 2, 1]

streamは、Java SE 8から追加されたイテレーションの拡張APIです。
stream()で返されたコレクションに対し、sorted(Comparator.reverseOrder())で降順を指定します。
更に、collect(Collectors.toList())でソートした順のListにして返します。

Comparatorを指定

PrintStream out = System.out;

// Comparatorを指定（lengthのみ）

Comparator<String> lenComparator = Comparator.comparing(String::length);

Set<String> lenTree = new TreeSet<>(lenComparator);

lenTree.add("11");

lenTree.add("22");

lenTree.add("AAA");

lenTree.add("aaa");

lenTree.add("BBBB");

lenTree.add("bbbb");

out.println("lenTree : " + lenTree);

// Comparatorを指定（lengthとhashcode）

Comparator<String> comparator = Comparator.comparing(String::length)

.thenComparing(String::hashCode);

Set<String> lenHashTree = new TreeSet<>(comparator);

lenHashTree.add("11");

lenHashTree.add("22");

lenHashTree.add("AAA");

lenHashTree.add("aaa");

lenHashTree.add("BBBB");

lenHashTree.add("bbbb");

out.println("lenHashTree : " + lenHashTree);

// 事項結果

lenTree : [11, AAA, BBBB]

lenHashTree : [11, 22, AAA, aaa, BBBB, bbbb]

Comparatorを指定（lengthのみ）で定義した結果、「22」「aaa」「bbbb」は無くなっています。
これは格納される値がComparatorによって、length()だけで等価であるかを判断しているためです。
文字列長のみを判定基準にするため、「22」「aaa」「bbbb」は、
すでに格納済みの「11」「AAA」「BBBB」と等価と判断されたことで追加されませんでした。

＜Java Docからの引用＞
TreeSetインスタンスはそのcompareToメソッドまたはcompareメソッドを使用してすべての要素比較を実行するので、このメソッドによって等価と見なされる2つの要素は、セットの見地からすれば同じものです。
クラスTreeSet

Comparatorを指定（lengthとhashcode）のように、
hashcode()で文字列のハッシュ・コード値を算出する条件を追加すれば回避できます。
以下のように、ハッシュ・コード値は文字毎に異なる値を算出するからです。

PrintStream out = System.out;

out.println("AAA : " + "AAA".hashCode());

out.println("aaa : " + "aaa".hashCode());

// ハッシュコード値

AAA : 64545

aaa : 96321

TreeSetの使いどころ

順序付けを必要とするSet（重複のない集合）を扱いたい場合に有効と考えます。