Java Language
TreeMap en TreeSet

Invoering

TreeMap van een eenvoudig Java-type

Eerst maken we een lege kaart en voegen we enkele elementen in:

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

Zodra we een paar elementen op de kaart hebben, kunnen we enkele bewerkingen uitvoeren:

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

We kunnen ook de kaartelementen herhalen met behulp van een Iterator of een foreach-lus. Merk op dat de items worden afgedrukt volgens hun natuurlijke volgorde , niet de volgorde van invoegen:

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 van een eenvoudig Java-type

Eerst maken we een lege set en voegen we enkele elementen in:

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

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

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

Zodra we een paar elementen in de set hebben, kunnen we enkele bewerkingen uitvoeren:

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

We kunnen ook de kaartelementen herhalen met behulp van een Iterator of een foreach-lus. Merk op dat de items worden afgedrukt volgens hun natuurlijke volgorde , niet de volgorde van invoegen:

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 van een aangepast Java-type

Omdat TreeMap en TreeSet sleutels / elementen onderhouden volgens hun natuurlijke volgorde . Daarom moeten TreeMap sleutels en TreeSet elementen met elkaar vergelijkbaar zijn.

Stel dat we een aangepaste Person :

public class Person  {

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

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

Als we het opslaan zoals het is in een TreeSet (of een sleutel in een TreeMap):

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

Dan zouden we een uitzondering zoals deze tegenkomen:

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)

Laten we aannemen dat we Person rangschikken op basis van de volgorde van hun ID's ( private int id ). We kunnen het op twee manieren doen:

1. Een oplossing is om Person zodanig aan te passen dat deze de Vergelijkbare interface implementeert:

   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. Een andere oplossing is om de TreeSet een Comparator te bieden :

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

Er zijn echter twee kanttekeningen bij beide benaderingen:

1. Het is heel belangrijk om geen velden te wijzigen die worden gebruikt om te bestellen nadat een exemplaar in een TreeSet / TreeMap is ingevoegd. Als we in het bovenstaande voorbeeld de id wijzigen van een persoon die al in de verzameling is ingevoegd, kunnen we onverwacht gedrag tegenkomen.

2. Het is belangrijk om de vergelijking correct en consistent te implementeren. Volgens de Javadoc :

De implementor moet zorgen voor sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) voor alle x en y. (Dit betekent dat x.compareTo(y) een uitzondering moet x.compareTo(y) y.compareTo(x) een uitzondering y.compareTo(x) .)

De implementator moet er ook voor zorgen dat de relatie transitief is: (x.compareTo(y)>0 && y.compareTo(z)>0) impliceert x.compareTo(z)>0 .

Ten slotte moet de implementator ervoor zorgen dat x.compareTo(y)==0 impliceert dat sgn(x.compareTo(z)) == sgn(y.compareTo(z)) , voor alle z.

TreeMap en TreeSet Thread Safety

TreeMap en TreeSet zijn geen thread-safe collecties, dus wees voorzichtig bij gebruik in multi-threaded programma's.

Zowel TreeMap als TreeSet zijn veilig wanneer ze worden gelezen, zelfs gelijktijdig, door meerdere threads. Dus als ze zijn gemaakt en gevuld met een enkele thread (bijvoorbeeld aan het begin van het programma) en alleen worden gelezen, maar niet worden gewijzigd door meerdere threads, is er geen reden voor synchronisatie of vergrendeling.

Als de verzameling echter gelijktijdig wordt gelezen en gewijzigd of gelijktijdig door meer dan één thread wordt gewijzigd, kan de verzameling een ConcurrentModificationException genereren of zich onverwacht gedragen. In deze gevallen is het absoluut noodzakelijk om de toegang tot de verzameling te synchroniseren / vergrendelen met behulp van een van de volgende benaderingen:

1. Collections.synchronizedSorted.. :

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

   Dit levert een SortedSet / SortedMap- implementatie op, ondersteund door de daadwerkelijke verzameling, en gesynchroniseerd met een of ander mutex-object. Merk op dat dit alle lees- en schrijftoegang tot de verzameling op één slot synchroniseert, dus zelfs gelijktijdige leesbewerkingen zouden niet mogelijk zijn.

2. Door handmatig op een object te synchroniseren, zoals de verzameling zelf:

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

   ...

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

   ...

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

3. Door een slot te gebruiken, zoals een 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();
   

In tegenstelling tot de vorige synchronisatiemethoden, kunnen met behulp van een ReadWriteLock meerdere threads tegelijkertijd van de kaart worden gelezen.