Java Language
TreeMap e TreeSet

introduzione

TreeMap di un semplice tipo Java

Per prima cosa, creiamo una mappa vuota e inseriamo alcuni elementi in essa:

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

Una volta che abbiamo alcuni elementi nella mappa, possiamo eseguire alcune operazioni:

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

Possiamo anche scorrere gli elementi della mappa usando un Iterator o un ciclo foreach. Si noti che le voci vengono stampate in base al loro ordinamento naturale , non all'ordine di inserimento:

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 di un semplice tipo Java

Per prima cosa, creiamo un set vuoto e inseriamo alcuni elementi in esso:

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

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

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

Una volta che abbiamo alcuni elementi nel set, possiamo eseguire alcune operazioni:

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

Possiamo anche scorrere gli elementi della mappa usando un Iterator o un ciclo foreach. Si noti che le voci vengono stampate in base al loro ordinamento naturale , non all'ordine di inserimento:

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 di un tipo Java personalizzato

Poiché TreeMap e TreeSet mantengono le chiavi / gli elementi in base al loro ordinamento naturale . Quindi le chiavi TreeMap e TreeSet elementi TreeSet devono essere paragonabili tra loro.

Supponiamo di avere una classe Person personalizzata:

public class Person  {

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

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

Se lo memorizziamo così com'è in un TreeSet (o una chiave in una TreeMap):

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

Quindi corriamo in un'eccezione come questa:

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)

Per risolvere il problema, supponiamo di voler ordinare istanze Person base all'ordine dei loro id ( private int id ). Potremmo farlo in due modi:

1. Una soluzione è modificare Person modo da implementare l' interfaccia 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. Un'altra soluzione è fornire TreeSet con un comparatore :

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

Tuttavia, vi sono due avvertimenti su entrambi gli approcci:

1. È molto importante non modificare i campi utilizzati per ordinare una volta che un'istanza è stata inserita in un TreeSet / TreeMap . Nell'esempio precedente, se cambiamo l' id di una persona che è già inserita nella raccolta, potremmo imbattersi in un comportamento imprevisto.

2. È importante implementare il confronto correttamente e coerentemente. Come da Javadoc :

L'implementatore deve garantire sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) per tutti xey. (Ciò implica che x.compareTo(y) deve generare un'eccezione iff y.compareTo(x) genera un'eccezione).

L'implementatore deve inoltre garantire che la relazione sia transitiva: (x.compareTo(y)>0 && y.compareTo(z)>0) implica x.compareTo(z)>0 .

Infine, l'implementatore deve assicurarsi che x.compareTo(y)==0 implichi che sgn(x.compareTo(z)) == sgn(y.compareTo(z)) , per tutti z.

TreeMap e TreeSet Thread Safety

TreeMap e TreeSet non sono TreeSet thread-safe, quindi è necessario prestare attenzione per garantire l'utilizzo in programmi multi-thread.

Sia TreeMap che TreeSet sono sicuri quando letti, anche contemporaneamente, da più thread. Quindi, se sono stati creati e popolati da un singolo thread (ad esempio all'inizio del programma) e solo poi letti, ma non modificati da più thread, non c'è motivo per la sincronizzazione o il blocco.

Tuttavia, se letto e modificato contemporaneamente o modificato contemporaneamente da più di un thread, la raccolta potrebbe generare una ConcurrentModificationException o comportarsi in modo imprevisto. In questi casi, è assolutamente necessario sincronizzare / bloccare l'accesso alla raccolta utilizzando uno dei seguenti approcci:

1. Utilizzando Collections.synchronizedSorted.. :

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

   Ciò fornirà una SortedSet / SortedMap attuazione sostenuta dalla collezione reale e sincronizzato su qualche oggetto mutex. Si noti che questo sincronizzerà tutti gli accessi in lettura e scrittura alla raccolta su un singolo blocco, quindi anche le letture concorrenti non sarebbero possibili.

2. Sincronizzando manualmente su alcuni oggetti, come la raccolta stessa:

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

   ...

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

   ...

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

3. Utilizzando un blocco, come un 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();
   

A differenza dei precedenti metodi di sincronizzazione, l'utilizzo di ReadWriteLock consente a più thread di leggere contemporaneamente dalla mappa.