3주차 Unit 2.2 — Set 3형제 (HashSet / TreeSet / LinkedHashSet)

Psj·2026년 5월 18일

F-lab

목록 보기
79/197

Unit 2.2 — Set 3형제 (HashSet / TreeSet / LinkedHashSet)

F-LAB JAVA · 3주차 · Phase 2 · 컬렉션 프레임워크 전체 지도

📌 학습 목표

이 Unit을 끝내면 다음을 답할 수 있어야 한다.

  • Set 인터페이스의 본질 은 무엇인가?
  • HashSet 이 내부적으로 어떻게 동작하나? (해시 테이블 + HashMap)
  • TreeSet 의 Red-Black Tree 구조는?
  • LinkedHashSet 이 어떻게 삽입 순서를 유지하나?
  • 3형제의 시간 복잡도와 메모리 비용 차이는?
  • hashCode + equals 계약 이 Set 에서 왜 결정적인가?
  • 시나리오별로 어떤 Set 을 선택하나?
  • TreeSet 정렬 순서 는 어떤 규칙인가? (숫자 → 대문자 → 소문자 → 한글)

🎯 핵심 한 문장

Set 은 "중복 없는 모음" 이라는 단일 의미를 가진 인터페이스이고, 구현체 3형제는 각자 다른 트레이드오프를 제공한다.
HashSet 은 빠른 검색 (O(1) 평균) 을 위해 순서를 포기,
TreeSet 은 정렬된 순회 (O(log n)) 를 위해 약간의 속도 포기,
LinkedHashSet 은 삽입 순서 유지를 위해 약간의 메모리 추가.
박승제씨가 ILIC 에서 매일 만나는 "중복 제거 + 빠른 검색" 의 정답은 거의 항상 HashSet.

비유 — 도서관의 도서 보관

시스템비유
HashSet도서를 해시번호로 무작위 진열장에 — 빠르게 찾지만 순서 없음
TreeSet도서를 ABC 순으로 정렬해 진열 — 보기 좋지만 정리 비용
LinkedHashSet들어온 순서대로 진열 + 빠른 검색 — 약간 무겁지만 안정적
공통점같은 책 두 권은 안 받음 (중복 제거)

→ "중복 없음" 은 공통, "추가 조건" 으로 3형제 갈림.

🧭 9개 섹션 로드맵

1. Set 인터페이스의 본질
2. HashSet 의 내부 구조와 동작
3. TreeSet 의 내부 구조 (Red-Black Tree)
4. LinkedHashSet 의 내부 구조
5. 3형제 시간 복잡도 + 메모리 비교
6. hashCode 와 equals 계약 — Set 의 결정적 토대
7. ILIC 실무 — Set 선택 가이드
8. 흔한 실수 + 안티패턴
9. 면접 + 자기 점검

1️⃣ Set 인터페이스의 본질

1.1 Set 의 정의

Set<E> 인터페이스의 정의:

  "중복 없는 요소들의 모음"
  
규칙:
  - 같은 요소는 단 한 번만 보유
  - "같다" 의 기준은 equals (+ hashCode)
  - 인덱스 없음 (List 와 다름)
  - 순서는 구현체에 따라 다름

1.2 Set 의 핵심 메서드

public interface Set<E> extends Collection<E> {
    
    // 추가 — 이미 있으면 false 반환
    boolean add(E e);
    
    // 포함 여부 — Set 의 핵심 메서드 (빠른 검색)
    boolean contains(Object o);
    
    // 제거
    boolean remove(Object o);
    
    // 크기
    int size();
    
    // 순회
    Iterator<E> iterator();
    
    // 집합 연산 (default)
    boolean addAll(Collection<? extends E> c);   // 합집합
    boolean retainAll(Collection<?> c);          // 교집합
    boolean removeAll(Collection<?> c);          // 차집합
    
    // ...
}

핵심:

  • add: 추가 (중복 시 false)
  • contains: 빠른 검색 (Set 의 존재 이유)
  • 인덱스 메서드 없음 (get(i), add(i, e) 없음)

1.3 Collection 인터페이스 대비 추가 의미

Collection 의 add:
  "추가한다"
  
Set 의 add (오버라이드 의미):
  "중복이 아니면 추가하고 true 반환, 중복이면 false 반환"
  
→ 같은 메서드 시그니처에 의미가 강화됨

1.4 Set 의 본질 — 수학의 집합

수학적 의미:

Set = {x | x ∈ universe, 각 x 는 unique}

연산:
  - 합집합 (union): A ∪ B = {x | x ∈ A or x ∈ B}
  - 교집합 (intersection): A ∩ B = {x | x ∈ A and x ∈ B}
  - 차집합 (difference): A - B = {x | x ∈ A and x ∉ B}

자바의 Set 은 이 수학적 의미를 자료구조로 구현.

1.5 ILIC 시나리오 — Set 의 자연스러운 사용처

@Service
public class ShipmentService {
    
    // 처리된 운송장 추적
    private final Set<Long> processedShipmentIds = new HashSet<>();
    
    // 권한 집합
    public boolean hasPermission(User user, Permission required) {
        Set<Permission> userPermissions = user.getPermissions();
        return userPermissions.contains(required);   // O(1) 검색
    }
    
    // 중복 제거된 노선 목록
    public Set<String> getUniqueRoutes() {
        return repository.findAll().stream()
            .map(Shipment::getRoute)
            .collect(Collectors.toSet());
    }
    
