자바가 제공하는 Set - HashSet, LinkedHashSet
Set은 중복을 허용하지 않고, 순서를 보장하지 않는 자료 구조이다.
Set 인터페이스
자바의 Set 인터페이스는 java.util 패키지의 컬렉션 프레임워크에 속하는 인터페이스 중 하나이다.
Set 인터페이스는 중복을 허용하지 않는 유일한 요소의 집합을 나타낸다. 즉 어떤 요소도 Set 내에 두번 이상 나타날 수 없다.
Set은 집합을 생각하면 이해하기 편하다. 순서를 보장하지 않으며 특정 요소가 집합에 있는지 여부를 확인하는데 최적화되어있다.
Set 인터페이스는 HashSet, LinkedHashSet, TreeSet 등의 여러 구현 클래스를 가지고 있다.
Set 인터페이스의 주요 메서드는 검색을 통해 확인하자. (거의 비슷하지만 다른 기능이 조금 더 있다)
1. HashSet
(이전에 공부한 MyHashSet이 HashSet이다.)
- 해시 자료 구조를 사용해서 요소를 저장한다.
- 요소들은 특정한 순서 없이 저장된다. 즉 요소를 추가한 순서를 보장하지 않는다. (해시 코드가 다르게 나오니까)
- 주요 연산은 평균적으로 O(1)의 시간 복잡도를 가진다.
- 데이터의 유일성만이 중요하고, 순서가 중요하지 않을 때 적합하다.
2. LinkedHashSet
- LinkedHashSet은 HashSet에 연결 리스트를 추가해서 요소들의 순서를 유지한다.
- 요소들은 추가 된 순서대로 유지된다. 즉 순서대로 조회시 요소들이 추가된 순서대로 반환된다.
- HashSet과 마찬가지로 주요 연산은 평균 O(1)의 시간복잡도를 가진다.
- 데이터의 유일성과 함께 삽입 순서를 유지해야 할 때 적합하다.
- 연결 링크를 유지해야하기 때문에 HashSet보다 조금 무겁다. (하지만 큰 지장은 없음)
LinkedHashSet은 HashSet에 연결 링크만 추가한 것이다. (HashSet에 노드만 추가했다고 이해하자)
데이터를 입력한 순서대로 연결되는 것을 확인할 수 있다. 노드를 이해했다면 그림을 보고 충분히 이해할 수 있다.
설명 생략!
자바가 제공하는 Set - TreeSet
TreeSet
- TreeSet은 이진 탐색 트리를 개선한 레드-블랙 트리를 내부에서 사용한다.
- 요소들은 정렬된 순서로 저장된다. 순서의 기준은 비교자(Comparator)로 변경할 수 있다.
- 주요 연산들은 O(log n)의 시간 복잡도를 가진다. 따라서 HashSet보다는 느리다.
- 데이터를 정렬된 순서로 유지하면서 집합의 특성을 유지할 때 사용한다. 예를 들어 범위 검색이나 정렬된 데이터가 필요한 경우에 사용.
참고로 입력 순서가 아니라 데이터 값의 순서이다. (3, 1, 2 입력 -> 1, 2, 3 출력)
트리 구조
TreeSet을 이해하려면 트리 구조를 먼저 알아야 한다.
- 트리는 부모 노드와 자식 노드로 구성된다.
- 가장 높은 조상을 루트(root)라 한다.
- 자식이 2개까지 올 수 있는 트리를 이진 트리라고 한다.
- 노드의 왼쪽은 더 작은 값을 가지고, 오른쪽 자손은 더 큰 값을 가지는 것을 이진 탐색 트리라고 한다.
- TreeSet은 이진 탐색 트리를 개선한 레드-블랙 트리를 사용한다. 기본 개념은 비슷하다.
- 트리 구조는 왼쪽, 오른쪽 노드를 알 고 있으면 된다.
- 이진 탐색 트리의 핵심은 데이터를 입력하는 시점에 정렬해서 보관한다는 점이다.
- 왼쪽엔 작은 값, 오른쪽엔 큰값을 저장하면 된다.
10보다 작은 5는 왼쪽, 10보다 큰 15는 오른쪽에 저장 되었다.
또 5보다 작은 1은 왼쪽, 5보다 큰 6은 오른쪽, 15보다 작은 11은 왼쪽, 15보다 큰 16은 오른쪽에 저장된다.
이진 탐색 트리 - 검색
총 15개의 데이터가 들어있다. 여기서 35를 검색해보자
1. 루트인 20과 35를 비교한다. 35가 더 크므로 오른쪽 노드로 찾아간다.
2. 35와 40을 비교한다. 35가 더 작으므로 왼쪽 노드로 찾아간다.
3. 35와 30을 비교한다. 30보다 크므로 오른쪽 노드로 찾아간다.
4. 노드에 있는 값을 비교한다. 35와 35가 같으므로 35를 찾는다.
데이터가 총 15개인데, 4번의 계산으로 원하는 결과를 얻을 수 있었다. O(n)인 리스트보다 빠르고, O(1)인 해시 검색보단 느리다.
- 리스트는 O(n), 15번의 연산 필요
- 해시 검색은 O(1), 1번의 연산 필요
이진 탐색 트리의 핵심은 한번에 절반을 날린다는 점이다.
- 2개의 데이터 -> 2로 1번 나누기. log2(2) = 1
- 4개의 데이터 -> 2로 2번 나누기. log2(4) = 2
- 8개의 데이터 -> 2로 3번 나누기. log2(8) = 3
...
- 64개의 데이터 -> 2로 6번 나누기. log2(64) = 6
- 1024개의 데이터 -> 2로 10번 나누기. log2(1024) = 10
1024개의 데이터를 10번의 계산으로 원하는 결과를 찾을 수 있다. 데이터의 크기가 늘어나도 늘어난 만큼 한번의
계산에 절반을 날려버리기 때문에, O(n)과 비교해서 데이터의 크기가 클 수록 효과적이다.
단순하게 생각하면 로그는 쉽게 이야기해서 2로 몇번 나누어서 1에 도달할 수 있는지 계산하면 된다.
이진 탐색 트리와 성능
이진 탐색트리의 검색, 삽입, 삭제의 평균 성능은 O(log n)이다. 하지만 트리의 균형이 맞지 않으면 O(n)이 나온다.
이렇게 오른쪽으로 치우치게 되면, 결과적으로 15를 검색했을 때 5번의 연산 O(n)의 성능이 나온다.
이런 문제를 해결하기 위해서 트리의 균형이 깨진 경우 동적으로 균형을 다시 맞추는것이다.
자바의 TreeSet은 레드-블랙 트리를 사용해서 균형을 지속적으로 유지한다. 따라서 최악의 경우에도 O(log n)의 성능이 나온다.
이진 탐색 트리 - 순회
이진 탐색 트리의 핵심은 입력 순서가 아니라, 데이터의 값을 기준으로 정렬해서 보관한다는 것이다.
따라서 정렬된 순서로 데이터를 차례대로 조회할 수 있다.
데이터를 차례대로 순회하려면 중위 순회 방법을 사용하면 된다. 왼쪽 서브트리를 방문 -> 현재 노드 처리 -> 오른쪽 서브트리 방문으로
작동한다. 이 방법은 이진 탐색 트리의 특성상 노드의 오름차순(숫자가 점점 커짐)으로 방문한다.
중위 순회 순서
1. 10의 기준에서 왼쪽 서브 트리 방문
2. 5의 기준에서 왼쪽 서브트리 방문 -> 1 출력
3. 5 자신 출력
4. 5의 기준에서 오른쪽 서브트리 방문 -> 6 출력
5. 10 자신 출력
6. 10 기준에서 오른쪽 서브트리 방문
... 반복
마지막으로 16 출력
기본적인 트리 구조 이론이다. 더 자세히 알고 싶으면 자료 구조와 알고리즘을 따로 학습하자.
자바의 Set - 예제
package collection.set.javaset;
import java.util.*;
public class JavaSetMain {
public static void main(String[] args) {
run(new HashSet<>());
run(new LinkedHashSet<>());
run(new TreeSet<>());
}
private static void run(Set<String> set) {
System.out.println("set = " + set.getClass());
set.add("C");
set.add("B");
set.add("A");
set.add("1");
set.add("2");
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
System.out.println();
}
}
iterator()를 호출하면 컬렉션을 반복해서 출력할 수 있다.
- iterator.hashNext() : 다음 데이터가 있는지 확인
- iterator.next() : 다음 데이터를 반환
HashSet : 입력 순서를 보장하지 않음 O(1)
LinkedHashSet : 입력순서를 보장 O(1), 다만 해시셋보다 조금 느림 (별 차이 없음)
TreeSet : 데이터 값을 기준으로 정렬
자바의 Set - 최적화
자바의 HashSet은 MyHashSet의 기능과 거의 같지만 다음과 같은 최적화를 추가로 진행한다.
재해싱(rehashing)
- 해시 기반 자료 구조를 사용하는 경우 통계적으로 입력한 데이터 수가 배열의 75%를 넘어가면 해시 인덱스가 자주 충돌한다.
이를 방지하기 위해 재해싱(rehashing)을 하는데, 배열의 크기를 2배로 늘리고 늘어난 크기를 기준으로 모든 요소에 해시 인덱스를
재적용한다. 해시 인덱스를 다시 적용하는 시간은 걸리겠지만, 해시 충돌이 줄어들게 된다.
실무에서는 Set이 필요한 경우 hashSet을 자주 사용한다. 그리고 입력 순서 유지, 값 정렬의 필요에 따라서
LinkedHashSet, TreeSet을 선택하면 된다.
'Java' 카테고리의 다른 글
| 컬렉션 프레임워크 - Map, Stack, Queue (1) | 2025.01.21 |
|---|---|
| 컬렉션 프레임워크 - HashSet (0) | 2025.01.18 |
| 컬렉션 프레임워크 - 해시(Hash) (1) | 2025.01.16 |
| 컬렉션 프레임워크 - List (1) | 2025.01.13 |
| 컬렉션 프레임워크 - LinkedList (0) | 2025.01.03 |