[Java/김영한] Set

https://inf.run/sDjcZ

김영한의 실전 자바 - 중급 2편| 김영한 - 인프런 강의

이 링크를 통해 구매하시면 제가 수익을 받을 수 있어요.

 

 

자바가 제공하는 Set

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

 

 

Set 인터페이스

 

 

자바의 `Set` 인터페이스는 `java.util` 패키지의 컬렉션 프레임워크에 속하는 인터페이스 중 하나이다. 수학적 집합 개념을 구현한 것으로, 순서를 보장하지 않으며, 특정 요소가 집합에 있는지 여부를 확인하는데 최적화되어 있다.

 

`Set` 인터페이스는 `Hashset`, `LinkedHashSet`, `TreeSet` 등의 여러 구현 클래스를 가지고 있다.

 

 

주요 메서드

메서드	설명
`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)`	세트의 모든 요소를 지정된 배열로 반환한다.

 

지금부터 `Set`의 주요 구현체를 하나씩 알아보자

---

HashSet

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

• `hashCode()`, `equals()`를 모두 사용한다.

---

LinkedHashSet

• 구현: `LinkedHashSet`은 `HashSet`에 연결 리스트를 추가해서 요소들의 순서를 유지한다.
• 순서: 요소들은 추가한 순서대로 유지된다. 즉, 순서대로 조회 시 요소들이 추가된 순서대로 반환된다.
• 시간 복잡도: 주요 연산에 대해 평균 `O(1)` 시간 복잡도를 가진다.
• 용도: 데이터의 유일성과 함께 삽입 순서를 유지해야 할 때 적합하다.
• 참고: 연결 링크를 유지해야 하기 때문에 `HashSet` 보다는 조금 무겁다.

• `LinkedHashSet`은 `HashSet`에 연결 링크만 추가한 것이다.
  • `HashSet`에 `LinkedList`를 합친 것으로 이해하면 된다.
• 이 연결 링크는 데이터를 입력한 순서대로 연결된다.
  • `head(first)`부터 순서대로 링크를 따라가면 입력 순서대로 데이터를 순회할 수 있다.
  • 양방향으로 연결된다. (그림은 이해를 돕기 위해 다음만 보여줌)
• 링크를 보면 입력한 순서대로 연결되어 있는 것을 확인할 수 있다. (1, 2, 5, 8, 14, 99)
• 이 링크를 `first`부터 순서대로 따라가면서 출력하면 순서대로 출력할 수 있다.

---

TreeSet

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

 

 

트리 구조

• 트리는 부모 노드와 자식 노드로 구성된다.
  • 가장 높은 조상을 루트(root)라 한다. 
• 자식이 2개까지 올 수 있는 트리를 이진 트리라 한다.
  • 노드의 왼쪽 자손은 더 작은 값을 가지고, 오른쪽 자손은 더 큰 값을 가지는 것을 이진 탐색 트리라 한다.
• `TreeSet`은 이진 탐색 트리를 개선한 레드-블랙 트리를 사용한다. (기본 개념은 비슷하다.)

 

 

트리 구조 구현

 

class Node {
    Object item;
    Node left;
    Node right; 
}

• 트리 구조는 왼쪽, 오른쪽 노드를 알고 있으면 된다.

 

 

이진 탐색 트리 - 입력 예시

이진 탐색 트리의 핵심은 데이터를 입력하는 시점에 정렬해서 보관한다는 점이다. 작은 값은 왼쪽에 큰 값은 오른쪽에 저장하면 된다.

 

 

데이터를 10, 5, 15, 1, 6, 11, 16 순서대로 입력한다고 가정해보자.

• 16은 10보다 크다. 따라서 오른쪽으로 찾아간다. 16은 15보다 크다. 따라서 오른쪽에 저장된다.

 

 

 

 

이진 탐색 트리 - 검색

 

숫자 35를 검색한다고 가정해보자. 

1. 루트인 20과 비교한다. 35가 더 크므로 오른쪽으로 찾아간다.
2. 40과 35를 비교한다. 35가 더 작으므로 왼쪽으로 찾아간다.
3. 30과 35를 비교한다. 35가 더 크므로 오른쪽으로 찾아간다.
4. 노드에 있는 값을 비교한다. 35와 같으므로 35를 찾는다.

데이터가 총 15개인데 4번의 계산으로 필요한 결과를 얻을 수 있다. 이것은 `O(n)`인 리스트의 검색보다는 빠르고, `O(1)`인 해시의 검색보다는 느리다.

 

