[컬렉션 프레임워크] Set

1. Set이란?

• 중복을 허용하지 않고, 순서를 보장하지 않는 자료구조
• 자바에서는 Set 인터페이스를 통해 다양한 구현체 제공

---

2. 자바가 제공하는 대표적인 Set 구현체

☑︎ HashSet 설명

특징	설명
구현	내부적으로 해시 테이블을 사용
순서	보장하지 않음(입력 순서 X)
성능	평균 시간 복잡도 O(1)
용도	중복 제거가 중요하고 순서가 중요하지 않은 경우

 

☑︎ LinkedHashSet 설명

특징	설명
구현	HashSet + 연결 리스트 구조
순서	입력 순서를 유지
성능	HashSet보다는 약간 느리지만 여전히 빠름
용도	입력 순서를 유지하면서 중복 제거가 필요할 때 사용

☑︎ TreeSet 설명

특징	설명
구현	내부적으로 레드-블랙 트리(이진 탐색 트리의 일종) 사용
순서	자동 정렬됨 (기본은 오름차순, Comparator로 커스텀 가능)
성능	O(log n) (이진 탐색 트리 기반)
용도	정렬된 Set, 범위 검색이 필요할 때 사용

---

3. Set 종류별 비교 예제

public class JavaSetMain {
    public static void main(String[] args) {
        run(new HashSet<>());          // 순서 보장 X
        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();
    }
}

 

☑️ 실행 결과

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

---

4. TreeSet의 내부 - 이진 탐색 트리

☑︎ 이진 탐색 트리란?

• 노드의 왼쪽에는 더 작은 값, 오른쪽에는 더 큰 값이 들어감
• 데이터를 삽입하는 즉시 정렬된 구조로 유지됨

☑︎ TreeSet의 장점

• 자동 정렬(Comparable 또는 Comparator 기반)
• 정렬된 범위 검색이 쉬움
• 탐색/삽입/삭제 성능 O(log n) 보장 (레드-블랙 트리 덕분)

---

5. Set의 중복 제거 실전 예제

☑︎ 문제1 - 중복 제거(순서 상관 없음)

Integer[] arr = {30, 20, 20, 10, 10};
Set<Integer> set = new HashSet<>();

for (Integer n : arr) {
    set.add(n); // 중복 제거 자동 처리
}

for (Integer n : set) {
    System.out.println(n); // 순서 보장 X
}

☑︎ 문제2 - 중복 제거 + 입력 순서 유지

Integer[] arr = {30, 20, 20, 10, 10};
Set<Integer> set = new LinkedHashSet<>(List.of(arr));

for (Integer n : set) {
    System.out.println(n); // 입력 순서대로 출력: 30, 20, 10
}

☑︎ 문제3 - 중복 제거 + 정렬된 순서 출력

Set<Integer> set = new TreeSet<>(List.of(30, 20, 20, 10, 10));

for (Integer n : set) {
    System.out.println(n); // 정렬된 순서: 10, 20, 30
}

---

6. Set 연산(합집합, 교집합, 차집합)

Set<Integer> set1 = new HashSet<>(List.of(1, 2, 3, 4, 5));
Set<Integer> set2 = new HashSet<>(List.of(3, 4, 5, 6, 7));

// 합집합
Set<Integer> union = new HashSet<>(set1);
union.addAll(set2); // 모든 요소 합치기

// 교집합
Set<Integer> intersection = new HashSet<>(set1);
intersection.retainAll(set2); // 공통 요소만 남기기

// 차집합
Set<Integer> difference = new HashSet<>(set1);
difference.removeAll(set2); // set2 요소 제거

System.out.println("합집합: " + union);
System.out.println("교집합: " + intersection);
System.out.println("차집합: " + difference);

 

---

7. equals & hashCode 오버라이딩 예제

public class Rectangle {
    private int width;
    private int height;

    public Rectangle(int width, int height) {
        this.width = width;
        this.height = height;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Rectangle)) return false;
        Rectangle r = (Rectangle) o;
        return width == r.width && height == r.height;
    }

    @Override
    public int hashCode() {
        return Objects.hash(width, height); // width + height 기준 해시 생성
    }

    @Override
    public String toString() {
        return "Rectangle{" + "width=" + width + ", height=" + height + '}';
    }
}

Set<Rectangle> set = new HashSet<>();
set.add(new Rectangle(10, 10));
set.add(new Rectangle(20, 20));
set.add(new Rectangle(20, 20)); // 중복으로 저장 안 됨

for (Rectangle r : set) {
    System.out.println("rectangle = " + r);
}

---

8. HashSet의 성능 최적화 원리

• 기본 버킷 크기: 16
• 부하율(load factor): 0.75 (75%)
• 버킷 사용률이 75%를 넘으면 → 배열 크기를 2배로 확장 + 모든 요소 재배치(rehashing)
• 성능 유지를 위해 필요한 비용이지만, 자바가 자동으로 처리

---

9. 정리

• HashSet  : 중복 제거
• LinkedHashSet : 중복 제거 + 순서 유지
• TreeSet : 중복제거 + 정렬 유지

구현체	중복 제거	순서 보장	자동 정렬	순서
HashSet	O	X	X	매우 빠름 O(1)
LinkedHashSet	O	O (입력 순서)	X	보통
TreeSet	O	O (값 정렬 순서)	O	느림 O(log n)

 

<참고> - 김영한의 실전 자바 중급2편 강의 섹션 9. 컬렉션 프레임워크 Set