    // 화물 분류 태그
    private final Set<CargoTag> dangerousTags = Set.of(
        CargoTag.HAZARDOUS,
        CargoTag.EXPLOSIVE,
        CargoTag.RADIOACTIVE
    );
    
    public boolean isDangerous(Cargo cargo) {
        return !Collections.disjoint(cargo.getTags(), dangerousTags);
        // disjoint: 교집합이 빈 집합인지
    }
}

→ Set 의 활용 패턴들.

1.6 자기 점검 답변

Set 을 List 대신 써야 하는 신호 3가지는?

답:
1. 중복 제거 가 필요할 때
2. "있는지 없는지" 검사 가 빈번할 때 (contains)
3. 순서가 중요하지 않을 때

이 3가지 중 하나라도 해당하면 Set 후보.
→ List 의 contains 는 O(n) 이지만 Set 은 O(1) (HashSet).

2️⃣ HashSet 의 내부 구조와 동작

2.1 HashSet 의 충격적 사실

public class HashSet<E> implements Set<E>, ... {
    
    private transient HashMap<E, Object> map;   // ★ 내부는 HashMap!
    
    private static final Object PRESENT = new Object();
    
    public HashSet() {
        map = new HashMap<>();
    }
    
    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
    
    public boolean contains(Object o) {
        return map.containsKey(o);
    }
    
    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }
}

놀라운 진실: HashSet 은 HashMap 을 감싼 wrapper!

  • 키 = Set 의 요소
  • 값 = 의미 없는 PRESENT 객체 (단순히 자리 채우기용)

2.2 왜 HashMap 을 재사용했나

Joshua Bloch 의 설계 결정:
  - HashSet 을 새로 만들 필요 X
  - HashMap 이 이미 "중복 없는 키" 를 처리
  - 키만 사용하면 그게 Set
  - 코드 재사용 + 유지보수 ↓
  - 단점: 값 슬롯 메모리 약간 낭비 (PRESENT 참조)

→ "이미 있는 자료구조 재사용" 의 좋은 예.

2.3 HashSet 동작 — add 메서드 추적

Set<String> set = new HashSet<>();
set.add("BL-001");

내부 단계:

Step 1: "BL-001".hashCode() 계산
  → 정수 값 (예: 1234567890)

Step 2: HashMap.put("BL-001", PRESENT) 호출
  → 해시값으로 버킷 위치 결정
  → 버킷에 새 노드 추가

Step 3: 기존에 같은 키 있으면 PRESENT 반환
  → HashSet.add()는 false 반환 (이미 있음)
  → 없으면 null 반환 → HashSet.add()는 true

2.4 HashSet 의 메모리 다이어그램

HashSet<String>:
  ┌─────────────────────────────────────┐
  │ map (HashMap<String, Object>)        │
  │  ┌────────────────────────────────┐ │
  │  │ table[]:                        │ │
  │  │  [0] → null                     │ │
  │  │  [1] → Node("BL-001", PRESENT) │ │
  │  │  [2] → null                     │ │
  │  │  [3] → Node("BL-002", PRESENT) │ │
  │  │       → Node("BL-005", PRESENT) │ │ (해시 충돌 시 연결)
  │  │  [4] → null                     │ │
  │  │  ...                             │ │
  │  └────────────────────────────────┘ │
  └─────────────────────────────────────┘
  
PRESENT 는 static 객체 (단 1개)
→ 모든 노드의 값이 같은 PRESENT 객체 가리킴
→ 메모리 효율적

2.5 박승제씨가 1주차에 본 HashMap 과 연결

박승제씨가 1주차에서 만든 HashMap PPT 자료 의 내용이 그대로 적용:

  • 초기 capacity 16
  • LoadFactor 0.75
  • 75% 차면 2배 resize
  • 해시 충돌은 체이닝 (Java 8+ 트리 변환)

→ HashSet 의 모든 성능 특성은 HashMap 의 특성과 동일.

2.6 HashSet 순서

Set<String> set = new HashSet<>();
set.add("A");
set.add("B");
set.add("C");

for (String s : set) {
    System.out.println(s);   // 어떤 순서?
}

예측 불가능:

  • HashMap 의 버킷 순서대로 순회
  • 해시값에 따라 버킷 결정
  • "삽입 순서" 와 무관
  • "정렬 순서" 도 아님

→ Set 의 본질 ("순서 없음") 그대로.
→ 순서 필요하면 TreeSet 또는 LinkedHashSet.

2.7 HashSet 성능

시간 복잡도:
  - add: O(1) 평균, O(n) 최악
  - contains: O(1) 평균
  - remove: O(1) 평균
  - 순회: O(n + capacity)

공간 복잡도:
  - 요소 n 개 보관 시 약 n / 0.75 = 1.33n 의 버킷
  - + Node 객체 (next + hash + key + value)
  - 약 40n bytes (대략)

→ ILIC 에서 가장 자주 쓰는 Set.

2.8 자기 점검 답변

HashSet 의 add 가 O(1) 인 이유는?

답:
1. 내부 HashMap 사용
2. hashCode 로 버킷 위치 즉시 결정
3. 버킷의 요소 수가 적음 (LoadFactor 0.75)
4. 평균적으로 1번의 비교로 추가 완료
5. 단, 최악 (해시 충돌 많음) 에는 O(n)

  • Java 8+ 는 트리로 변환해 O(log n) 까지 보장

3️⃣ TreeSet 의 내부 구조 (Red-Black Tree)

3.1 TreeSet 의 내부

public class TreeSet<E> implements NavigableSet<E>, ... {
    
    private transient NavigableMap<E, Object> m;   // 내부는 TreeMap!
    