데이터의 크기가 늘어나도 늘어난 만큼 한 번의 계산에 절반을 날려버리기 때문에, `O(n)`과 비교해서 데이터의 크기가 클수록 효과적이다. 이것을 수학으로 `log_2(n)`으로 표현한다. 빅오 표기법에서는 상수를 사용하지 않으므로 단순히 `O(log n)`로 표현한다.

 

 

이진 탐색 트리 - 성능 

이진 탐색 트리의 검색, 삽입, 삭제의 평균 성능은 `O(log n)`이다. 하지만 트리의 균형이 맞지 않으면 최악의 경우 O(n)의 성능이 나온다.

 

만약 데이터를 1, 5, 6, 10, 15 순서대로 입력했다고 가정해보자.

• 이렇게 오른쪽으로 치우치게 되면, 결과적으로 15를 검색했을 때 데이터의 수인 5만큼 검색해야 한다.
• 따라서 이런 최악의 경우, `O(n)`의 성능이 나오게 된다.

 

 

이진 탐색 트리 - 개선

위와 같은 문제를 해결하기 위한 다양한 해결 방안이 있는데 트리의 균형이 너무 깨진 경우 동적으로 균형을 다시 맞추는 것이다.

• 앞서 중간에 있는 6을 기준으로 다시 정렬한다.
• AVL 트리, 레드-블랙 트리 같은 균형을 맞추는 다양한 알고리즘이 존재한다.
• 자바의 `TreeSet`은 레드-블랙 트리를 사용해서 균형을 지속해서 유지한다. 따라서 최악의 경우에도 `O(log n)`의 성능을 제공한다. 

 

이진 탐색 트리 - 순회

• 이진 탐색 트리는 데이터의 값을 기준으로 정렬해서 보관한다. 따라서 정렬된 순서로 데이터를 차례로 조회할 수 있다.
• 데이터를 차례로 순회하려면 중위 순회라는 방법을 사용하면 된다. 왼쪽 서브트리를 방문한 다음, 현재 노드를 처리하고, 마지막으로 오른쪽 서브트리를 방문한다. 
  • 이 방식은 이진 탐색 트리의 특성상, 노드를 오름차순으로 방문한다.

중위 순회 순서

쉽게 이야기해서 자신의 왼쪽 모든 노드를 처리하고, 자신의 노드를 처리하고, 자신의 오른쪽 노드를 처리하는 방식이다.

• 10의 기준에서 왼쪽 서브트리 방문
  • 5의 기준에서 왼쪽 서브트리 방문
    • 1을 출력
  • 5 자신을 출력
  • 5의 기준으로 오른쪽 서브트리 방문
    • 6을 출력
• 10 자신을 출력
• 10의 기준에서 오른쪽 서브트리 방문
  • 15의 기준에서 왼쪽 서브트리 방문
    • 11을 출력
  • 15 자신을 출력
  • 15 기준으로 오른쪽 서브트리 방문
    • 16을 출력

 

순서대로 1, 5, 6, 10, 11, 15, 16이 출력된 것을 확인할 수 있다.

---

Set의 최적화

자바가 제공하는 `HashSet`은 다음과 같은 최적화를 추가로 진행한다.

• 해시 기반 자료 구조를 사용하는 경우 통계적으로 입력한 데이터의 수가 배열의 크기를 75% 정도 넘어가면 해시 인덱스가 자주 충돌한다. 따라서 75%가 넘어가면 성능이 떨어지기 시작한다.
  • `O(n)`으로 성능이 좋지 않아진다.
• 하지만 데이터가 동적으로 계속 추가되기 때문에 적절한 배열의 크기를 정하는 것은 어렵다.

 

자바의 `HashSet`은 데이터의 양이 배열 크기의 75%를 넘어가면 배열의 크기를 2배로 늘리고 2배 늘어난 크기를 기준으로 모든 요소에 해시 인덱스를 다시 적용한다. 이 과정을 재해싱(rehashing)이라 한다. 해시 인덱스를 다시 적용하는 시간이 걸리지만, 결과적으로 해시 충돌이 줄어든다.

 

자바 `HashSet`의 기본 크기는 `16`이다.

 

 

정리

실무에서는 `Set`이 필요한 경우 `HashSet`을 가장 많이 사용한다. 그리고 입력 순서 유지, 값 정렬의 필요에 따라서 `LinkedHashSet`, `TreeSet`을 선택하면 된다.