Java Language
TreeMapとTreeSet

前書き

単純なJava型のTreeMap

まず、空のマップを作成し、いくつかの要素を挿入します。

TreeMap<Integer, String> treeMap = new TreeMap<>();

TreeMap<Integer, String> treeMap = new TreeMap<Integer, String>();

treeMap.put(10, "ten");
treeMap.put(4, "four");
treeMap.put(1, "one");
treeSet.put(12, "twelve");

マップにいくつかの要素があれば、いくつかの操作を実行できます：

System.out.println(treeMap.firstEntry()); // Prints 1=one
System.out.println(treeMap.lastEntry()); // Prints 12=twelve
System.out.println(treeMap.size()); // Prints 4, since there are 4 elemens in the map
System.out.println(treeMap.get(12)); // Prints twelve
System.out.println(treeMap.get(15)); // Prints null, since the key is not found in the map

また、Iteratorまたはforeachループのいずれかを使用してマップ要素を反復処理することもできます。エントリは、挿入順序ではなく、 自然順序付けに従って出力されることに注意してください。

for (Entry<Integer, String> entry : treeMap.entrySet()) {
    System.out.print(entry + " "); //prints 1=one 4=four 10=ten 12=twelve 
}

Iterator<Entry<Integer, String>> iter = treeMap.entrySet().iterator();
while (iter.hasNext()) {
    System.out.print(iter.next() + " "); //prints 1=one 4=four 10=ten 12=twelve 
}

単純なJava型のTreeSet

最初に、空のセットを作成し、いくつかの要素を挿入します。

TreeSet<Integer> treeSet = new TreeSet<>();

TreeSet<Integer> treeSet = new TreeSet<Integer>();

treeSet.add(10);
treeSet.add(4);
treeSet.add(1);
treeSet.add(12);

セット内にいくつかの要素があれば、いくつかの操作を実行できます：

System.out.println(treeSet.first()); // Prints 1
System.out.println(treeSet.last()); // Prints 12
System.out.println(treeSet.size()); // Prints 4, since there are 4 elemens in the set
System.out.println(treeSet.contains(12)); // Prints true
System.out.println(treeSet.contains(15)); // Prints false

また、Iteratorまたはforeachループのいずれかを使用してマップ要素を反復処理することもできます。エントリは、挿入順序ではなく、 自然順序付けに従って出力されることに注意してください。

for (Integer i : treeSet) {
    System.out.print(i + " "); //prints 1 4 10 12
}

Iterator<Integer> iter = treeSet.iterator();
while (iter.hasNext()) {
    System.out.print(iter.next() + " "); //prints 1 4 10 12
}

カスタムJava型のTreeMap / TreeSet

TreeMapとTreeSetは自然順序付けに従ってキー/要素を保持しているためしたがって、 TreeMapキーとTreeSet要素は、互いに匹敵する必要があります。

カスタムPersonクラスがあるとします。

public class Person  {

    private int id;
    private String firstName, lastName;
    private Date birthday;

    //... Constuctors, getters, setters and various methods
}

TreeSet （またはTreeMapのKey）にそのまま保存すると：

TreeSet<Person2> set = ...      
set.add(new Person(1,"first","last",Date.from(Instant.now())));

それから、このような例外に遭遇します：

Exception in thread "main" java.lang.ClassCastException: Person cannot be cast to java.lang.Comparable
    at java.util.TreeMap.compare(TreeMap.java:1294)
    at java.util.TreeMap.put(TreeMap.java:538)
    at java.util.TreeSet.add(TreeSet.java:255)

これを修正するために、ids（ private int id ）の順序に基づいてPersonインスタンスを注文したいと仮定しましょう。私たちは2つの方法のいずれかでそれを行うことができます：

