Java Language
TreeMap и TreeSet

Вступление

TreeMap простого типа Java

Сначала мы создаем пустую карту и вставляем в нее некоторые элементы:

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 
}

TreeSet простого типа Java

Сначала мы создаем пустой набор и вставляем в него некоторые элементы:

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
}

TreeMap / TreeSet настраиваемого типа Java

Поскольку TreeMap s и 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):

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)

Чтобы исправить это, предположим, что мы хотим заказать экземпляры Person на основе порядка их идентификаторов ( private int id ). Мы могли бы сделать это одним из двух способов:

1. Одним из решений является изменение Person чтобы он реализовал интерфейс Comparable :

   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 компаратору :

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());
    }
});

Однако есть два оговорки к обоим подходам:

1. Очень важно не изменять какие-либо поля, используемые для упорядочения, как только экземпляр был вставлен в TreeSet / TreeMap . В приведенном выше примере, если мы изменим id человека, который уже вставлен в коллекцию, мы можем столкнуться с неожиданным поведением.

2. Важно правильно и последовательно выполнять сравнение. Согласно Джавадоку :

Разработчик должен обеспечить sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) для всех x и y. (Это означает, что x.compareTo(y) должен генерировать исключение, если y.compareTo(x) генерирует исключение).

Разработчик должен также гарантировать, что отношение транзитивно: (x.compareTo(y)>0 && y.compareTo(z)>0) подразумевает x.compareTo(z)>0 .

Наконец, разработчик должен убедиться, что x.compareTo(y)==0 означает, что sgn(x.compareTo(z)) == sgn(y.compareTo(z)) для всех z.

Безопасность 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 позволяет одновременно просматривать несколько потоков с карты.