[DataStructure] TreeMap (Java)

1. TreeMap

Java11

Module java.base
Package java.util
Class TreeMap<K,​V>

java.lang.Object
    java.util.AbstractMap<K,​V>
        java.util.TreeMap<K,​V>

Type Parameters:
K - the type of keys maintained by this map
V - the type of mapped values

All Implemented Interfaces:
Serializable, Cloneable, Map<K,​V>, NavigableMap<K,​V>, SortedMap<K,​V>

public class TreeMap<K,​V>
extends AbstractMap<K,​V>
implements NavigableMap<K,​V>, Cloneable, Serializable

Red-Black 트리 기반 NavigableMap 구현입니다. Map은 사용되는 생성자에 따라, 키의 자연스러운 순서에 따라, 또는 Map 생성 시 제공된 Comparator에 따라 정렬됩니다.

이 구현은 containsKey, get, put 및 remove 작업에 대한 보장된 log(n) 시간 비용을 제공합니다. 알고리즘은 Cormen, Leiserson, Rivest's Introduction to Algorithms에 있는 알고리즘을 적용한 것입니다.

SortedMap과 마찬가지로 TreeMap에 의해 유지되는 순서와 명시적 comparator가 제공되는지 여부는 이 SortedMap이 Map 인터페이스를 올바르게 구현하는 경우 equals와 일치해야합니다.(consistent와 equals의 정확한 정의는 Comparable 또는 Comparator를 참조하세요.)
이는 Map 인터페이스가 equals 연산으로 정의되어 있지만 sortedMap은 compareTo(또는 compare) 메서드를 사용하여 모든 키 비교를 수행하므로 이 메서드에서 동일한 것으로 간주되는 두개의 키는 SortedMap 관점에서 동일합니다. TreeMap의 동작은 순서가 equals와 일치하지 않더라도 잘 정의됩니다. Map 인터페이스의 일반 계약을 따르지 않을 뿐입니다.

이 구현은 동기화되지 않습니다. 여러 스레드가 동시에 맵에 액세스하고 스레드 중 하나 이상이 구조적으로 맵을 수정하는 경우 외부에서 동기화되어야 합니다. (구조적 수정은 하나 이상의 매핑을 추가하거나 삭제하는 모든 작업입니다. 단순히 기존 키와 연결된 값을 변경하는 것은 구조적 수정이 아닙니다.) 이는 일반적으로 맵을 자연스럽게 캡슐화하는 일부 객체를 동기화하여 수행됩니다. 그러한 객체가 없으면 Collections.synchronizedSortedMap 메소드를 사용하여 맵을 "래핑"해야 합니다. 지도에 대한 우발적인 동기화되지 않은 액세스를 방지하려면 생성 시 수행하는 것이 가장 좋습니다.

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

이 클래스의 모든 "컬렉션 뷰 메소드"에 의해 리턴된 컬렉션의 iterator 메소드에 의해 리턴된 반복자는 고속입니다. 반복자가 생성된 후 언제든지 맵이 구조적으로 수정되는 경우 반복자의 자체 제거를 통하지 않는 방식으로 수정됩니다. 메서드에서 반복자는 ConcurrentModificationException을 throw합니다. 따라서 동시 수정에 직면하여 반복자는 미래의 불확실한 시간에 임의적이고 비결정적인 동작의 위험을 감수하기보다는 빠르고 깔끔하게 실패합니다.

iterator의 fail-fast 동작은 일반적으로 동기화되지 않은 동시 수정이 있는 상태에서 확실한 보장을 하는 것이 불가능하기 때문에 보장할 수 없습니다. Fail-fast iterator는 최선을 다해 ConcurrentModificationException을 발생시킵니다. 따라서 정확성을 위해 이 예외에 의존하는 프로그램을 작성하는 것은 잘못된 것입니다. 반복기의 빠른 실패 동작은 버그를 감지하는 데만 사용해야 합니다.

이 클래스의 메서드에서 반환된 모든 Map.Entry 쌍과 해당 뷰는 매핑이 생성된 시점의 스냅샷을 나타냅니다. Entry.setValue 메소드를 지원하지 않습니다. (그러나 put을 사용하여 연결된 맵에서 매핑을 변경할 수 있습니다.)

이 클래스는 Java Collections Framework의 멤버입니다.

Since:
1.2
See Also:
Map, HashMap, Hashtable, Comparable, Comparator, Collection, Serialized Form