    private static final Object PRESENT = new Object();
    
    public TreeSet() {
        this(new TreeMap<E, Object>());
    }
}

→ HashSet 과 같은 패턴: TreeMap 의 wrapper.

3.2 TreeMap 의 본질 — Red-Black Tree

Red-Black Tree (RB Tree):
  - 자가 균형 이진 탐색 트리
  - 모든 노드가 RED 또는 BLACK
  - 규칙으로 균형 유지
  - 최악 O(log n) 보장

자가 균형 조건:

1. 루트는 BLACK
2. RED 노드의 자식은 BLACK
3. 모든 leaf 까지 BLACK 노드 수가 같음 (Black Height)
4. RED 가 연속 안 됨

→ 삽입/삭제 후에도 자동으로 균형 유지.
→ 깊이가 log(n) 보장.

3.3 RB Tree 시각화

삽입: 1, 2, 3, 4, 5, 6, 7

  일반 BST (이진 탐색 트리) 였다면:
        1
         \
          2
           \
            3
             \  ← 거의 linked list
              4
               \
                5
  → 깊이 7, 검색 O(n)
  
  Red-Black Tree:
            4 (BLACK)
           / \
          2   6
         /\   /\
        1 3 5 7
  → 깊이 3, 검색 O(log n)

3.4 TreeSet 동작 — add 메서드

TreeSet<String> set = new TreeSet<>();
set.add("BL-003");   // 트리에 삽입
set.add("BL-001");
set.add("BL-002");

내부 단계:

add("BL-003"):
  - 빈 트리 → 루트로
  - 루트는 BLACK

add("BL-001"):
  - "BL-001" < "BL-003" → 왼쪽
  - RED 로 추가 후 균형 조정

add("BL-002"):
  - "BL-002" < "BL-003" → 왼쪽으로
  - "BL-002" > "BL-001" → 오른쪽
  - 트리 회전으로 균형 조정

결과:
       "BL-002" (BLACK)
       /      \
  "BL-001"  "BL-003"

3.5 TreeSet 의 정렬 순서

TreeSet<String> set = new TreeSet<>();
set.add("apple");
set.add("Banana");
set.add("3rd");
set.add("사과");
set.add("Apple");

for (String s : set) {
    System.out.println(s);
}
// 출력:
// 3rd
// Apple
// Banana
// apple
// 사과

정렬 규칙 (자연 순서):

1. 숫자 0-9 (ASCII 48-57)
2. 대문자 A-Z (ASCII 65-90)
3. 소문자 a-z (ASCII 97-122)
4. 한글 (Unicode 0xAC00 ~ 0xD7A3)

→ String 의 compareTo() 동작.

3.6 TreeSet 의 추가 메서드 (NavigableSet)

TreeSet<Integer> set = new TreeSet<>();
set.addAll(List.of(1, 3, 5, 7, 9));

// 첫/마지막
set.first();      // 1
set.last();       // 9

// 특정 값 근처
set.floor(6);     // 5 (6 이하 최댓값)
set.ceiling(6);   // 7 (6 이상 최솟값)
set.lower(5);     // 3 (5 미만 최댓값)
set.higher(5);    // 7 (5 초과 최솟값)

// 부분 집합
set.headSet(5);     // [1, 3]
set.tailSet(5);     // [5, 7, 9]
set.subSet(3, 7);   // [3, 5]

// 역순
set.descendingSet();   // [9, 7, 5, 3, 1]

→ TreeSet 의 가치는 정렬된 순회 + 범위 검색.

3.7 Comparator 지정

// Comparator 로 정렬 기준 변경
TreeSet<String> set = new TreeSet<>(Comparator.reverseOrder());
set.add("A");
set.add("C");
set.add("B");
// 순회: C, B, A

// 또는 객체 비교
TreeSet<Shipment> shipments = new TreeSet<>(
    Comparator.comparing(Shipment::getCreatedAt)
);

→ Phase 6 (Comparable/Comparator) 에서 더 깊이.

3.8 TreeSet 성능

시간 복잡도:
  - add: O(log n)
  - contains: O(log n)
  - remove: O(log n)
  - 순회 (정렬): O(n)
  - first/last: O(log n) [실제로는 O(1) 캐시]
  - subSet 등 범위: O(log n)

공간 복잡도:
  - Node 객체에 부모/왼쪽/오른쪽 + color 비트 + key + value
  - HashSet 보다 약 25% 더

3.9 자기 점검 답변

TreeSet 이 HashSet 보다 느린데도 쓰는 이유는?

답:
1. 자동 정렬: 순회 시 정렬된 순서
2. 범위 검색: subSet, headSet, tailSet 같은 강력 API
3. first/last: 최솟값/최댓값 즉시 접근
4. floor/ceiling: 근사 검색

→ 정렬 또는 범위 검색이 필요하면 TreeSet.
→ 그 외엔 HashSet 이 빠름.

4️⃣ LinkedHashSet 의 내부 구조

4.1 LinkedHashSet 의 내부

public class LinkedHashSet<E> extends HashSet<E> ... {
    
    // HashSet 을 상속받지만, 부모의 다른 생성자 호출
    public LinkedHashSet() {
        super(16, .75f, true);   // ★ true 가 핵심
    }
}

// HashSet 의 패키지 private 생성자
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
    //         ↑ HashMap 이 아니라 LinkedHashMap!
}

핵심: LinkedHashSet 은 내부적으로 LinkedHashMap 사용.

4.2 LinkedHashMap 의 본질

