8. 컬렉션 프레임워크 - Set

자바가 제공하는 Set1 - HashSet, LinkedHashSet

컬렉션 프레임워크 - Set

Collection 인터페이스

Collection 인터페이스는 java.util 패키지의 컬렉션 프레임워크의 핵심 인터페이스 중 하나이다. 이 인터페이스는 자바에서 다양한 컬렉션, 즉 데이터 그룹을 다루기 위한 메서드를 정의한다. Collection 인터페이스는 List, Set, Queue 와 같은 다양한 하위 인터페이스와 함께 사용되며, 이를 통해 데이터를 리스트, 세트, 큐 등의 형태로 관리할 수 있다.

Set 인터페이스

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

Set 인터페이스는 HashSet, LikedHashSet, TreeSet 등의 여러 구현 클래스를 가지고 있으며, 각 클래스는 Set 인터페이스를 구현하며 각각의 특성을 가지고 있다.

1. HashSet

• 구현: 해시 자료 구조를 사용해서 요소를 저장한다.

• 순서: 요소들은 특정한 순서 없이 저장된다. 즉, 요소를 추가한 순서를 보장하지 않는다.

• 시간 복잡도: HashSet 의 주요 연산(추가, 삭제, 검색)은 평균적으로 O(1) 시간 복잡도를 가진다.

• 용도: 데이터의 유일성만 중요하고, 순서가 중요하지 않은 경우에 적합하다.

HashSet 구현

2. LinkedHashSet

• 구현: LinkedHashSet 은 HashSet 에 연결 리스트를 추가해서 요소들의 순서를 유지한다.

• 순서: 요소들은 추가된 순서대로 유지된다. 즉, 순서대로 조회 시 요소들이 추가된 순서대로 반환된다.

• 시간 복잡도: LinkedHashSet 도 HashSet 과 마찬가지로 주요 연산에 대해 평균 O(1) 시간 복잡도를 가진다.

• 용도: 데이터의 유일성과 함께 삽입 순서를 유지해야 할 때 적합하다.

• 참고: 연결 링크를 유지해야 하기 때문에 HashSet 보다는 조금 더 무겁다.

LinkedHashSet 구현

• LinkedHashSet은 HashSet에 연결 링크만 추가한 것이다.

• HashSet에 LinkedList를 합친 것으로 이해하면 된다.

• 이 연결 링크는 데이터를 입력한 순서대로 연결된다.

  • head(first) 부터 순서대로 링크를 따라가면 입력 순서대로 데이터를 순회할 수 있다.

  • 양방향으로 연결된다. (그림에서는 이해를 돕기 위해 화살표는 다음 순서로만 보여주었다. 실제로는 양방향이다.)

• 여기서는 1, 2, 5, 8, 14, 99 순서대로 입력된다. 링크를 보면 1, 2, 5, 8, 14, 99 순서로 연결 되어 있는 것을 확인할 수 있다.

• 이 링크를 first 부터 순서대로 따라가면서 출력하면 순서대로 출력할 수 있다.

자바가 제공하는 Set2 - TreeSet

3. TreeSet

• 구현: TreeSet 은 이진 탐색 트리를 개선한 레드-블랙 트리를 내부에서 사용한다.

  • 이진 탐색 트리 계산의 핵심은 한번에 절반을 날린다는 점이다.

• 순서: 요소들은 정렬된 순서로 저장된다. 순서의 기준은 비교자( Comparator )로 변경할 수 있다.

• 시간 복잡도: 주요 연산들은 O(log n) 의 시간 복잡도를 가진다. 따라서 HashSet 보다는 느리다.

• 용도: 데이터들을 정렬된 순서로 유지하면서 집합의 특성을 유지해야 할 때 사용한다.

  • 예를 들어, 범위 검색이나 정렬된 데이터가 필요한 경우에 유용하다. (참고로 입력된 순서가 아니라 데이터 값의 순서이다)

  • 예를 들어 3, 1, 2 를 순서대로 입력해도 1, 2, 3 순서로 출력된다.

이진 탐색 트리와 성능

이진 탐색 트리의 검색, 삽입, 삭제의 평균 성능은 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을 출력한다.

자바가 제공하는 Set3 - 예제

package collection.set.javaset;

import java.util.*;

public class JavaSetMain {

    public static void main(String[] args) {
        run(new HashSet<String>());
        run(new LinkedHashSet<String>());
        run(new TreeSet<String>());
    }

    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();
    }
}

참고 - TreeSet 의 정렬 기준

TreeSet 을 사용할 때 데이터를 정렬하려면 크다, 작다라는 기준이 필요하다. 1, 2, 3이나 "A", "B", "C" 같은 기본 데이터는 크다 작다라는 기준이 명확하기 때문에 정렬할 수 있다.

하지만 우리가 직접 만든 Member 와 같은 객체는 크다 작다는 기준을 어떻게 알 수 있을까?

이런 기준을 제공하려면 Comparable, Comparator 인터페이스를 구현해야 한다. 이 부분은 뒤에서 설명한다.

자바가 제공하는 Set4 - 최적화

자바 HashSet 과 최적화

자바의 HashSet 은 우리가 직접 구현한 내용과 거의 같지만 다음과 같은 최적화를 추가로 진행한다.

최적화

• 해시 기반 자료 구조를 사용하는 경우 통계적으로 입력한 데이터의 수가 배열의 크기를 75% 정도 넘어가면 해시 인덱스가 자주 충돌한다. 따라서 75%가 넘어가면 성능이 떨어지기 시작한다.

  • 해시 충돌로 같은 해시 인덱스에 들어간 데이터를 검색하려면 모두 탐색해야 한다. 따라서 성능이 O(n)으로 좋지 않다.

• 하지만 데이터가 동적으로 계속 추가되기 때문에 적절한 배열의 크기를 정하는 것은 어렵다.

• 자바의 HashSet 은 데이터의 양이 배열 크기의 75%를 넘어가면 배열의 크기를 2배로 늘리고 2배 늘어난 크기를 기준으로 모든 요소에 해시 인덱스를 다시 적용한다.

• 해시 인덱스를 다시 적용하는 시간이 걸리지만, 결과적으로 해시 충돌이 줄어든다. 자바 HashSet 의 기본 크기는 16 이다.

정리

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