Java API 분석__Set, HashSet, TreeSet, LinkedHashSet
Set
public interface Set<E>
extends Collection<E>
순서에 상관없이, 어떤 데이터가 존재하는지를 확인하기 위한 용도로 많이 사용된다. 중복되는 것을 방지하고, 원하는 값이 포함되어 있는지를 확인하는 것이 주 용도이다.
1. HashSet: 순서가 전혀 필요없는 데이터를 해시 테이블 hash table 에 저장한다. Set 중에서 가장 성능이 좋다.
2. TreeSet: 저장된 데이터의 값에 따라서 정렬되는 셋이다. red-black 이라는 트리 tree 타입으로 값이 저장되며, HashSet 보다 약간 성능이 느리다.
3. LinkedHashSet: 연결된 목록 타입으로 구현된 해시 테이블에 데이터를 저장한다. 저장된 순서에 따라서 값이 정렬된다. 대신 성능이 이 셋 중에서 가장 나쁘다.
성능 차이는 데이터 정렬 때문이다.
HashSet / LinkedHashSet
HashSet
LinkedHashSet
HashSet
, without incurring the increased cost associated with TreeSet
. (Clients generally appreciate having things returned in the same order they were presented.) It can be used to produce a copy of a set that has the same order as the original, regardless of the original set's implementation void foo(Set s) { Set copy = new LinkedHashSet(s); ... }
TreeSet
TreeSet
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, SortedSet <E>, Cloneable, Serializable
Java TreeSet class implements the Set interface that uses a tree for storage.
A NavigableSet
implementation based on a TreeMap
. The elements are ordered using their natural ordering, or by a Comparator
provided at set creation time, depending on which constructor is used.
This implementation provides guaranteed log(n) time cost for the basic operations (add
, remove
and contains
).
A SortedSet
extended with navigation methods reporting closest matches for given search targets.
- 트리 구조로 저장하는 Set Interface 구현한 자료구조
- 순서를 가진다. 값들은 별도로 Comparator 가 주어지지 않는 한, Natural Ordering 을 따른다.
- NavigableSet<E> 인터페이스가 추가됨에 따라 주어진 target 보다 큰것, 크거나 같은것 등등 위치를 찾아 돌아다니는 메소드들이 다양하게 추가되어있다.
- 기본 기능에 시간 log(n) 이 소요된다.
public TreeSet(Comparator<? super E> comparator)
etc.