🎡 자바가 제공하는 Set
Set 자료 구조는 알다시피 중복을 허용하지 않고, 순서를 보장하지 않는 자료 구조다.
Collection 인터페이스는 자바에서 다양한 데이터 그룹을 다루기 위한 메서드를 정의하고 있다. 그 하위에 Set 인터페이스는 java.util 패키지의 컬렉션 프레임워크에 속하는 인터페이스 중 하나다. 이 Set 인터페이스는 다시 HashSet, LinkedHashSet, TreeSet 등의 여러 구현 클래스로 나뉜다.
<Set 인터페이스의 주요 메서드>
| 메서드 | 설명 |
|---|---|
add(E e) | 지정된 요소를 Set에 추가한다. 이미 존재하는 경우에는 추가하지 않는다. |
addAll(Collection<? extends E> c) | 지정된 컬렉션의 모든 요소를 Set에 추가한다. |
contains(Object o) | Set가 지정된 요소를 포함하고 있는지 여부를 반환한다. |
containsAll(Collection<?> c) | Set가 지정된 컬렉션의 모든 요소를 포함하고 있는지 여부를 반환한다. |
remove(Object o) | 지정된 요소를 Set에서 제거한다. |
removeAll(Collection<?> c) | 지정된 컬렉션에 포함된 요소를 Set에서 모두 제거한다. |
retainAll(Collection<?> c) | 지정된 컬렉션에 포함된 요소만을 유지하고 나머지 요소는 Set에서 제거한다. |
clear() | Set에서 모든 요소를 제거한다. |
size() | Set에 있는 요소의 수를 반환한다. |
isEmpty() | Set가 비어 있는지 여부를 반환한다. |
iterator() | Set의 요소에 대한 반복자를 반환하다. |
toArray() | Set의 모든 요소를 배열로 반환한다. |
toArray(T[] a) | Set의 모든 요소를 지정된 배열로 반환한다. |
HashSet은 앞서 살펴 보았으니 LinkedHashSet, TreeSet에 대해 하나씩 살펴보자.
📚 LinkedHashSet
LinkedHashSet은 HashSet 안에 LinkedList를 추가해서 요소들의 순서를 유지한다. 주요 연산에 대해 O(1)의 성능을 가졌고, 데이터의 중복을 허락하지 않고, 삽입 순서를 유지해야 할 때 사용하면 적합하다. 연결 링크를 유지해야 하므로 HashSet보다는 조금 더 무겁다.
위 그림처럼 HashSet에 노드를 쑤셔 넣은 느낌이다. head(first)부터 시작해서 순서대로 연결 링크를 따라가면 입력된 순서대로 데이터를 순회할 수 있다.
🎄 TreeSet
TreeSet은 이진 탐색 트리를 개선한 레드-블랙 트리를 내부에서 사용한다. 요소들은 정렬된 순서로 저장된다. 시간 복잡도는 HashSet보다 조금 느린 O(log n)이다. 보통 데이터들을 정렬된 순서로 유지하면서 집합의 특성을 유지해야 할 때 사용한다.
🤔 트리 구조?
트리는 보다시피 나무를 거꾸로 매달아 놓은 것 같은 느낌으로, 부모 노드와 자식 노드로 구성된다. 가장 높은 조상(10)을 “루트” 라고 한다. 위 그림처럼 자식 노드가 2개까지 올 수 있는 트리를 이진 트리라고 한다. 왼쪽 서브 트리는 더 작은 값을 가지고, 오른쪽 서브 트리는 더 큰 값을 가지는 특징까지 더해져 이진 탐색 트리라고 한다.
앞서 연결 리스트에서 이전 노드와 이후 노드를 알고 있는 것처럼 트리 구조는 왼쪽과 오른쪽 노드를 알고 있으면 그만이다. 이진 탐색 트리의 핵심은 데이터를 입력하는 시점에 정렬해서 보관한다는 점이다. 루트보다 작은 값이 들어오면 왼쪽으로, 루트보다 큰 값이 들어오면 오른쪽으로 저장하면 된다. 검색할 때도 비슷하게 하면 된다. 아래 예시를 보자.
숫자 35를 검색한다고 하면,
- 루트 20과 비교했을 때 35가 더 크므로 오른쪽 서브 트리로 간다.
- 루트 40과 비교했을 때 35가 더 작으므로 왼쪽 서브 트리로 간다.
- 루트 30과 비교했을 때 35가 더 크므로 오른쪽 서브 트리로 간다.
- 숫자 35를 찾는데 성공했다.
이처럼 데이터의 개수가 총 15개인데 단 4번의 계산으로 원하는 값을 찾는데 성공한 것이다. 이 점이 이진 탐색 트리의 핵심이다. 한번에 절반 가량의 계산을 날리는 셈이다.
⭕ 이진 탐색 트리의 Big-O
데이터의 크기가 늘어나도 늘어난 만큼 한 번의 계산으로 절반을 날려버리기 때문에 O(n)과 비교해서 데이터의 크기가 클수록 효과적이다. 이진 탐색 트리의 검색, 삽입, 삭제의 평균 성능은 O(log n)이다. 트리의 균형이 맞지 않으면 최악의 경우 O(n)까지 내려갈 수 있다. 아래 그림처럼 극단적으로 치우쳐져 있으면 15라는 값을 찾기 위해 데이터의 수만큼 검색을 수행해야 할 수도 있다는 것이다.
이런 문제를 해결하기 위해 다양한 해결책이 제시되었는데 그 중 하나가 위와 같이 트리의 균형이 심하게 깨진 경우, 동적으로 균형을 다시 맞추는 방법이다. 위의 예시에 적용하자면, 중간에 있는 값인 6을 기준으로 다시 정렬하면 된다.
자바의 TreeSet의 경우, 레드-블랙 트리를 사용해서 균형을 계속해서 유지한다. 따라서 최악의 경우라 하더라도 O(log n)의 성능을 보장한다.
이진 탐색 트리의 핵심은 앞서 말했듯이, 데이터의 값을 기준으로 정렬해서 보관한다는 것이었다. 따라서 정렬된 순서로 데이터를 순회하면서 조회할 수 있는데, 차례대로 수행하려면 중위 순회라는 방법을 사용하면 된다. 왼쪽 서브 트리를 먼저 방문하고, 현재 노드를 거쳐, 오른쪽 서브 트리를 방문하는 방법이다. 이제 실제 HashSet, LinkedHashSet, TreeSet을 이용한 순회 방식을 코드로 직접 확인해보자.
📝 예제
HashSet, LinkedHashSet, TreeSet 모두 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를 사용한 컬렉션 반복 출력
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
System.out.println();
}
}
/*
set = class java.util.HashSet
A 1 B 2 C
set = class java.util.LinkedHashSet
C B A 1 2
set = class java.util.TreeSet
1 2 A B C
*/
🤔 자바의 HashSet 최적화
자바에서의 HashSet은 해시 기반 자료 구조를 사용하는 경우에, 통계적으로 입력한 데이터의 수가 배열의 크기를 75% 정도 넘어가게 되면 해시 충돌이 자주 발생한다. 해시 충돌로 인해 충돌된 해시 인덱스 안에 있는 데이터를 다 뒤져야 하기 때문에 성능이 O(n)으로 좋지 않다. 데이터는 동적으로 계속해서 추가되기 때문에 초기에 적절한 배열의 크기를 정하는 것은 사실상 불가능하다. 따라서 HashSet은 데이터의 양이 배열 크기의 75% 정도를 넘어가면 배열의 크기를 2배로 늘리고, 그 늘어난 크기를 기준으로 모든 요소에 대해 다시 해시 인덱스를 계산한다. 계산하는 만큼의 시간은 늘어나겠지만, 결과적으로 해시 충돌이 줄어든다.
위 그림에서 데이터의 개수는 총 4개로 배열 크기의 80%를 차지하고 있다. 따라서 해시 인덱스의 충돌 가능성이 높아진 상태다. 이때 배열의 크기를 2배 증가시키고, 그에 맞게 다시 해시 인덱스를 계산한다.
보다시피 모든 데이터의 해시 인덱스를 커진 배열에 맞춰 다시 계산했다. 이 과정을 재해싱(re-hashing)이라고 한다. 결과적으로 해시 충돌이 줄어 들었고, 데이터가 균일하게 분포되어 있는 것을 확인할 수 있다. 여기서 데이터가 계속해서 추가되다가 다시 현재 배열의 크기의 75% 정도 차지하게 된다면 재해싱 작업을 또 수행한다. 마지막으로 실무에서는 Set이 필요한 경우, HashSet을 가장 많이 사용한다. 입력 순서를 유지하고 싶거나, 값 정렬을 해야 할 상황일 때 LinkedHashSet, TreeSet을 선택하면 된다.
