Java Language
TreeMap 및 TreeSet

소개

간단한 Java 유형의 TreeMap

먼저, 빈 맵을 생성하고 거기에 몇 가지 요소를 삽입합니다.

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

지도에 몇 가지 요소가 있으면 몇 가지 작업을 수행 할 수 있습니다.

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

또한 Iterator 또는 foreach 루프를 사용하여 맵 요소를 반복 할 수 있습니다. 엔트리는 삽입 순서가 아닌 자연 순서 에 따라 인쇄됩니다.

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 
}

간단한 Java 형의 TreeSet

먼저 빈 세트를 만들고 그 안에 몇 개의 요소를 삽입합니다.

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

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

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

세트에 몇 가지 요소가 있으면 몇 가지 작업을 수행 할 수 있습니다.

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

또한 Iterator 또는 foreach 루프를 사용하여 맵 요소를 반복 할 수 있습니다. 엔트리는 삽입 순서가 아닌 자연 순서 에 따라 인쇄됩니다.

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
}

커스텀 Java 형의 TreeMap / TreeSet

TreeMap 및 TreeSet 는 자연 순서 부 에 따라 키 / 요소를 유지하므로 따라서 TreeMap 키와 TreeSet 요소는 서로 비교할 수 있어야합니다.

사용자 정의 Person 클래스가 있다고 가정 해보십시오.

public class Person  {

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

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

TreeSet (또는 TreeMap의 Key)에 현재의 것을 보관 유지하는 경우는, 다음과 같이합니다.

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

그런 다음 우리는 다음과 같은 Exception을 실행합니다.

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)

이 문제를 해결하기 위해, 우리는 자신의 id ( private int id )의 순서에 따라 Person 인스턴스를 정렬하고자한다고 가정 해 봅시다. 우리는 두 가지 방법 중 하나로 그것을 할 수 있습니다 :

1. 한 가지 해결책은 Person 을 수정하여 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. 또 다른 해결책은 제공하는 것입니다 TreeSet A를 비교기를 :

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

그러나 두 가지 접근 방법에 대한 두 가지주의 사항이 있습니다.

1. 인스턴스가 TreeSet / TreeMap 삽입되면 순서 지정에 사용되는 필드를 수정하지 않는 것이 매우 중요 합니다. 위의 예에서 컬렉션에 이미 삽입 된 사람의 id 를 변경하면 예기치 않은 동작이 발생할 수 있습니다.

2. 비교를 적절하고 일관되게 실행하는 것이 중요합니다. Javadoc에 따라 :

구현자는 모든 x와 y에 대해 sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) 을 보장해야한다. ( y.compareTo(x) 가 예외를 throw하면 x.compareTo(y) 가 예외를 throw해야 함을 의미합니다.

구현자는 또한이 관계가 이행 적이라는 것을 보장해야한다 : (x.compareTo(y)>0 && y.compareTo(z)>0) x.compareTo(z)>0 의미한다.

마지막으로, 구현자는 모든 z에 대해 x.compareTo(y)==0 이 sgn(x.compareTo(z)) == sgn(y.compareTo(z)) 하도록 보장해야합니다.

TreeMap 및 TreeSet 스레드 안전성

TreeMap 및 TreeSet 관리가 멀티 스레드 프로그램에서 사용할 때 않도록주의해야한다, 그래서하지 스레드 안전 모음입니다.

TreeMap 과 TreeSet 는 동시에 여러 스레드에서 읽을 때 안전합니다. 따라서 프로그램이 시작될 때 단일 스레드로 생성되고 채워지고 여러 스레드에서 읽지 만 수정되지 않으면 동기화 또는 잠금이 필요하지 않습니다.

다만, 복수의 thread에 의해 동시에 변경 또는 독해가 행해지면, 콜렉션은 ConcurrentModificationException를 Throw하거나 예기치 않게 동작합니다. 이러한 경우 다음 방법 중 하나를 사용하여 컬렉션에 대한 액세스를 동기화 / 잠그는 것이 중요합니다.

1. Collections.synchronizedSorted.. 사용 :

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

   이것에 의해, 실제의 콜렉션에 근거 하는 SortedSet / SortedMap 구현이 제공되어 일부 뮤텍스 객체상에서 동기화됩니다. 이렇게하면 단일 잠금에서 컬렉션에 대한 모든 읽기 및 쓰기 액세스가 동기화되므로 동시 읽기조차도 불가능합니다.

2. 컬렉션 자체와 같이 일부 개체에서 수동으로 동기화하면 다음과 같이됩니다.

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

   ...

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

   ...

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

3. 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();
   

이전 동기화 방법과 달리 ReadWriteLock을 사용하면 여러 스레드가 동시에 맵에서 읽을 수 있습니다.