[JAVA] Set

Set

• Set은 중복을 허용하지 않고, 순서를 보장하지 않는 자료구조. 어떤 요소도 같은 Set 내에 두 번 이상 나타날 수 없다.
• Set은 수학적 집합 개념을 구현한 것으로 순서를 보장하지 않고 특정 요소가 집합에 있는지 여부를 확인하는데 최적화.
• Set 인터페이스는 HashSet, LinkedHashSet, TreeSet 등 다양한 구현 클래스를 가지고 있고 각 클래스는 Set 인터페이스를 구현한다.

HashSet

• 해시 자료 구조를 사용해 특정 순서 없이 저장
• O(1) 의 시간 복잡도
• 데이터의 유일성만 중요하고, 순서가 중요하지 않는 경우 적합
• hashCode(), equals() 를 모두 사용

LinkedHashSet

• HashSet에 연결 리스트를 추가해 요소들의 순서 보장 즉 순서대로 조회 시 요소들이 추가된 순서대로 반환
• O(1) 의 시간 복잡도
• 데이터의 유일성과 삽입 순서를 유지할때 적합
• 연결 링크를 유지해 HashSet 보다 무거움.

TreeSet

• TreeSet은 이진 탐색 트리를 개선한 레드-블랙 트리를 내부에서 사용
• 요소들은 정렬 순서로 저장
• O(log n) 의 시간복잡도
• 데이터들을 정렬된 순서로 유지하며 집합의 특성을 유지하는 경우 사용 ex) 3,2,1 순서로 입력 → 1,2,3 출력

트리 구조

• 부모 노드와 자식 노드로 구성
• 가장 높은 조상은 루트(root)
• 왼쪽 자손은 더 작은값, 오른쪽 자손은 더 큰 값 → 이진 탐색 트리

• 이진 탐색 트리 계산의 핵심은 한번에 절반을 날린다는 점
• 트리의 균형이 깨진 최악의 경우 O(n)의 성능이 나오는데, 동적으로 균형을 다시 맞추는 해결 방안이 있다.
• 균형을 맞추는 AVL 트리, 레드-블랙 트리 같은 다양한 알고리즘이 존재한다.
• 따라서 최악의 경우에도 O(log n) 의 성능 제공

이진 탐색 트리의 핵심은 입력 순서가 아니라, 데이터의 값을 기준으로 정렬해서 보관한다는 점이다.

public class JavaSetMain {
    public static void main(String[] args) {
        run(new HashSet<String>()); //입력 순서 보장 안함 O(1)
        run(new LinkedHashSet<String>()); //입력 순서 보장 O(1)
        run(new TreeSet<String>()); //데이터 값을 기준으로 정렬 O(log N)
    }

    private static void run(Set<String> set) {
        System.out.println("set = " + set.getClass());

        set.add("C");
        set.add("B");
        set.add("A");
        set.add("D");
        set.add("1");
        set.add("2");

        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 D 
set = class java.util.LinkedHashSet
C B A D 1 2 
set = class java.util.TreeSet
1 2 A B C D 

HashSet, LinkedHashSet, TreeSet 모두 Set 인터페이스를 구현하기 때문에 구현체를 변경하면서 실행할 수 있다.

iterator() → 컬렉션 반복 출력

HashSet 과 최적화

통계적으로 입력한 데이터 수가 배열의 크기를 75% 정도 넘어가면 해시 인덱스가 자주 충돌한다. 따라서 성능이 떨어진다.

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

HashSet의 기본 크기 → 16

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

출처: 김영한의 실전 자바 - 중급 2편