LinkedHashMap = HashMap + 이중 연결 리스트
  
  HashMap 의 기능:
    - 해시 테이블 (O(1) 검색)
  
  추가:
    - 모든 노드를 삽입 순서대로 이중 연결
    - 추가 prev/next 포인터

4.3 LinkedHashSet 의 메모리 구조

LinkedHashSet:
  
  내부 LinkedHashMap.table[]:
    [0] → Node("A")
    [1] → null
    [2] → Node("B")
    ...
  
  추가로 이중 연결 리스트:
    head → Node("A") ↔ Node("B") ↔ Node("C") ← tail
    (삽입 순서대로)
  
  각 Node:
    - hash, key, value (HashMap 의 Node 그대로)
    - next (해시 충돌 시 연결)
    - before, after (이중 연결, 순서 보존)

→ HashSet 의 노드 + 추가 포인터 2개.

4.4 LinkedHashSet 동작

LinkedHashSet<String> set = new LinkedHashSet<>();
set.add("A");
set.add("C");
set.add("B");

for (String s : set) {
    System.out.println(s);
}
// 출력:
// A
// C
// B
// → 삽입 순서!

순회 메커니즘:

HashSet 의 iterator():
  - 버킷 순서대로 순회 (해시 기반, 예측 불가)
  
LinkedHashSet 의 iterator():
  - 이중 연결 리스트 head 부터 순회
  - 삽입 순서 그대로

4.5 LinkedHashSet 의 메모리 비용

한 노드당 메모리:
  HashSet:         ~ 40 bytes
  LinkedHashSet:   ~ 48 bytes (before/after 포인터 추가 8 bytes × 2 = 16, 하지만 정렬 인해 약 +8)
  
큰 차이 아님 (10-20%)
하지만 큰 컬렉션에선 누적 메모리 차이 큼

4.6 LinkedHashSet 의 가치

사용 시점:
  - 순서를 보존하고 싶지만 (List 가 줄 수 있음)
  - 중복 제거도 필요 (Set 의 특성)
  - 빠른 검색도 필요 (HashSet 의 O(1))

대안:
  - List + 매번 contains 검사 → O(n) 매번
  - HashSet → 순서 X
  - LinkedHashSet → 둘 다 만족

4.7 LinkedHashSet 성능

시간 복잡도:
  - add: O(1) 평균 (HashSet 과 동일 + 약간의 포인터 갱신)
  - contains: O(1) 평균
  - remove: O(1) 평균
  - 순회: O(n) — 더 정확히 O(n) (HashSet 은 O(n + capacity))

공간 복잡도:
  - HashSet 보다 약 20% 더

4.8 ILIC 사용처

// 시나리오 1 — 최근 본 운송장 목록 (중복 제거 + 순서 유지)
public class RecentShipmentTracker {
    private final Set<Long> recentlyViewed = new LinkedHashSet<>();
    private static final int MAX_SIZE = 10;
    
    public void view(Long id) {
        recentlyViewed.remove(id);    // 있으면 제거
        recentlyViewed.add(id);        // 끝에 추가
        
        if (recentlyViewed.size() > MAX_SIZE) {
            Iterator<Long> it = recentlyViewed.iterator();
            it.next();
            it.remove();   // 가장 오래된 것 제거
        }
    }
}

// 시나리오 2 — 처리 순서를 기억해야 하는 ID 집합
public class OrderedProcessor {
    private final Set<Long> processedInOrder = new LinkedHashSet<>();
    
    public void process(Long id) {
        if (processedInOrder.contains(id)) return;
        // ... 처리
        processedInOrder.add(id);
    }
    
    public List<Long> getProcessOrder() {
        return new ArrayList<>(processedInOrder);
    }
}

4.9 자기 점검 답변

LinkedHashSet 은 언제 HashSet 대신 쓰는가?

답:

  • 삽입 순서가 의미 있을 때:

    • 처리 순서 기록
    • 최근 본 항목 목록
    • 사용자에게 보여줄 순서

  • HashSet 의 O(1) 성능도 필요할 때:

    • 빈번한 contains 검사
    • 큰 데이터셋

→ "순서 + 빠른 검색" 의 균형점.

5️⃣ 3형제 시간 복잡도 + 메모리 비교

5.1 시간 복잡도 비교표

작업HashSetTreeSetLinkedHashSet
add(e)O(1) 평균O(log n)O(1) 평균
contains(e)O(1) 평균O(log n)O(1) 평균
remove(e)O(1) 평균O(log n)O(1) 평균
iterator 시작O(capacity)O(log n)O(1)
순회 1바퀴O(n + capacity)O(n)O(n)
first/last(없음)O(log n)(없음)
floor/ceiling(없음)O(log n)(없음)

5.2 공간 복잡도 비교

n 개 요소 보관 시 메모리:

HashSet:
  table[]:      capacity × 4 bytes (참조) = (n/0.75) × 4
  Node:         n × ~36 bytes (hash + key + value + next)
  PRESENT:      1 (공유)
  ────────────────────────────────────
  대략: n × 41 bytes

TreeSet:
  Entry:        n × ~52 bytes (key + value + parent + left + right + color)
  PRESENT:      1 (공유)
  ────────────────────────────────────
  대략: n × 52 bytes (HashSet 보다 ~25% 더)

LinkedHashSet:
  table[]:      (n/0.75) × 4
  LinkedNode:   n × ~52 bytes (Node + before + after)
  PRESENT:      1 (공유)
  ────────────────────────────────────
  대략: n × 57 bytes (HashSet 보다 ~40% 더)

