Set

Set

Set은 중복을 허용하지 않고, 순서를 보장하지 않는 자료 구조이다.

Set 인터페이스

자바의 Set 인터페이스는 java.util 패키지의 컬렉션 프레임워크에 속하는 인터페이스 중 하나이다. Set 인터페이스는 중복을 허용하지 않는 유일한 요소의 집합을 나타낸다. 즉, 어떤 요소도 같은 Set 내에 두 번 이상 나타날 수 없다. Set 은 수학적 집합 개념을 구현한 것으로, 순서를 보장하지 않으며, 특정 요소가 집합에 있는지 여부를 확인하는데 최적화되어 있다.
Set 인터페이스는 HashSet, LinkedHashSet, TreeSet 등의 여러 구현 클래스를 가지고 있으며, 각 클래스는 Set 인터페이스를 구현하며 각각의 특성을 가지고 있다.

Set 인터페이스의 주요 메서드

메서드	설명
add(E e)	지정된 요소를 세트에 추가한다(이미 존재하는 경우 추가하지 않음).
addAll(Collection<? extends E> c)	지정된 컬렉션의 모든 요소를 세트에 추가한다.
contains(Object o)	세트가 지정된 요소를 포함하고 있는지 여부를 반환한다.
containsAll(Collection<?> c)	세트가 지정된 컬렉션의 모든 요소를 포함하고 있는지 여부를 반환한다.
remove(Object o)	지정된 요소를 세트에서 제거한다.
removeAll(Collection<?> c)	지정된 컬렉션에 포함된 요소를 세트에서 모두 제거한다.
retainAll(Collection<?> c)	지정된 컬렉션에 포함된 요소만을 유지하고 나머지 요소는 세트에서 제거한다.
clear()	세트에서 모든 요소를 제거한다.
size()	세트에 있는 요소 수를 반환한다.
isEmpty()	세트가 비어있는지 여부를 반환한다.
iterator()	세트의 요소에 대한 반복자를 반환한다.
toArray()	세트의 모든 요소를 배열로 반환한다.
toArray(T[] a)	세트의 모든 요소를 지정된 배열로 반환한다.

1. HashSet

• 구현: 해시 자료 구조를 사용해서 요소를 저장한다.
• 순서: 요소들은 특정한 순서 없이 저장된다. 즉, 요소를 추가한 순서를 보장하지 않는다.
• 시간 복잡도: HashSet의 주요 연산(추가, 삭제, 검색)은 평균적으로 O(1)시간 복잡도를 가진다.
• 용도: 데이터의 유일성만 중요하고, 순서가 중요하지 않은 경우에 적합하다.
  

2. LinkedHashSet

• 구현: LinkedHashSet은 HashSet에 연결 리스트를 추가해서 요소들의 순서를 유지한다.
• 순서: 요소들은 추가된 순서대로 유지된다. 즉, 순서대로 조회 시 요소들이 추가된 순서대로 반환된다.
• 시간 복잡도: LinkedHashSet도 HashSet과 마찬가지로 주요 연산에 대해 평균 O(1)시간 복잡도를 가진다.
• 용도: 데이터의 유일성과 함께 삽입 순서를 유지해야 할 때 적합하다.
• 참고: 연결 링크를 유지해야 하기 때문에 HashSet보다는 조금 더 무겁다.
  
• LinkedHashSet은 HashSet에 연결 링크만 추가한 것이다.
• HashSet에 LinkedList를 합친 것으로 이해하면 된다.
• 이 연결 링크는 데이터를 입력한 순서대로 연결된다.
  - head(first)부터 순서대로 링크를 따라가면 입력 순서대로 데이터를 순회할 수 있다.
  • 양방향으로 연결된다. (그림에서는 이해를 돕기 위해 화살표는 다음 순서로만 보여주었다. 실제로는 양방향이다.)
• 여기서는 1, 2, 5, 8, 14, 99 순서대로 입력된다. 링크를 보면 1, 2, 5, 8, 14, 99 순서로 연결 되어 있는 것을 확인할 수 있다.
• 이 링크를 first부터 순서대로 따라가면서 출력하면 순서대로 출력할 수 있다.

3. TreeSet

• 구현: TreeSet은 이진 탐색 트리를 개선한 레드-블랙 트리를 내부에서 사용한다.
• 순서: 요소들은 정렬된 순서로 저장된다. 순서의 기준은 비교자(Comparator)로 변경할 수 있다.
• 시간 복잡도: 주요 연산들은 O(log n)의 시간 복잡도를 가진다. 따라서 HashSet보다는 느리다.
• 용도: 데이터들을 정렬된 순서로 유지하면서 집합의 특성을 유지해야 할 때 사용한다. 예를 들어, 범위 검색이나 정렬된 데이터가 필요한 경우에 유용하다. 참고로 입력된 순서가 아니라 데이터 값의 순서이다. 예를 들어 3, 1, 2를 순서대로 입력해도 1, 2, 3 순서로 출력된다. (기본적으로 오름차순 정렬이다)