[DataStructure] TreeSet (Java)

1. TreeSet

Java11

Module java.base
Package java.util
Class TreeSet<E>
java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractSet<E>
java.util.TreeSet<E>
Type Parameters:
E - the type of elements maintained by this set
All Implemented Interfaces:
Serializable, Cloneable, Iterable<E>, Collection<E>, NavigableSet<E>, Set<E>, SortedSet<E>

public class TreeSet<E>
extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, Serializable

2. 설명

TreeMap을 기반으로 하는 NavigableSet 인터페이스를 구현한 클래스입니다. 요소는 사용되는 생성자에 따라 자연스러운 순서를 사용하거나 세트 생성 시 제공되는 Comparator에 의해 순서가 지정됩니다.

이 구현은 기본 작업(추가, 제거 및 포함)에 대해 보장된 log(n) 시간 복잡도를 제공합니다.

Set 인터페이스를 올바르게 구현하려면 집합에 의해 유지되는 순서(명시적 비교기가 제공되는지 여부에 관계없이)가 equals와 일치해야 합니다. (같음과 일치에 대한 정확한 정의는 Comparable 또는 Comparator를 참조하십시오.) 이는 Set 인터페이스가 equal 작업의 관점에서 정의되기 때문에 그렇습니다. 그러나 TreeSet 인스턴스는 compareTo(또는 비교) 메서드를 사용하여 모든 요소 비교를 수행하므로 두 이 방법으로 동일하다고 간주되는 요소는 집합의 관점에서 동일합니다. 집합의 동작은 순서가 equals와 일치하지 않더라도 잘 정의됩니다. Set 인터페이스의 일반 계약을 따르지 않을 뿐입니다.

이 구현은 동기화되지 않습니다. 여러 스레드가 동시에 TreeSet에 액세스하고 스레드 중 적어도 하나가 세트를 수정하는 경우 외부에서 동기화되어야 합니다. 이것은 일반적으로 집합을 자연스럽게 캡슐화하는 일부 개체에서 동기화하여 수행됩니다. 그러한 개체가 없으면 Collections.synchronizedSortedSet 메서드를 사용하여 집합을 "래핑"해야 합니다. 이는 세트에 대한 우발적인 동기화되지 않은 액세스를 방지하기 위해 생성 시 수행하는 것이 가장 좋습니다.

SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

이 클래스의 iterator 메서드에 의해 반환된 iterator는 fail-fast입니다. iterator가 생성된 후 언제든지 집합이 수정되면 반복자의 자체 제거 메서드를 통하지 않고 어떤 방식으로든 반복자는 ConcurrentModificationException을 throw합니다. 따라서 동시 수정에 직면하여 반복자는 미래의 불확실한 시간에 임의적이고 비결정적인 동작의 위험을 감수하기보다는 빠르고 깔끔하게 실패합니다.

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

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

Since:
1.2
See Also:
Collection, Set, HashSet, Comparable, Comparator, TreeMap, Serialized Form