1. 1つの解決策は、 Comparableインターフェイスを実装するようにPersonを変更することです。

   public class Person implements Comparable<Person> {
       private int id;
       private String firstName, lastName;
       private Date birthday;
   
       //... Constuctors, getters, setters and various methods
   
       @Override
       public int compareTo(Person o) {
           return Integer.compare(this.id, o.id); //Compare by id
       }
   }
   

2. もう一つの解決策は、 TreeSetにComparatorを提供することです：

TreeSet<Person> treeSet = new TreeSet<>((personA, personB) -> Integer.compare(personA.getId(), personB.getId()));

TreeSet<Person> treeSet = new TreeSet<>(new Comparator<Person>(){
    @Override
    public int compare(Person personA, Person personB) {
        return Integer.compare(personA.getId(), personB.getId());
    }
});

しかし、両方のアプローチには2つの注意点があります。

1. インスタンスがTreeSet / TreeMap挿入されると、順序付けに使用されるフィールドを変更しないことが非常に重要 TreeMap 。上記の例では、コレクションにすでに挿入されている人物のidを変更すると、予期しない動作が発生する可能性があります。

2. 比較を適切かつ一貫して実施することが重要です。 Javadocによると ：

実装者は、すべてのxとyに対してsgn(x.compareTo(y)) == -sgn(y.compareTo(x))を保証する必要があります。 （これは、 y.compareTo(x)が例外をスローする場合、 x.compareTo(y)が例外をスローする必要があることを意味します。

実装者は、関係が推移的であることを保証しなければならない。 (x.compareTo(y)>0 && y.compareTo(z)>0) x.compareTo(z)>0意味する。

最後に、実装者は、すべてのzに対して、 x.compareTo(y)==0がsgn(x.compareTo(z)) == sgn(y.compareTo(z))をx.compareTo(y)==0ことを保証する必要があります。

TreeMapとTreeSetスレッドの安全性

TreeMapとTreeSetはスレッドセーフなコレクションではないので、マルチスレッドプログラムで使用するときは注意が必要です。

TreeMapとTreeSetは、同時に複数のスレッドで読み込んだ場合でも安全です。したがって、それらが作成されて単一のスレッド（たとえば、プログラムの開始時に）によって読み込まれ、複数のスレッドによって読み取られ、変更されない場合、同期またはロックの理由はありません。

ただし、複数のスレッドが同時に読み取りまたは変更したり、複数のスレッドによって同時に変更された場合、コレクションはConcurrentModificationExceptionをスローしたり、予期しない動作をする可能性があります。このような場合は、次のいずれかの方法を使用して、コレクションへのアクセスを同期化/ロックすることが不可欠です。

1. Collections.synchronizedSorted..使用：

   SortedSet<Integer> set = Collections.synchronizedSortedSet(new TreeSet<Integer>());
   SortedMap<Integer,String> map = Collections.synchronizedSortedMap(new TreeMap<Integer,String>());
   

   これにより、実際のコレクションを基にしたSortedSet / SortedMap実装が提供され、一部のmutexオブジェクトで同期されます。これは、単一のロック上のコレクションへのすべての読み取りおよび書き込みアクセスを同期させるため、同時読み取りでさえ不可能であることに注意してください。

2. コレクション自体のように、一部のオブジェクトを手動で同期することによって：

    TreeSet<Integer> set = new TreeSet<>(); 
   

   ...

   //Thread 1
   synchronized (set) {
       set.add(4);
   }
   

   ...

   //Thread 2
   synchronized (set) {
       set.remove(5);
   }        
   

3. ReentrantReadWriteLockなどのロックを使用すると：

    TreeSet<Integer> set = new TreeSet<>(); 
    ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
   

   ...

    //Thread 1
    lock.writeLock().lock();
    set.add(4);
    lock.writeLock().unlock();
   

   ...

    //Thread 2
    lock.readLock().lock();
    set.contains(5);
    lock.readLock().unlock();
   

以前の同期方法とは対照的に、 ReadWriteLockを使用すると、複数のスレッドがマップから同時に読み取ることができます。