Java Language
TreeMap och TreeSet

Introduktion

TreeMap av en enkel Java-typ

Först skapar vi en tom karta och sätter in några element i den:

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

När vi har några element på kartan kan vi utföra några åtgärder:

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

Vi kan också iterera över kartelementen med antingen en Iterator eller en förhandslinga. Observera att posterna skrivs ut enligt deras naturliga beställning , inte införingsordningen:

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 av en enkel Java-typ

Först skapar vi en tom uppsättning och sätter in några element i den:

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

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

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

När vi har några element i uppsättningen kan vi utföra några åtgärder:

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

Vi kan också iterera över kartelementen med antingen en Iterator eller en förhandslinga. Observera att posterna skrivs ut enligt deras naturliga beställning , inte införingsordningen:

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 av en anpassad Java-typ

Eftersom TreeMap och TreeSet behåller nycklar / element enligt deras naturliga beställning . Därför TreeMap nycklar och TreeSet element jämföras med varandra.

Säg att vi har en anpassad Person :

public class Person  {

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

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

Om vi lagrar den som den är i en TreeSet (eller en nyckel i en TreeMap):

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

Sedan skulle vi stöta på ett undantag som det här:

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)

För att fixa det, låt oss anta att vi vill beställa Person baserat på deras ID: s ( private int id ). Vi kan göra det på ett av två sätt:

1. En lösning är att ändra Person så att det skulle implementera det jämförbara gränssnittet :

   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. En annan lösning är att förse TreeSet med en komparator :

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

Det finns dock två varningar för båda metoderna:

1. Det är mycket viktigt att inte ändra några fält som används för att beställa när en instans har lagts in i en TreeSet / TreeMap . I exemplet ovan, om vi ändrar id för en person som redan är infogad i samlingen, kan det hända att vi får ett oväntat beteende.

2. Det är viktigt att genomföra jämförelsen korrekt och konsekvent. Enligt Javadoc :

Implementorn måste säkerställa sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) för alla x och y. (Detta innebär att x.compareTo(y) måste kasta ett undantag iff y.compareTo(x) kastar ett undantag.)

Implementören måste också se till att relationen är transitiv: (x.compareTo(y)>0 && y.compareTo(z)>0) innebär x.compareTo(z)>0 .

Slutligen måste implementatören se till att x.compareTo(y)==0 innebär att sgn(x.compareTo(z)) == sgn(y.compareTo(z)) , för alla z.

TreeMap och TreeSet tråd säkerhet

TreeMap och TreeSet är inte trådsäkra samlingar, så man måste se till att de används i flertrådade program.

Både TreeMap och TreeSet är säkra när de läses, även samtidigt, av flera trådar. Så om de har skapats och fyllts av en enda tråd (säg i början av programmet), och först sedan läses, men inte modifierats av flera trådar, finns det ingen anledning till synkronisering eller låsning.

Men om du läser och modifierar samtidigt, eller modifieras samtidigt med mer än en tråd, kan samlingen kasta en ConcurrentModificationException eller bete sig oväntat. I dessa fall är det viktigt att synkronisera / låsa åtkomst till samlingen med någon av följande metoder:

1. Använda Collections.synchronizedSorted.. :

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

   Detta ger en SortedSet / SortedMap- implementering som stöds av den faktiska samlingen och synkroniseras på något mutex-objekt. Observera att detta kommer att synkronisera all läs- och skrivåtkomst till samlingen på ett enda lås, så att inte samtidigt läsning skulle vara möjligt.

2. Genom att manuellt synkronisera på något objekt, som själva samlingen:

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

   ...

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

   ...

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

3. Genom att använda ett lås, till exempel en 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();
   

Till skillnad från de tidigare synkroniseringsmetoderna, med hjälp av en ReadWriteLock kan flera trådar läsas från kartan samtidigt.