Java Language
TreeMap i TreeSet

Wprowadzenie

TreeMap prostego typu Java

Najpierw tworzymy pustą mapę i wstawiamy do niej kilka elementów:

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");

Gdy mamy już kilka elementów na mapie, możemy wykonać kilka operacji:

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

Możemy również iterować elementy mapy za pomocą iteratora lub pętli foreach. Pamiętaj, że wpisy są drukowane zgodnie z ich naturalną kolejnością , a nie kolejnością wstawiania:

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 z prostego typu Java

Najpierw tworzymy pusty zestaw i wstawiamy do niego kilka elementów:

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

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

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

Gdy mamy już kilka elementów w zestawie, możemy wykonać kilka operacji:

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

Możemy również iterować elementy mapy za pomocą iteratora lub pętli foreach. Pamiętaj, że wpisy są drukowane zgodnie z ich naturalną kolejnością , a nie kolejnością wstawiania:

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 niestandardowego typu Java

Ponieważ TreeMap i TreeSet s utrzymują klucze / elementy zgodnie z ich naturalną kolejnością . Dlatego klucze TreeMap i elementy TreeSet muszą być do siebie porównywalne.

Załóżmy, że mamy niestandardową klasę Person :

public class Person  {

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

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

Jeśli przechowujemy go tak, jak jest w TreeSet (lub Key w TreeMap):

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

Następnie natrafilibyśmy na wyjątek taki jak ten:

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)

Aby to naprawić, załóżmy, że chcemy zamówić instancje Person na podstawie kolejności ich identyfikatorów ( private int id ). Możemy to zrobić na dwa sposoby:

1. Jednym z rozwiązań jest zmodyfikowanie Person aby implementowało interfejs porównywalny :

   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. Innym rozwiązaniem jest wyposażenie TreeSet w komparator :

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

Istnieją jednak dwa zastrzeżenia do obu podejść:

1. Bardzo ważne jest, aby nie modyfikować żadnych pól używanych do zamawiania po wstawieniu instancji do TreeSet / TreeMap . W powyższym przykładzie, jeśli zmienimy id osoby, która jest już wstawiona do kolekcji, możemy napotkać nieoczekiwane zachowanie.

2. Ważne jest prawidłowe i spójne wdrożenie porównania. Zgodnie z Javadoc :

Implementator musi zapewnić sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) dla wszystkich x i y. (Oznacza to, że x.compareTo(y) musi y.compareTo(x) wyjątek, a jeśli y.compareTo(x) zgłasza wyjątek).

Implementator musi również upewnić się, że relacja jest przechodnia: (x.compareTo(y)>0 && y.compareTo(z)>0) oznacza x.compareTo(z)>0 .

Wreszcie, implementator musi upewnić się, że x.compareTo(y)==0 oznacza, że sgn(x.compareTo(z)) == sgn(y.compareTo(z)) , dla wszystkich z.

TreeMap i TreeSet Bezpieczeństwo wątków

TreeMap i TreeSet nie są kolekcjami bezpiecznymi dla wątków, dlatego należy zachować ostrożność, aby zapewnić ich stosowanie w programach wielowątkowych.

Zarówno TreeMap jak i TreeSet są bezpieczne, gdy odczytywane, nawet jednocześnie, przez wiele wątków. Więc jeśli zostały one utworzone i wypełnione jednym wątkiem (powiedzmy na początku programu), a dopiero potem przeczytane, ale nie zmodyfikowane przez wiele wątków, nie ma powodu do synchronizacji lub blokowania.

Jeśli jednak odczytane i zmodyfikowane jednocześnie lub zmodyfikowane jednocześnie przez więcej niż jeden wątek, kolekcja może zgłosić wyjątek ConcurrentModificationException lub zachowywać się nieoczekiwanie. W takich przypadkach konieczne jest zsynchronizowanie / zablokowanie dostępu do kolekcji przy użyciu jednego z następujących sposobów:

1. Za pomocą Collections.synchronizedSorted.. :

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

   Zapewni to implementację SortedSet / SortedMap wspieraną przez rzeczywistą kolekcję i zsynchronizowaną z jakimś obiektem mutex. Zauważ, że spowoduje to zsynchronizowanie całego dostępu do odczytu i zapisu do kolekcji na jednej blokadzie, więc nawet jednoczesne odczytywanie nie byłoby możliwe.

2. Poprzez ręczną synchronizację jakiegoś obiektu, takiego jak sama kolekcja:

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

   ...

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

   ...

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

3. Korzystając z blokady, takiej jak 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();
   

W przeciwieństwie do poprzednich metod synchronizacji, użycie ReadWriteLock pozwala na jednoczesne czytanie wielu wątków z mapy.