Java Language
TreeMap y TreeSet

Introducción

TreeMap de un tipo de Java simple

Primero, creamos un mapa vacío, e insertamos algunos elementos en él:

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 vez que tenemos algunos elementos en el mapa, podemos realizar algunas operaciones:

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

También podemos iterar sobre los elementos del mapa usando un iterador o un bucle foreach. Tenga en cuenta que las entradas se imprimen de acuerdo con su orden natural , no el orden de inserción:

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 de un tipo de Java simple

Primero, creamos un conjunto vacío, e insertamos algunos elementos en él:

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

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

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

Una vez que tenemos algunos elementos en el conjunto, podemos realizar algunas operaciones:

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

También podemos iterar sobre los elementos del mapa usando un iterador o un bucle foreach. Tenga en cuenta que las entradas se imprimen de acuerdo con su orden natural , no el orden de inserción:

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 de un tipo de Java personalizado

Dado que TreeMap sy TreeSet s mantienen llaves / elementos de acuerdo con su orden natural . Por TreeMap tanto, TreeMap claves TreeMap y los elementos TreeSet tienen que ser comparables entre sí.

Digamos que tenemos una clase personalizada de Person :

public class Person  {

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

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

Si lo almacenamos como está en un TreeSet (o una clave en un TreeMap):

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

Entonces nos encontraríamos con una excepción como esta:

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)

Para solucionarlo, supongamos que queremos ordenar instancias de Person función del orden de sus private int id ( private int id ). Podríamos hacerlo de una de dos maneras:

1. Una solución es modificar Person para que implemente la interfaz 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. Otra solución es proporcionar al TreeSet un Comparador :

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

Sin embargo, hay dos advertencias para ambos enfoques:

1. Es muy importante no modificar los campos utilizados para ordenar una vez que una instancia se haya insertado en un TreeSet / TreeMap . En el ejemplo anterior, si cambiamos el id de una persona que ya está insertada en la colección, podríamos encontrar un comportamiento inesperado.

2. Es importante implementar la comparación de manera adecuada y consistente. Según el Javadoc :

El implementador debe asegurarse de que sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) para todas las x y y. (Esto implica que x.compareTo(y) debe lanzar una excepción si y.compareTo(x) lanza una excepción).

El implementador también debe asegurarse de que la relación sea transitiva: (x.compareTo(y)>0 && y.compareTo(z)>0) implica x.compareTo(z)>0 .

Finalmente, el implementador debe asegurarse de que x.compareTo(y)==0 implica que sgn(x.compareTo(z)) == sgn(y.compareTo(z)) , para todas las z.

TreeMap y TreeSet Thread Safety

TreeMap y TreeSet no son colecciones seguras para subprocesos, por lo que se debe tener cuidado para garantizar que se utilicen en programas de subprocesos múltiples.

Tanto TreeMap como TreeSet son seguros cuando se leen, incluso al mismo tiempo, por varios subprocesos. Por lo tanto, si se crearon y rellenaron con un solo subproceso (por ejemplo, al inicio del programa), y solo luego se leyeron, pero no se modificaron por varios subprocesos, no hay razón para la sincronización o el bloqueo.

Sin embargo, si se lee y se modifica al mismo tiempo, o si se modifica al mismo tiempo por más de un hilo, la colección puede generar una ConcurrentModificationException o comportarse de manera inesperada. En estos casos, es imperativo sincronizar / bloquear el acceso a la colección utilizando uno de los siguientes métodos:

1. Utilizando Collections.synchronizedSorted.. :

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

   Esto proporcionará una implementación SortedSet / SortedMap respaldada por la colección real y sincronizada en algún objeto de exclusión mutua . Tenga en cuenta que esto sincronizará todos los accesos de lectura y escritura a la colección en un solo bloqueo, por lo que incluso las lecturas simultáneas no serían posibles.

2. Al sincronizar manualmente en algún objeto, como la propia colección:

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

   ...

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

   ...

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

3. Mediante el uso de un bloqueo, como 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 diferencia de los métodos de sincronización anteriores, el uso de ReadWriteLock permite que varios subprocesos lean del mapa simultáneamente.