→ HashSet 이 메모리 가장 효율적.
→ LinkedHashSet 이 가장 무거움.
→ TreeSet 은 중간.

5.3 실제 벤치마크 (가상)

10,000 개 String 요소:

add 10,000 회:
  HashSet:         5 ms
  TreeSet:         15 ms
  LinkedHashSet:   6 ms

contains 10,000 회:
  HashSet:         3 ms
  TreeSet:         12 ms
  LinkedHashSet:   3 ms

순회 1바퀴:
  HashSet:         2 ms
  TreeSet:         2 ms (정렬된 순회)
  LinkedHashSet:   1 ms (이중 연결 리스트가 더 빠름)

메모리:
  HashSet:         ~ 400 KB
  TreeSet:         ~ 520 KB
  LinkedHashSet:   ~ 570 KB

→ HashSet 이 거의 모든 작업에서 빠름.
→ LinkedHashSet 의 순회는 의외로 빠름 (캐시 친화적 이중 연결).

5.4 선택 트리

박승제씨의 Set 선택 트리:

1. 정렬된 순회나 범위 검색이 필요?
   YES → TreeSet
   NO  → 2

2. 삽입 순서가 의미 있나?
   YES → LinkedHashSet
   NO  → HashSet (90% 이 경우)

5.5 ILIC 실전 비율 90:9:1

박승제씨가 ILIC 에서 사용:

90%: HashSet
  - 중복 제거
  - 빠른 검색
  - 순서 무관

9%: LinkedHashSet
  - 순서 보존이 필요한 곳
  - 최근 본 목록 등

1%: TreeSet
  - 정렬된 순회 필요
  - 범위 검색 필요
  - 도메인 객체 비교 (Phase 6 참고)

5.6 자기 점검 답변

3형제 중 메모리 가장 효율적인 것과 그 이유는?

답:

  • HashSet 이 가장 효율적
  • 이유:
    • Node 에 추가 메타데이터 없음 (TreeSet 은 color + 3 포인터)
    • 추가 연결 없음 (LinkedHashSet 은 before/after 포인터)
    • PRESENT 만 공유 사용

→ ILIC 같은 큰 데이터셋에서 HashSet 우선.

6️⃣ hashCode 와 equals 계약 — Set 의 결정적 토대

6.1 Set 동작의 토대

Set 의 "중복 제거" 동작은 hashCode + equals 에 의존:

HashSet.add(e):
  1. e.hashCode() 계산
  2. 버킷 위치 결정
  3. 그 버킷 안에서 e.equals(...) 로 동일 요소 검색
  4. 있으면 추가 안 함, 없으면 추가

6.2 hashCode + equals 계약 (Object 클래스 규약)

규약 1: equals 가 true 면 hashCode 도 같아야 함
  a.equals(b) == true → a.hashCode() == b.hashCode()

규약 2: hashCode 같다고 반드시 equals true 는 아님
  a.hashCode() == b.hashCode() ↛ a.equals(b)
  (해시 충돌 가능)

규약 3: equals 와 hashCode 는 일관되어야 함
  객체 상태 안 바뀌면 hashCode 도 안 바뀌어야 함

규약 4: x.equals(x) == true (반사성)
  x.equals(y) == y.equals(x) (대칭성)
  추이성: x.equals(y) && y.equals(z) → x.equals(z)

6.3 계약 위반 시 Set 동작 깨짐

// ❌ equals 만 오버라이드, hashCode 안 함
public class Shipment {
    private Long id;
    
    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Shipment)) return false;
        return id.equals(((Shipment) o).id);
    }
    // hashCode 안 만듦 → Object 의 기본 사용 (참조 기반)
}

Set<Shipment> set = new HashSet<>();
Shipment s1 = new Shipment(1L);
Shipment s2 = new Shipment(1L);

s1.equals(s2);       // true (equals 만 오버라이드)
s1.hashCode() == s2.hashCode();   // false (Object 기본)

set.add(s1);
set.contains(s2);    // false! 못 찾음!

문제:

  • equals 로 같다고 했지만 hashCode 다름
  • 다른 버킷에 들어감
  • contains 시 다른 버킷 검색 → 없다고 함

규약 위반의 결과 = Set 깨짐.

6.4 올바른 구현

// ✓ equals + hashCode 둘 다
public class Shipment {
    private Long id;
    private String blNo;
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Shipment)) return false;
        Shipment other = (Shipment) o;
        return Objects.equals(id, other.id);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

→ Java 7+ 의 Objects.hash 활용.
→ Lombok 의 @EqualsAndHashCode 도 권장.

6.5 Lombok 활용

@Getter
@EqualsAndHashCode(of = "id")
public class Shipment {
    private Long id;
    private String blNo;
    // ...
}

@EqualsAndHashCode:

  • equals + hashCode 자동 생성
  • of = "id" 로 특정 필드만 사용
  • ILIC 표준 패턴

6.6 가변 객체의 위험

public class MutableShipment {
    private Long id;
    
    @Override
    public int hashCode() {
        return id != null ? id.hashCode() : 0;
    }
}

Set<MutableShipment> set = new HashSet<>();
MutableShipment s = new MutableShipment();
s.setId(1L);
set.add(s);    // hashCode 기반 버킷에 저장

s.setId(2L);   // 객체 상태 변경 → hashCode 변경!
set.contains(s);  // false! 못 찾음

문제:

  • hashCode 변경 → 다른 버킷에 있어야 할 위치
  • 실제로는 옛 버킷에 있음
  • Set 깨짐

