Java Language
TreeMap und TreeSet

Einführung

TreeMap eines einfachen Java-Typs

Zuerst erstellen wir eine leere Map und fügen einige Elemente ein:

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

Sobald wir einige Elemente in der Karte haben, können wir einige Operationen ausführen:

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

Wir können die Kartenelemente auch mit einem Iterator oder einer foreach-Schleife durchlaufen. Beachten Sie, dass die Einträge gemäß ihrer natürlichen Reihenfolge gedruckt werden, nicht der Reihenfolge der Einfügung:

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 eines einfachen Java-Typs

Zuerst erstellen wir ein leeres Set und fügen einige Elemente ein:

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

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

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

Sobald wir einige Elemente im Set haben, können wir einige Operationen ausführen:

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

Wir können die Kartenelemente auch mit einem Iterator oder einer foreach-Schleife durchlaufen. Beachten Sie, dass die Einträge gemäß ihrer natürlichen Reihenfolge gedruckt werden, nicht der Reihenfolge der Einfügung:

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 eines benutzerdefinierten Java-Typs

Da TreeMap s und TreeSet s Schlüssel / Elemente gemäß ihrer natürlichen Reihenfolge pflegen. TreeMap Schlüssel und TreeSet Elemente miteinander vergleichbar sein.

Angenommen, wir haben eine benutzerdefinierte Person :

public class Person  {

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

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

Wenn wir es in einem TreeSet (oder einem Key in einer TreeMap) unverändert speichern:

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

Dann stießen wir auf eine Ausnahme wie diese:

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)

Um dies zu beheben, nehmen wir an, dass wir Person nach der Reihenfolge ihrer IDs ordnen möchten ( private int id ). Wir können es auf zwei Arten tun:

1. Eine Lösung besteht darin, Person so zu ändern, dass die Comparable-Schnittstelle implementiert wird :

   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. Eine andere Lösung besteht darin, das TreeSet mit einem Comparator 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());
    }
});

Bei beiden Ansätzen gibt es jedoch zwei Einschränkungen:

1. Es ist sehr wichtig , keine Felder zu ändern, die zum TreeSet verwendet werden, nachdem eine Instanz in eine TreeSet / TreeMap eingefügt wurde. Wenn wir im obigen Beispiel die id einer Person ändern, die bereits in die Sammlung eingefügt wurde, kann dies zu unerwartetem Verhalten führen.

2. Es ist wichtig, den Vergleich richtig und konsistent durchzuführen. Wie im Javadoc :

Der Implementierer muss sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) für alle x und y sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) . (Dies bedeutet, dass x.compareTo(y) eine Ausnahme y.compareTo(x) muss, wenn y.compareTo(x) eine Ausnahme y.compareTo(x) .)

Der Implementierer muss außerdem sicherstellen, dass die Relation transitiv ist: (x.compareTo(y)>0 && y.compareTo(z)>0) impliziert x.compareTo(z)>0 .

Schließlich muss der Implementierer sicherstellen, dass x.compareTo(y)==0 bedeutet, dass sgn(x.compareTo(z)) == sgn(y.compareTo(z)) für alle z.

TreeMap- und TreeSet-Thread-Sicherheit

TreeMap und TreeSet sind keine Thread-sicheren Sammlungen, daher muss bei der Verwendung in Multithread-Programmen darauf geachtet werden.

Sowohl TreeMap als auch TreeSet sind sicher, wenn sie von mehreren Threads gleichzeitig gelesen werden. Wenn sie also von einem einzelnen Thread erstellt und gefüllt wurden (z. B. beim Start des Programms) und erst dann gelesen, aber nicht von mehreren Threads geändert werden, gibt es keinen Grund für die Synchronisierung oder das Sperren.

Wenn die Auflistung jedoch gleichzeitig gelesen und geändert wird oder von mehr als einem Thread gleichzeitig geändert wird, kann die Auflistung eine ConcurrentModificationException auslösen oder sich unerwartet verhalten. In diesen Fällen ist es unbedingt erforderlich, den Zugriff auf die Sammlung mit einem der folgenden Ansätze zu synchronisieren / sperren:

1. Verwenden von Collections.synchronizedSorted.. :

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

   Dadurch wird eine SortedSet / SortedMap- Implementierung bereitgestellt , die von der eigentlichen Auflistung unterstützt und für ein Mutex-Objekt synchronisiert wird. Beachten Sie, dass dadurch alle Lese- und Schreibzugriffe auf die Sammlung mit einer einzigen Sperre synchronisiert werden, so dass selbst gleichzeitiges Lesen nicht möglich ist.

2. Durch manuelles Synchronisieren für ein Objekt wie die Sammlung selbst:

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

   ...

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

   ...

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

3. Verwenden Sie eine Sperre, z. B. eine 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();
   

Im Gegensatz zu den vorherigen Synchronisationsmethoden können bei Verwendung von ReadWriteLock mehrere Threads gleichzeitig aus der Map lesen.