Set

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

 

Set : 중복 X, 순서 X

Collection 인터페이스는 List, Set, Queue와 같은 다양한 하위 인터페이스와 함께 사용된다.

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

Set 구현체는 순서를 보장할 수도, 보장하지 않을 수도 있다.

 

Set 인터페이스의 주요 메서드

메서드	설명
add(e)	요소 추가 (중복 X)
contains(o)	포함 여부 확인
remove(o)	요소 제거
clear()	전체 삭제
size()	요소 개수

 

HashSet

• 순서 보장 X
• 시간 복잡도 : O(1)
• hashCode(), equals() 모두 사용한다.

 

LinkedHashSet

• HashSet에 연결 리스트를 추가하여 요소들의 순서를 유지한다.
• HashSet에 LinkedList를 합친 것으로 이해하면 된다.
• 시간 복잡도 : O(1)
• 연결 링크를 유지해야 하기 때문에 HashSet 보다 조금 더 무겁다. 

• head(first) 부터 순서대로 링크를 따라가면 입력 순서대로 데이터를 순회할 수 있다.
• 양방향으로 연결된다.
• 여기서는 1, 2, 5, 8, 14, 99 순서대로 입력된다.

 

2. 자바가 제공하는 Set2 - TreeSet

TreeSet

• 이진 탐색 트리를 개선한 레드-블랙 트리를 내부에서 사용한다.
• 요소들은 정렬된 순서로 저장된다. 순서의 기준은 비교자(Comparator)로 변경할 수 있다.
• 시간 복잡도 : O(log n) (HashSet 보다 느림)
• ex) 3, 1, 2 순서로 입력하면 1, 2, 3 순서로 출력된다.

 

트리 구조

 

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

 

트리 구조의 구현

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

 

이진 탐색 트리

• 이진 탐색 트리의 핵심은 데이터를 입력하는 시점에 정렬해서 보관한다는 점이다.
• 그리고 작은 값을 왼쪽에, 큰 값은 오른쪽에 저장한다.
• 검색 시에는 O(n)인 리스트의 검색 보다는 빠르고, O(1)인 해시의 검색 보다는 느리다.
• 이진 탐색 트릭 계산의 핵심은 한 번에 절반을 날리므로, O(n)과 비교했을 때 데이터의 양이 많을수록 효율적이다.
• 트리의 균형이 맞지 않으면 최악의 경우 O(n)의 성능이 나올 수 있다.
• 자바의 TreeSet은 레드-블랙 트리(균형을 맞추는 알고리즘)를 사용하여 균형을 유지하므로,
  최악의 경우에도 O(log n)의 성능을 제공한다.
• 이진 탐색 트리에서 정렬된 순서로 데이터를 차례대로 순회하려면 중위 순회라는 방법을 사용하면 된다.

이진 탐색 트리 - 중위 순회

중위 순회 : 자신의 왼쪽 모든 노드 처리 -> 자신의 노드 처리 -> 자신의 오른쪽 모든 노드 처리

• 10 기준 왼쪽 서브트리 방문
  • 5 기준 왼쪽 서브트리 방문
    • 1 출력
  • 5 출력
  • 5 기준 오른쪽 서브트리 방문
    • 6 출력
• 10 출력
• 10 기준 오른쪽 서브트리 방문
  • 15 기준 왼쪽 서브트리 방문
    • 11 출력
  • 15 출력
  • 15 기준 오른쪽 서브트리 방문
  • 16 출력

순서대로 1 -> 5 -> 6 -> 10 -> 11 -> 15 -> 16 출력됨.

 

3. 자바가 제공하는 Set3 - 예제

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

• HashSet, LinkedHashSet, TreeSet 모두 Set 인터페이스를 구현하기 때문에 구현체를 변경하면서 실행할 수 있다.
• HashSet : 입력한 순서 보장 X
• LinkedHashSet : 입력한 순서 보장 O
• TreeSet : 데이터 값을 기준으로 정렬

 

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

자바의 HashSet은 최적화가 진행된다.

데이터의 양이 배열 크기의 75%를 넘어가면,

배열의 크기를 2배로 늘리고 2배 늘어난 크기를 기준으로 모든 요소에 해시 인덱스를 다시 적용한다.(재해싱, rehashing)

이렇게 하면, 인덱스 충돌 가능성이 줄어들어 성능 저하를 피할 수 있다.

 

정리

Set이 필요한 경우, HashSet이 가장 많이 사용된다.

입력 순서 유지, 값 정렬의 필요에 따라서 LinkedHashSet, TreeSet을 선택하면 된다.

 

시간 복잡도

• HashSet O(1)
• LinkedHashSet O(1)
• TreeSet O(log N)