Ricerca…


introduzione

TreeMap e TreeSet sono raccolte Java di base aggiunte in Java 1.2. TreeMap è un mutevole, ordinata, Map implementazione. Allo stesso modo, TreeSet è un'implementazione Set mutevole e ordinata .

TreeMap è implementato come un albero Red-Black, che fornisce i tempi di accesso O(log n) . TreeSet viene implementato utilizzando una TreeMap con valori fittizi.

Entrambe le collezioni non sono thread-safe.

TreeMap di un semplice tipo Java

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

Java SE 7
TreeMap<Integer, String> treeMap = new TreeMap<>();
Java SE 7
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:

Java SE 7
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:

Java SE 7
TreeSet<Integer> treeSet = new TreeSet<>();
Java SE 7
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:

Java SE 7
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 :

Java SE 8
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.



Modified text is an extract of the original Stack Overflow Documentation
Autorizzato sotto CC BY-SA 3.0
Non affiliato con Stack Overflow