TIL - HashSet (09.19)

📚 오늘 학습한 내용

MyHashSet 진화 과정

MyHashSetV1 → V3: 점진적 개선

1. V1: 기본 해시 알고리즘 구현 (Integer만 지원)
2. V2: Object 지원으로 모든 타입 처리 가능
3. V3: 제네릭과 인터페이스 도입으로 타입 안전성 확보

// V3의 핵심 - 제네릭 인터페이스 구현
public class MyHashSetV3<E> implements MySet<E> {
    private LinkedList<E>[] buckets;
    // hashCode() 활용한 해시 인덱스 생성
    private int hashIndex(Object value) {
        return Math.abs(value.hashCode()) % capacity;
    }
}

equals()와 hashCode()의 중요성

3단계 실험으로 증명한 필수성

1단계: 둘 다 구현하지 않은 경우

• 문제: 중복 데이터 저장, 검색 실패
• 원인: Object 기본 기능이 참조값 기반으로 동작

2단계: hashCode()만 구현한 경우

• 문제: 중복 데이터 저장됨
• 원인: 같은 해시 인덱스에 저장되지만 equals() 비교에서 실패

3단계: 둘 다 구현한 경우

• 결과: 완벽한 Set 동작 - 중복 방지, 정확한 검색

자바 표준 Set 구현체 비교

HashSet vs LinkedHashSet vs TreeSet

구분 HashSet LinkedHashSet TreeSet

내부구조	해시 테이블	해시테이블 + 연결리스트	레드-블랙 트리
순서보장	❌	✅ (입력순서)	✅ (정렬순서)
시간복잡도	O(1)	O(1)	O(log n)
메모리	가장 효율적	연결링크로 약간 무거움	트리 구조로 더 무거움

실행 결과로 확인한 차이점

// 입력: C, B, A, 1, 2
HashSet:       A 1 B 2 C        // 순서 무작위
LinkedHashSet: C B A 1 2        // 입력 순서 유지  
TreeSet:       1 2 A B C        // 값 기준 정렬

TreeSet의 트리 구조 이해

이진 탐색 트리의 핵심 원리

• 저장 규칙: 작은 값은 왼쪽, 큰 값은 오른쪽
• 검색 효율: 한 번에 절반씩 제거 → O(log n)
• 자동 정렬: 중위 순회로 정렬된 순서 출력

성능 비교 (1024개 데이터 기준)

• 리스트 검색: O(n) → 최대 1024번 비교
• 해시 검색: O(1) → 1번 계산
• 트리 검색: O(log n) → 최대 10번 비교

해시 자료구조 최적화 기법

자바 HashSet의 동적 리사이징

// 75% 임계점 도달 시
if (size > capacity * 0.75) {
    capacity *= 2;          // 배열 크기 2배 증가
    rehashing();            // 모든 요소 재배치
}

최적화 효과:

• 해시 충돌 빈도 감소
• 평균 O(1) 성능 유지
• 메모리와 성능의 균형

💡 핵심 인사이트

1. 해시 자료구조 사용 시 필수 규칙

equals()와 hashCode() 계약:

• 논리적으로 같은 객체는 같은 해시코드 반환
• equals()가 true면 hashCode()도 같아야 함
• IDE 자동생성 기능 적극 활용

2. Set 구현체 선택 기준

// 기본적인 중복 제거
Set<String> basic = new HashSet<>();

// 입력 순서가 중요한 경우
Set<String> ordered = new LinkedHashSet<>();

// 정렬이 필요한 경우
Set<String> sorted = new TreeSet<>();

3. 실무 적용 가이드

• 일반적인 경우: HashSet (가장 빠름)
• 순서 유지 필요: LinkedHashSet
• 정렬된 데이터 필요: TreeSet
• 대용량 데이터: HashSet + 동적 리사이징 활용

🔄 집합 연산 마스터

// 합집합 (Union)
Set<Integer> union = new HashSet<>(set1);
union.addAll(set2);

// 교집합 (Intersection)  
Set<Integer> intersection = new HashSet<>(set1);
intersection.retainAll(set2);

// 차집합 (Difference)
Set<Integer> difference = new HashSet<>(set1);
difference.removeAll(set2);

🎯 다음 학습 목표

• Map 자료구조와 해시 테이블의 관계 이해