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

This class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element. (...) 

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets.

- Set 인터페이스를 구현하고

- Hash table ( Hash Map ) 의 방식을 통하며,

- 순서를 무시한다. 그만큼 빠르다.

- 기본 기능에 시간이 "상수"로 소요된다. 

LinkedHashSet

Hash table and linked list implementation of the Set interface, with predictable iteration order. (...) This implementation spares its clients from the unspecified, generally chaotic ordering provided by 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 

- Set 인터페이스를 구현하는데

- iteration 순서를 가진다. (HashSet 의 순서무시 카오스와 대비되게-)

- 그러면서도 TreeSet 이 야기하는 비용? 비효율성도 없다.

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)

E ceiling(E e)        //greater or inclusive

E higher(E e)        //greater

etc.