# 셋 (Set)
정의
Set은 집합이라는 의미를 가지며, 순서가 없고, 중복되는 요소는 없이 오로지 희소한(unique) 값만 저장하는 자료구조입니다.
- 중복을 허용하지 않아서 같은 값이 계속해서 삽입하게 되면, 마지막에 삽입한 값 하나만 저장됩니다.
# Set을 사용해야하는 이유
- 집합과 관련한 문제를 해소해야 할 때
- 중복 처리를 고려해야 할 때
- 중복 처리와 동시에 빠른 조회가 필요할 때
# 자바에서의 Set
- Hash 알고리즘을 이용한 HashSet
- 이진 탐색 트리를 사용하여 오름차순 정렬까지 해주는 TreeSet
- Set에 순서를 부여해주는 LinkedHashSet
일반적으로 HashSet, TreeSet, LinkedHashSet 순으로 빠릅니다.
# HashSet
- Hash 알고리즘 기반으로 동작합니다.
- HashTable 구조를 이용한 HashMap을 이용하여 만들어져 있습니다.
- 입력된 키를 해시 코드로 변환합니다.
- 해시 코드를 인덱스로 한 bucket이라는 array에 해당 인덱스를 찾아 저장합니다.
(여기서 배열 길이가 초과하는 경우에는 길이의 나머지를 구해 링크드 리스트로 추가합니다.)
- index가 아닌 key를 이용하여 데이터 저장과 접근이 필요한 경우 사용합니다.
- 데이터의 크기가 어느 정도 예상되는 경우 사용합니다.
- 삽입 삭제가 빈번할 경우 사용합니다.
import java.util.HashSet;
// Set 생성하기
HashSet<String> texts = new HashSet<>();
// 데이터 삽입하기
set.add("moosong");
// 값 포함여부 확인하기
boolean isExist = set.contains("moosong"); // 있으면 true, 없으면 false
// 데이터 삭제
set.remove("moosong");
// 데이터 출력
for (String value : set) {
System.out.println(value);
}
- HashMap을 이용하여 만들어졌으므로, 저장된 값은 정렬되어 있지 않습니다.
# TreeSet
- 이진트리의 향상된 버전인 Red-Black Tree를 기반으로 만들어집니다.
- Tree 구조를 이용한 TreeMap을 이용하여 만들어져 있습니다.
- 새로운 데이터가 들어오면 루트부터 비교합니다.
- 비교의 결과에 따라 우측, 좌측으로 갈지 결정됩니다.
- 더 이상 비교를 할 수 없을 때까지 반복합니다.
- 추가/삭제는 링크드 리스트 보다 비효율적이지만 검색/정렬은 TreeSet이 더 좋다.
- 저장되는 데이터의 개수가 몇개인지 예상되지 않는 경우 사용합니다.
- 삽입과 삭제가 빈번하지 않을 때 사용합니다.
- 정렬된 값이 필요할 때 사용합니다.
import java.util.TreeSet;
// Set 생성하기
TreeSet<String> texts = new TreeSet<>();
// 데이터 삽입하기
set.add("moosong");
// 값 포함여부 확인하기
boolean isExist = set.contains("moosong"); // 있으면 true, 없으면 false
// 데이터 삭제
set.remove("moosong");
// 데이터 출력
for (String value : set) {
System.out.println(value);
}
- TreeMap을 이용하여 만들어졌으므로, 저장된 값은 오름차순으로 정렬되어 출력할 수 있습니다.
# LinkedHashSet
- LinkedHashSet은 HashSet을 상속하여 만들어진 클래스입니다.
- 다만 내부는 LinkedHashMap을 이용하여 구현되어 있습니다.
- 값의 저장된 순서가 중요할 때 사용합니다.
import java.util.LinkedHashSet;
// Set 생성하기
LinkedHashSet<String> texts = new LinkedHashSet<>();
// 데이터 삽입하기
set.add("moosong");
// 값 포함여부 확인하기
boolean isExist = set.contains("moosong"); // 있으면 true, 없으면 false
// 데이터 삭제
set.remove("moosong");
// 데이터 출력
for (String value : set) {
System.out.println(value);
}
- LinkedHashMap을 이용하기에, 저장된 값은 저장된 순서대로 출력됩니다.
# Set으로 집합 연산하기
# A가 B의 부분집합인가요?
boolean isContainAll = B.containsAll(A);
- 부분집합이면 True, 아니면 False
# x가 A의 원소인가요?
boolean isContain = A.contains(x);
- 원소가 포함되면 True, 아니면 False
# A와 B의 교집합 구하기
TreeSet<String> cloneA = new TreeSet<>(set1);
boolean isModified = cloneA.retainAll(B);
- 반환값은 cloneA 변경 여부를 반환합니다. -> cloneA에 원소가 존재하지 않는 경우를 제외하고는 항상 True를 반환한다고 보면 됩니다.
set.retainAll(collection)
메서드는 원본의 데이터를 변경하므로, 원본 데이터의 손실을 원하지 않는다면 원본을 복사해서 사용해야 합니다.
# A와 B의 합집합 구하기
TreeSet<String> cloneA = new TreeSet<>(set1);
boolean isModified = cloneA.addAll(B);
- 반환값은 cloneA 변경 여부를 반환합니다. -> cloneA에 원소가 존재하지 않는 경우를 제외하고는 항상 True를 반환한다고 보면 됩니다.
set.addAll(collection)
원본의 데이터를 변경하므로, 원본 데이터의 손실을 원하지 않는다면 원본을 복사해서 사용해야 합니다.
# A와 B의 차집합 구하기
TreeSet<String> cloneA = new TreeSet<>(set1);
boolean isModified = cloneA.removeAlll(B);
- 반환값은 cloneA 변경 여부를 반환합니다. -> cloneA에 원소가 존재하지 않는 경우를 제외하고는 항상 True를 반환한다고 보면 됩니다.
set.removeAlll(collection)
메서드는 원본의 데이터를 변경하므로, 원본 데이터의 손실을 원하지 않는다면 원본을 복사해서 사용해야 합니다.
# 참고자료
- 주홍철.면접을 위한 CS 전공지식 노트.서울:길벗,2022.
- nemne (opens new window)
- taeha7b (opens new window)
- codelatte (opens new window)
- st-lab (opens new window)