해결:

  • Set 키로 사용할 객체는 불변 권장
  • 또는 hashCode 계산에 변경 안 되는 필드만 사용 (id 등)

6.7 TreeSet 은 hashCode 안 씀

HashSet:
  - hashCode + equals 사용
  - 둘 다 오버라이드 필요

TreeSet:
  - Comparable.compareTo() 또는 Comparator.compare() 사용
  - hashCode 무관
  - 단, compareTo 가 equals 와 일관되어야 함
public class Shipment implements Comparable<Shipment> {
    @Override
    public int compareTo(Shipment o) {
        return id.compareTo(o.id);
    }
    
    // TreeSet 에선 hashCode 안 봄
    // 하지만 HashSet 호환을 위해 hashCode + equals 도 권장
}

6.8 박승제씨가 ILIC 에서 만나는 표준 패턴

@Entity
@Getter
@NoArgsConstructor
@EqualsAndHashCode(of = "id")
public class Shipment {
    @Id
    @GeneratedValue
    private Long id;
    
    @Column(unique = true)
    private String blNo;
    
    // ... 더 많은 필드
    
    // equals + hashCode 는 id 기반 (Lombok 자동)
}

→ JPA Entity 의 표준.
→ id 기반 동일성 → DB의 unique 보장.

6.9 자기 점검 답변

HashSet 에 객체 추가했는데 contains 가 false 반환하는 가장 흔한 원인은?

답:
1. equals 오버라이드, hashCode 안 함
2. hashCode 오버라이드, equals 안 함
3. 둘 다 오버라이드했지만 일관성 없음
4. 객체의 hashCode 가 변경됨 (mutable 객체)

해결:

  • 항상 둘 다 함께 오버라이드
  • Lombok @EqualsAndHashCode 활용
  • 불변 객체 권장

7️⃣ ILIC 실무 — Set 선택 가이드

7.1 시나리오별 선택

시나리오 1 — 권한 집합

public class User {
    @EqualsAndHashCode.Include
    private Long id;
    
    @ElementCollection
    @Enumerated(EnumType.STRING)
    private Set<Permission> permissions = new HashSet<>();
    // ↑ HashSet — 빠른 contains, 순서 무관
}

public boolean canApprove(User user) {
    return user.getPermissions().contains(Permission.APPROVER);
}

→ HashSet 적합.

시나리오 2 — 노선 정렬 목록

public class ShipmentService {
    public NavigableSet<Route> getActiveRoutes() {
        return new TreeSet<>(
            repository.findAllRoutes(),
            Comparator.comparing(Route::getName)
        );
        // ↑ TreeSet — 정렬된 순회
    }
    
    public NavigableSet<Route> getRoutesAlphabetical(String prefix) {
        TreeSet<Route> sorted = (TreeSet<Route>) getActiveRoutes();
        return sorted.subSet(
            new Route(prefix),
            new Route(prefix + Character.MAX_VALUE)
        );
        // 범위 검색
    }
}

→ TreeSet 적합 (정렬 + 범위 검색).

시나리오 3 — 최근 본 운송장 (순서 유지)

public class ShipmentHistoryService {
    private final Set<Long> recentlyViewed = new LinkedHashSet<>();
    // ↑ LinkedHashSet — 순서 유지 + 빠른 검색
    
    public void recordView(Long shipmentId) {
        recentlyViewed.remove(shipmentId);   // 있으면 제거
        recentlyViewed.add(shipmentId);       // 끝에 추가
        
        // 최대 10개 유지
        while (recentlyViewed.size() > 10) {
            Iterator<Long> it = recentlyViewed.iterator();
            it.next();
            it.remove();
        }
    }
}

→ LinkedHashSet 적합.

시나리오 4 — 처리된 ID 추적 (대량)

@Service
public class BatchProcessor {
    
    // 매우 큰 데이터셋
    public void processAll(List<Shipment> shipments) {
        Set<Long> processed = new HashSet<>(shipments.size());
        // ↑ HashSet + 초기 크기 지정 (확장 비용 회피)
        
        for (Shipment s : shipments) {
            if (processed.contains(s.getId())) continue;
            process(s);
            processed.add(s.getId());
        }
    }
}

→ HashSet + 초기 크기 지정.

시나리오 5 — 멀티스레드 환경

@Service
public class ShipmentEventBus {
    
    // ❌ 일반 HashSet — 멀티스레드 위험
    private final Set<EventListener> listeners = new HashSet<>();
    
    // ✓ ConcurrentHashMap.newKeySet
    private final Set<EventListener> listeners = ConcurrentHashMap.newKeySet();
    
    // ✓ CopyOnWriteArraySet (읽기 위주)
    private final Set<EventListener> listeners = new CopyOnWriteArraySet<>();
    
    public void register(EventListener l) {
        listeners.add(l);
    }
    
    public void notifyAll(Event e) {
        listeners.forEach(l -> l.onEvent(e));
    }
}

→ 멀티스레드 환경의 Set 선택.

시나리오 6 — Enum 집합

public class CargoClassifier {
    
    // 일반 HashSet
    private static final Set<CargoType> RESTRICTED = 
        new HashSet<>(Set.of(CargoType.HAZARDOUS, CargoType.EXPLOSIVE));
    
    // ✓ EnumSet — Enum 전용, 매우 빠름
    private static final Set<CargoType> RESTRICTED = 
        EnumSet.of(CargoType.HAZARDOUS, CargoType.EXPLOSIVE);
}

