📖 Set 컬렉션 클래스

---

• Set 인터페이스를 구현한 모든 Set 컬렉션 클래스의 특징

  1. 요소의 저장 순서 유지하지 않음
  2. 같은 요소의 중복 저장 허용하지 않음

• 대표적인 Set 컬렉션 클래스
  1. HashSet
  2. TreeSet

💬 HashSet< E > 클래스

---

• HashSet 클래스는 Set 컬렉션 클래스에서 가장 많이 사용되는 클래스 중 하나
• JDK 1.2부터 제공된 HashSet 클래스는 해시 알고리즘(hash algorithm)을 사용하여 검색 속도가 매우 빠름
• 내부적으로 HashMap 인스턴스를 이용하여 요소 저장
• 요소를 저장 순서가 유지되지 않고 중복 값은 허용하지 않음
• null 허용
• 시간복잡도
  • add : O(1)
  • contains : O(1)
  • next : O(h/n) (h는 테이블 용량)

◾ HashSet 메소드

메소드명	설명
boolean add(E o)	제네릭 타입으로 넘어온 객체가 Set구조에 없다면 추가하고 true를 반환합니다.
boolean addAll(Collection c)	주어진 컬렉션에 저장된 모든 객체들을 추가합니다.(합집합)
void clear( )	Set구조에 있는 모든 요소들을 삭제합니다.
Object clone()	HashSet을 복제해서 반환합니다.(얕은 복사)
boolean contains(Object o)	인자로 전달된 객체를 현 Collection에서 요소로 가지고 있으면 true를 반환합니다.
boolean containsAll(Collection c)	주어진 컬렉션에 저장된 모든 객체들을 포함하고 있는지 알려줍니다.
boolean isEmpty( )	현 Collection에 저장된 요소가 없으면 true반환합니다.
Iterator< E > iterator( )	현 Set 구조의 요소들을 순서대로 처리하기 위해 Iterator객체로 반환합니다.
boolean remove(Object o)	현 Set 구조에서 인자로 전달된 객체를 삭제합니다. 이때 삭제에 성공하면 true를 반환합니다.
boolean removeAll(Collection c)	주어진 컬렉션에 저장된 모든 객체와 동일한 것들을 HashSet에서 모두 삭제합니다.(차집합)
int size( )	현 Set구조에 저장된 요소의 수를 반환합니다.
Object[] toArray()	저장된 객체들을 객체배열의 형태로 반환합니다.
Object[] toArray(Object[] a)	저장된 객체들을 주어진 객체배열(a)에 저장합니다.

💬 TreeSet< E > 클래스

---

• TreeSet 클래스는 데이터가 정렬된 상태로 저장되는 이진 검색 트리(binary search tree)의 형태로 요소를 저장

• 이진 검색 트리는 데이터를 추가하거나 제거하는 등의 기본 동작 시간이 매우 빠름

• JDK 1.2부터 제공되는 TreeSet 클래스는 NavigableSet 인터페이스를 기존의 이진 검색 트리의 성능을 향상시킨 레드-블랙 트리(Red-Black tree)로 구현

  • 레드 블랙 트리
    • 일반적인 이진 탐색 트리는 트리의 높이만큼 시간이 걸림
    • 데이터의 값이 트리에 잘 분산되어 있다면 효율성에 큰 문제가 없으나 데이터가 들어올 때 값이 편향되게 들어올 경우 한쪽으로 크게 치우쳐진 트리가 되어 굉장히 비효율적인 퍼포먼스 나옴
    • 이 문제를 보완하기 위해 레드 블랙 트리가 등장
    • 레드 블랙 트리는 부모노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제 시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞추어줌

• 요소를 저장 순서 유지되지 않고 중복 값 허용하지 않음

• HashSet보다 데이터의 추가/삭제는 시간이 더 걸리지만 검색과 정렬에는 유리

  • 삽입과 동시에 정렬 상태 유지

• 다양한 정렬 방법을 지정할 수 있음

• 시간복잡도

  • add : O(log n)
  • contains : O(log n)
  • next : O(long n)

◾ TreeSet의 주요 메소드

메소드	설명
boolean add(Object o)	지정된 객체(o)의 객체들을 Collection에 추가합니다.
boolean addAll(Collection c)	지정된 Collection(c)의 객체들을 Collection에 추가합니다.
Object ceiling(Object o)	지정된 객체와 같은 객체를 반환합니다. 없으면 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환합니다. 없으면 null
void clear()	저장된 모든 객체를 삭제합니다.
Object clone()	TreeSet을 복제하여 반환합니다.
Comparator comparator()	TreeSet의 정렬기준(Comparator)를 반환합니다.
boolean contains(Object o)	지정된 객체(o)의 객체들이 포함되어 있는지 확인합니다.
boolean containsAll(Collection c)	지정된 Collection의 객체들이 포함되어 있는지 확인합니다.
NavigableSet descendingSet()	TreeSet에 저장된 요소들을 역순으로 정렬해서 반환합니다.
Object first()	정렬된 순서에서 첫 번째 객체를 반환합니다.
Object floor(Object o)	지정된 객체와 같은 객체를 반환합니다.없으면 작은 값을 가진 객체 중 가장 가까운 값의 객체를 반환합니다. 없으면 null
SortedSet headSet(Object toElement)	지정된 객체보다 작은 값의 객체들을 반환합니다.
NavigableSet headSet(Object toElement, boolean inclusive)	지정된 객체보다 작은 값으 객체들을 반환합니다. inclusive가 true이면 같은 값의 객체도 포함합니다.
Object higher(Object o)	지정된 객체보다 큰 값을 가진 객체 중 제일 가까운 값의 객체를 반환합니다. 없으면 null
boolean isEmpty()	TreeSet이 비어 있는지 확인합니다.
Iterator iterator()	TreeSet의 Iterator를 반환합니다.
Object last()	정렬된 순서에서 마지막 객체를 반환합니다.
Object lower(Object o)	지정된 객체보다 작은 값을 가진 객체 중 제일 가까운 값의 객체를 반환합니다. 없으면 null
Object pollFirst()	TreeSet의 첫번째 요소(제일 작은 값의 객체)를 반환합니다.
Object pollLast()	TreeSet의 마지막 요소(제일 큰 값의 객체)를 반환합니다.
boolean remove(Object o)	지정된 객체를 제거합니다.
boolean retainAll(Collection c)	주어진 컬렉션과 공통된 요소만을 남기고 삭제합니다.(교집합)
int size()	저장된 객체의 개수를 반환합니다.
Spliterator spliterator()	TreeSet의 spliterator를 반환합니다.
SortedSet subSet(Object frontElement, Object toElement)	범위검색(fromElement와 toElement사이)의 결과를 반환합니다. 끝 범위인 toElement는 범위에 포함되지 않습니다.
NavigableSet< E > subSet(E fromElement, boolean fromInclusive, E toElement, booleantoInclusive)	범위검색(fromElement와 toElement사이)의 결과를 반환합니다.fromInclusive가 true이면 시작값이 포함되고, toInclusive가 true이면 끝값이 포함됩니다.
SortedSet tailSet(Object fromElement)	지정된 객체보다 큰 값의 객체들을 반환합니다.
Object[] toArray()	저장된 객체를 객체배열로 반환합니다.
Object[] toArray(Object[] a)	저장된 객체를 주어진 객체배열에 저장하여 반환합니다.