EnumSet:

  • Enum 전용 Set 구현체
  • 비트 벡터 사용 (매우 메모리 효율)
  • 모든 작업 O(1) 보장
  • HashSet 보다 훨씬 빠름

→ Enum Set 은 항상 EnumSet 권장.

시나리오 7 — 불변 Set

// Java 9+ 불변 Set
public static final Set<String> ALLOWED_STATUSES = Set.of(
    "DRAFT", "ACTIVE", "COMPLETED"
);

// 변경 시도하면 UnsupportedOperationException
// 멀티스레드 안전
// 매우 가벼움

→ 상수 Set 은 Set.of 활용.

7.2 ILIC Set 선택 의사결정 표

시나리오선택이유
일반 권한/태그HashSet빠른 검색
정렬 필요TreeSet자연 순회
순서 + 빠른 검색LinkedHashSet둘 다 만족
멀티스레드ConcurrentHashMap.newKeySet안전
읽기 위주 멀티스레드CopyOnWriteArraySet빠른 읽기
EnumEnumSet비트벡터 최적화
상수Set.of불변, 가벼움
큰 데이터HashSet + 초기 크기확장 회피

7.3 ILIC 코드 리뷰 체크리스트

Set 사용 검토:

타입 선택:
  - HashSet (90%) 또는 다른 구현체?
  - 정렬 필요한데 TreeSet 미사용?
  - 순서 필요한데 HashSet?
  - Enum 인데 EnumSet 미사용?
  - 멀티스레드인데 일반 HashSet?

equals + hashCode:
  - 도메인 객체에 둘 다 오버라이드?
  - Lombok @EqualsAndHashCode 활용?
  - id 기반 동일성 (Entity 의 경우)?
  - 가변 객체 사용 안 함?

성능:
  - 큰 컬렉션에 초기 크기 지정?
  - List.contains → Set 변환?
  - 자주 변하는 Set 의 캐시?

7.4 자기 점검 답변

ILIC 에서 Set 을 잘못 선택하는 가장 흔한 케이스 3가지는?

답:
1. Enum 인데 HashSet 사용 → EnumSet 으로 변환
2. 정렬 필요한데 HashSet + 후처리 정렬 → TreeSet 으로
3. 멀티스레드인데 일반 HashSet → ConcurrentHashMap.newKeySet

→ ILIC 코드 리뷰 시 자주 발견되는 패턴.

8️⃣ 흔한 실수 + 안티패턴

8.1 실수 1 — equals 없이 contains 기대

// ❌ equals 안 오버라이드
public class Shipment {
    private Long id;
    // equals, hashCode 없음
}

Set<Shipment> set = new HashSet<>();
set.add(new Shipment(1L));
set.contains(new Shipment(1L));   // false!

원인: Object 의 기본 equals (참조 비교).
해결: equals + hashCode 오버라이드.

8.2 실수 2 — Set 안에서 객체 변경

Set<MutableShipment> set = new HashSet<>();
MutableShipment s = new MutableShipment(1L);
set.add(s);

s.setId(2L);   // hashCode 변경
set.contains(s);   // false!
set.remove(s);     // 못 제거!

해결:

  • 불변 객체 사용
  • 또는 변경 안 되는 필드 기반 hashCode (id 등)

8.3 실수 3 — TreeSet 에 null 추가

TreeSet<String> set = new TreeSet<>();
set.add(null);   // ❌ NullPointerException

이유:

  • TreeSet 은 compareTo 호출
  • null.compareTo(...) 불가

해결:

  • HashSet (null 1개 허용) 또는 LinkedHashSet 사용
  • 또는 null 명시적 처리

8.4 실수 4 — 큰 Set 에 초기 크기 미지정

// ❌ 매번 resize
Set<Long> ids = new HashSet<>();   // 초기 16
for (int i = 0; i < 1_000_000; i++) {
    ids.add(...);   // 매번 resize 발생
}

// ✓ 미리 크기 지정
Set<Long> ids = new HashSet<>(1_500_000);
// 초기 buckets ≈ 1,500,000 (capacity 미리 확보)

큰 Set 은 초기 크기 지정.

8.5 실수 5 — Set.of 변경 시도

Set<String> immutable = Set.of("A", "B", "C");
immutable.add("D");   // ❌ UnsupportedOperationException

해결:

Set<String> mutable = new HashSet<>(Set.of("A", "B", "C"));
mutable.add("D");   // OK

8.6 실수 6 — HashSet 으로 정렬 시도

// ❌ HashSet 은 순서 X
Set<String> set = new HashSet<>(List.of("C", "A", "B"));
// 순회 순서 예측 불가

// ❌ 정렬을 위해 List 변환 후 정렬
List<String> list = new ArrayList<>(set);
Collections.sort(list);
// 매번 정렬 비용

// ✓ TreeSet
TreeSet<String> sorted = new TreeSet<>(set);
// 자동 정렬

8.7 실수 7 — Enum 인데 HashSet

// ❌ HashSet 으로 Enum
Set<Status> statuses = new HashSet<>();
statuses.add(Status.ACTIVE);
statuses.add(Status.INACTIVE);

// ✓ EnumSet
Set<Status> statuses = EnumSet.of(Status.ACTIVE, Status.INACTIVE);
// 비트벡터, 매우 빠름

8.8 실수 8 — 컬렉션 매개변수로 받아 변경

public void filterShipments(Set<Long> ids) {
    ids.removeAll(processedIds);   // 호출자 Set 변경!
}

// 호출
Set<Long> myIds = new HashSet<>(...);
service.filterShipments(myIds);
// myIds 가 의도치 않게 변경됨

해결:

public Set<Long> filterShipments(Set<Long> ids) {
    Set<Long> result = new HashSet<>(ids);
    result.removeAll(processedIds);
    return result;
}

→ Phase 1 의 매개변수 안전 패턴.

8.9 ILIC Set 안티패턴 체크리스트

박승제씨가 ILIC 에서 피할 것:

equals/hashCode:
  - 한쪽만 오버라이드 → 항상 둘 다
  - 가변 필드 기반 hashCode → 불변 필드 기반
  - JPA Entity 에서 lazy field 사용 → id 기반

구현체 선택:
  - Enum 에 HashSet → EnumSet
  - 정렬 필요 시 매번 sort → TreeSet
  - 멀티스레드에 HashSet → ConcurrentHashMap.newKeySet

성능:
  - 큰 Set 에 초기 크기 미지정 → 지정
  - 빈번 contains 에 List → Set 변환

안전:
  - 매개변수 Set 변경 → 방어적 복사
  - Set.of 변경 시도 → new HashSet<>()

9️⃣ 면접 + 자기 점검

9.1 면접 단골 질문 매핑

Q핵심 답변
Set 의 정의?중복 없는 모음
HashSet 내부 구조?HashMap 의 wrapper
HashSet 이 빠른 이유?해시 테이블 O(1)
TreeSet 내부 구조?Red-Black Tree (자가 균형 BST)
TreeSet 시간 복잡도?O(log n)
LinkedHashSet 내부?LinkedHashMap (HashMap + 이중 연결)
3형제 선택 기준?정렬? → Tree, 순서? → Linked, 그 외 → Hash
hashCode+equals 계약?equals true → hashCode 같아야
계약 위반 결과?contains 못 찾음, Set 깨짐
EnumSet 의 이점?비트벡터, 메모리/속도 최적
TreeSet 정렬 순서?숫자 → 대문자 → 소문자 → 한글
ConcurrentHashMap.newKeySet?멀티스레드 안전 Set

9.2 자기 점검 체크리스트

기본 이해

  • Set 인터페이스의 본질 (중복 없음, 인덱스 없음) 을 안다
  • HashSet 의 내부가 HashMap 임을 안다
  • TreeSet 이 Red-Black Tree 인 것을 안다
  • LinkedHashSet 이 어떻게 순서 유지하는지 안다
  • 3형제 시간 복잡도를 외운다

hashCode + equals

  • hashCode + equals 계약을 외운다
  • equals 만 오버라이드하면 발생할 문제를 안다
  • @EqualsAndHashCode 활용 가능
  • 가변 객체의 위험을 안다
  • JPA Entity 의 표준 패턴을 안다

실전 적용

  • 시나리오에 맞는 Set 선택 가능
  • EnumSet 활용 (Enum 시)
  • 멀티스레드 Set 선택 (ConcurrentHashMap.newKeySet)
  • 큰 Set 에 초기 크기 지정
  • Set.of 불변 활용

면접 대비

  • 3형제 내부 구조 설명
  • hashCode+equals 계약 설명
  • 시간 복잡도 비교
  • EnumSet 의 비트벡터 설명
  • ILIC 사용 사례 설명

🎯 핵심 요약 — 3줄 정리

1. Set 3형제의 본질

  • HashSet = HashMap wrapper (해시 테이블, O(1))
  • TreeSet = TreeMap wrapper (Red-Black Tree, O(log n))
  • LinkedHashSet = LinkedHashMap wrapper (해시 + 이중 연결, O(1) + 순서)

2. hashCode + equals 계약 = Set 의 토대

  • equals true → hashCode 같아야 함
  • 둘 다 오버라이드 필수
  • @EqualsAndHashCode 활용
  • 가변 객체 위험

3. ILIC 실무 패턴

  • 90% HashSet
  • 9% LinkedHashSet, ConcurrentHashMap.newKeySet, EnumSet
  • 1% TreeSet (정렬 필요 시)

📚 다음으로...

Unit 2.3 — List 3형제 (ArrayList / LinkedList / Vector)

이번 Unit에서 Set 3형제를 봤다면, 다음은 List 3형제.

박승제씨가 2주차에서 본 ArrayList/LinkedList 내부 구조 위에:

  • Vector 의 정체 (legacy, synchronized)
  • 3형제의 시간 복잡도 비교
  • LinkedList 의 Queue 역할
  • CopyOnWriteArrayList 까지

→ 1·2주차 학습의 종합 + 3주차 신규 (Vector legacy).

Phase 2 진행 상황

🚀 Phase 2 — 컬렉션 프레임워크 전체 지도
  ✅ Unit 2.1 배열의 한계와 컬렉션의 등장
  ✅ Unit 2.2 Set 3형제 ← 여기
  ⏭ Unit 2.3 List 3형제 (ArrayList/LinkedList/Vector)
  ⏭ Unit 2.4 Queue (FIFO 자료구조)
  ⏭ Unit 2.5 Map 5형제
  ⏭ Unit 2.6 컬렉션 전체 지도 정리

3주차 누적 진행

✅ Phase 1 — Pass by Value (1.1 ~ 1.3 완주)
🚀 Phase 2 — 컬렉션 프레임워크 (2/6 진행)

총: 5/43 Unit 작성 (약 12%)

--

profile
Psj
Software Developer
이전 포스트

3주차 Unit 2.1 — 배열의 한계와 컬렉션의 등장

다음 포스트

3주차 Unit 2.3 — List 3형제 (ArrayList / LinkedList / Vector)

0개의 댓글