Unit 3.2 — 해시 충돌 (Hash Collision)

F-LAB JAVA · 3주차 · Phase 3 · 해시(Hash)의 원리

---

📌 학습 목표

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

• 해시 충돌 의 정확한 정의는?
• 비둘기집 원리 (Pigeonhole Principle) 가 무엇이고, 해시 충돌과 어떻게 연결되나?
• 입력 공간이 출력 공간보다 큰 경우 충돌이 수학적으로 불가피한 이유 는?
• 생일 역설 (Birthday Paradox) 이 해시 충돌 확률에 시사하는 바는?
• Perfect Hashing 이 무엇이고, 왜 일반적으로 사용 못 하나?
• 두 가지 충돌 — hashCode 충돌 vs 인덱스 충돌 의 차이는?
• 충돌이 잦으면 해시 검색이 어떻게 O(1) → O(n) 으로 무너지나?
• HashDoS 공격 의 메커니즘과 자바의 대응은?
• 충돌 해결법의 두 갈래 (체이닝 vs 오픈 어드레싱) 는 무엇이 다른가?

---

🎯 핵심 한 문장

해시 충돌은 "서로 다른 키가 같은 해시값을 갖는 현상" 으로, 수학적으로 불가피하다.
비둘기집 원리에 따라 무한한 입력을 유한한 출력 (예: 32비트 int) 으로 매핑하면 충돌이 반드시 발생한다.
충돌이 잦으면 해시 검색이 O(1) 에서 O(n) 으로 무너지며, 이는 HashDoS 공격 의 기초가 된다.
자바는 이를 해결하기 위해 체이닝 + Java 8+ 트리 변환 으로 최악의 경우에도 O(log n) 을 보장한다.

비유 — 무한한 손님과 유한한 객실

호텔 (해시 테이블):
  객실 수: 100개 (유한)

손님 (가능한 키들):
  방문 가능한 사람: 무한대

배정 규칙 (해시 함수):
  주민등록번호 마지막 2자리 → 객실 번호
  
결과:
  - 1번 손님과 101번 손님: 같은 객실 배정 → 충돌
  - 손님이 객실보다 많으면 충돌 불가피
  - "누가 먼저 왔든 같은 방" → 둘 다 처리해야 함

→ 충돌은 결함이 아니라 수학적 필연.

---

🧭 9개 섹션 로드맵

1. 해시 충돌의 정의와 사례
2. 비둘기집 원리 (Pigeonhole Principle)
3. 생일 역설 — 충돌 확률의 수학
4. Perfect Hashing 의 가능성과 한계
5. 두 가지 충돌 — hashCode 충돌 vs 인덱스 충돌
6. 충돌이 성능에 미치는 영향 (O(1) → O(n))
7. HashDoS 공격과 자바의 방어
8. 충돌 해결법의 두 갈래
9. 면접 + 자기 점검

---

1️⃣ 해시 충돌의 정의와 사례

1.1 해시 충돌의 정확한 정의

해시 충돌 (Hash Collision):
  
  서로 다른 두 입력에 대해 해시 함수가 같은 출력을 반환하는 현상.
  
수식으로:
  k₁ ≠ k₂ 이지만 h(k₁) = h(k₂)
  
영어:
  Two distinct keys producing the same hash value.

1.2 자바에서의 실제 충돌 사례

// 사례 1 — String 의 충돌
"Aa".hashCode();   // 2112
"BB".hashCode();   // 2112  ← 충돌!

// 사례 2 — 더 많은 String 충돌
"FB".hashCode() == "Ea".hashCode();   // true
"Ca".hashCode() == "DB".hashCode();   // true

// 이유: 
// "Aa" = 65 × 31 + 97 = 2112
// "BB" = 66 × 31 + 66 = 2112
// 31 의 차이를 한 글자 늘려서 보충

→ String 의 hashCode 알고리즘은 결정적이지만 충돌 발생.

1.3 충돌이 의미하는 것

충돌이 발생하면:
  - 같은 버킷에 여러 키 존재
  - HashMap.get(key) 시 그 버킷의 모든 노드와 equals 비교
  - 추가 비용 발생

극단적 경우:
  - 모든 키가 충돌 → 모든 노드가 한 버킷
  - 검색 = 그 버킷의 연결 리스트 전체 순회
  - O(1) → O(n) 으로 성능 저하

1.4 충돌을 직접 확인하는 코드

public class HashCollisionDemo {
    public static void main(String[] args) {
        // 알려진 충돌 쌍
        String s1 = "Aa";
        String s2 = "BB";
        
        System.out.println("s1: " + s1 + ", hashCode: " + s1.hashCode());
        System.out.println("s2: " + s2 + ", hashCode: " + s2.hashCode());
        System.out.println("같은 hashCode? " + (s1.hashCode() == s2.hashCode()));
        System.out.println("같은 객체? " + s1.equals(s2));
        // 출력:
        // s1: Aa, hashCode: 2112
        // s2: BB, hashCode: 2112
        // 같은 hashCode? true
        // 같은 객체? false
    }
}

1.5 충돌의 두 측면

1. 정상적 충돌 (불가피)
   - 비둘기집 원리에 의한 통계적 충돌
   - LoadFactor 0.75 에서 자연스럽게 발생
   - 평균 < 1 개 / 버킷 → 성능 영향 미미

2. 비정상적 충돌 (공격)
   - 의도적으로 충돌 키 생성
   - HashDoS 공격
   - 자바 String 의 알려진 충돌 패턴 활용

1.6 String 충돌의 수학적 분석

String.hashCode() 의 알고리즘:
  h = 0
  for each char c in s:
    h = 31 × h + c
  
2글자 String 의 hashCode:
  "ab" → 31 × a + b
  
"Aa" vs "BB":
  "Aa" → 31 × 65 + 97 = 2015 + 97 = 2112
  "BB" → 31 × 66 + 66 = 2046 + 66 = 2112
  
일반화:
  "Xy" vs "(X+1)(y-31)" → 같은 hashCode
  31 = "B"-"A" 의 차이 × 1글자 단위

→ 31 의 배수만큼 첫 글자 줄이면 다음 글자 31 증가로 보상.

1.7 자기 점검 답변

두 다른 String 이 같은 hashCode 를 가질 수 있는 이유는?

답:

• hashCode 는 int (32비트), 약 42억 가지 값
• 가능한 String 은 무한대
• 비둘기집 원리로 충돌 불가피
• String.hashCode() 의 31 배수 알고리즘에 의한 충돌 패턴 존재
• 예: "Aa" 와 "BB" 모두 2112

---

2️⃣ 비둘기집 원리 (Pigeonhole Principle)

2.1 비둘기집 원리의 정의

비둘기집 원리 (Pigeonhole Principle):

  n+1 마리의 비둘기를 n 개의 비둘기집에 넣으면,
  반드시 한 비둘기집에는 2마리 이상의 비둘기가 들어간다.

일반화:
  n 개의 비둘기를 m 개의 비둘기집에 넣을 때 (n > m),
  적어도 한 비둘기집에는 ⌈n/m⌉ 마리 이상이 들어간다.

2.2 해시 충돌에의 적용

입력 공간 (비둘기):
  - 가능한 모든 키 — 무한대 또는 매우 큰 집합
  - 예: 모든 String, 모든 객체

출력 공간 (비둘기집):
  - hashCode 의 가능한 값 — 32비트 int = 약 42억
  - 또는 HashMap 의 버킷 수 (보통 16, 32, ...)

결과:
  입력이 출력보다 많으면 충돌 발생 보장
  무한 입력 → 충돌 불가피

2.3 시각화

가능한 모든 String (입력 공간):
  "A", "B", ..., "Z",
  "AA", "AB", ..., "ZZ",
  "AAA", ..., "Hello World",
  ...
  → 사실상 무한대

hashCode 가능한 값 (출력 공간):
  -2,147,483,648 ~ 2,147,483,647
  → 약 42억 (4.29 × 10^9)

비둘기집 원리:
  무한 / 42억 = 무한
  → 평균적으로 무한 개 키가 같은 hashCode
  → 충돌 보장

2.4 작은 예시

가정:
  - 가능한 키: 1, 2, 3, ..., 100 (100개)
  - 해시 함수: h(k) = k % 10
  - 출력: 0 ~ 9 (10개)

비둘기집 원리:
  100 / 10 = 10
  → 각 출력값에 평균 10개 키
  → 충돌 발생

실제:
  h(1) = 1, h(11) = 1, h(21) = 1, ..., h(91) = 1
  → 10개 키가 같은 출력 (출력 1)

→ 입력이 출력보다 많으면 반드시 충돌.

2.5 자바 코드로 확인

public class PigeonholeDemo {
    public static void main(String[] args) {
        // 100개 키, 10개 버킷
        Map<Integer, List<Integer>> bucket = new HashMap<>();
        
        for (int i = 0; i < 100; i++) {
            int hash = i % 10;
            bucket.computeIfAbsent(hash, k -> new ArrayList<>()).add(i);
        }
        
        bucket.forEach((hash, keys) -> {
            System.out.println("Hash " + hash + ": " + keys.size() + " keys");
        });
        // 모든 버킷에 10개씩 → 비둘기집 원리 확인
    }
}

2.6 해시 함수가 좋다면?

좋은 해시 함수의 경우:
  - 균등 분포
  - 평균적으로 100/10 = 10개 / 버킷

나쁜 해시 함수의 경우:
  - 편향된 분포
  - 한 버킷에 50개, 다른 버킷엔 0개

핵심:
  좋은 해시 함수는 충돌의 "수" 자체는 못 줄임
  대신 충돌이 "균등하게" 분포되도록 함

→ 비둘기집 원리는 피할 수 없지만, 분포는 조정 가능.

2.7 일반화된 의미

비둘기집 원리는 컴퓨터 과학에서 자주 등장:

1. 해시 충돌 (이 Unit)
2. 압축의 한계
   - 모든 데이터를 더 작게 압축할 수 없음
3. 인코딩의 한계
   - 정보 손실 없는 압축의 한계
4. 캐시 충돌
   - CPU 캐시 라인 매핑
5. 데이터 무결성
   - CRC, 체크섬의 한계

2.8 자기 점검 답변

비둘기집 원리가 해시 충돌과 어떻게 연결되나?

답:

• n 마리 비둘기 > m 개 비둘기집 → 적어도 한 집에 2마리 이상
• 해시 매핑:
  • 비둘기 = 가능한 키들 (무한대)
  • 비둘기집 = hashCode 값들 (42억)
• 무한 / 42억 = 무한 → 반드시 충돌
• 좋은 해시 함수는 충돌 수를 못 줄이지만 분포를 균등하게

---

3️⃣ 생일 역설 — 충돌 확률의 수학

3.1 생일 역설의 직관

질문:
  한 방에 몇 명이 있으면 두 사람이 같은 생일일 확률이 50% 인가?

직관적 답:
  365 / 2 = 약 183 명?

실제 답:
  단 23 명!
  
→ 직관과 다른 결과 → "역설"

3.2 수학적 계산

모두 다른 생일일 확률:
  P(모두 다름) = 365/365 × 364/365 × 363/365 × ... × (365-n+1)/365

n = 23 일 때:
  P(모두 다름) ≈ 49.3%
  P(충돌) = 1 - 49.3% = 50.7%

n = 50 일 때:
  P(충돌) ≈ 97%

n = 100 일 때:
  P(충돌) ≈ 99.99997%

3.3 해시 충돌에의 적용

해시값이 N 가지인 해시 함수의 경우:

n 개 키 입력 시 충돌 확률:
  P(충돌) ≈ 1 - exp(-n² / 2N)

50% 충돌 확률 도달 키 수:
  n ≈ √(2N × ln 2) ≈ 1.177 × √N

예시:
  N = 100      → n ≈ 12
  N = 10,000   → n ≈ 118
  N = 1,000,000 → n ≈ 1,177
  N = 2^32 (약 42억) → n ≈ 77,163

핵심 통찰:

• √N 정도의 입력에서 50% 충돌 확률
• 직관 (N/2) 보다 훨씬 빨리 충돌 발생

3.4 자바 hashCode 에의 적용

자바 hashCode 의 출력: 32비트 int
N = 2^32 = 4,294,967,296

50% 충돌 확률:
  n ≈ 1.177 × √(4.3 × 10^9) ≈ 77,000

즉, 약 77,000 개의 객체를 만들면 50% 확률로 두 객체가 같은 hashCode 보유.

→ 100만 개 데이터의 HashMap 에선 hashCode 충돌이 일상.

3.5 시뮬레이션 코드

public class BirthdayCollision {
    public static void main(String[] args) {
        Set<Integer> seen = new HashSet<>();
        Random r = new Random();
        int n = 0;
        
        while (true) {
            n++;
            int hash = r.nextInt();   // 32비트 random int
            if (!seen.add(hash)) {
                System.out.println("Collision at n = " + n);
                break;
            }
        }
        // 평균 출력: n = 약 65,000 ~ 80,000
    }
}

여러 번 실행하면 평균 약 77,000 부근.

3.6 의미

생일 역설의 시사:

1. 충돌은 생각보다 빨리 발생
   - n / 2 가 아니라 √n 수준

2. 해시 함수 선택의 중요성
   - 작은 hashCode 공간 (예: 16비트) 은 위험

3. HashMap 의 capacity 가 작은 이유
   - capacity 16 → 5~6 개만 넣어도 충돌 일상
   - LoadFactor 0.75 로 조기 확장

4. 보안의 함의
   - 암호학적 해시 (SHA-256 등) 는 충돌 회피 위해 큰 출력 (256비트)
   - 일반 해시 (32비트) 는 보안 부적합

3.7 HashMap 의 capacity 와 충돌

capacity 16 에 다양한 키 넣을 때:

n = 4:  충돌 확률 ≈ 30%
n = 8:  충돌 확률 ≈ 75%
n = 12: 충돌 확률 ≈ 95% (LoadFactor 0.75 도달)
n = 16: 충돌 확률 ≈ 99% (가득 참)

→ HashMap 은 LoadFactor 0.75 에서 확장
→ 평균적으로 충돌 1-2회 / 버킷
→ O(1) 유지

3.8 자기 점검 답변

자바 HashMap 에서 충돌이 정상적인 이유는?

답:
1. 비둘기집 원리: 무한 입력 → 42억 출력 → 충돌 보장
2. 생일 역설: √N 정도에서 50% 충돌 → 작은 데이터에서도 충돌
3. HashMap capacity 16: 5~6개만 넣어도 충돌 가능
4. LoadFactor 0.75: 충돌을 평균 1개/버킷으로 유지
5. Java 8+ 트리 변환: 최악의 경우에도 O(log n)

→ 충돌은 정상, 분포 관리 가 핵심.

---

4️⃣ Perfect Hashing 의 가능성과 한계

4.1 Perfect Hashing 의 정의

Perfect Hashing:
  주어진 입력 집합에 대해 충돌이 절대 없는 해시 함수.

수학적 표현:
  S = {k₁, k₂, ..., k_n}
  h: S → ℤ
  ∀ i ≠ j: h(kᵢ) ≠ h(kⱼ)

4.2 Perfect Hashing 의 가능 조건

조건 1: 입력 집합 S 가 정해져 있어야 함
  - 미리 알려진 키 집합
  - 동적 추가 불가

조건 2: 출력 공간이 입력보다 커야 함
  - |출력 공간| ≥ |S|
  
조건 3: 해시 함수가 입력별 맞춤형이어야 함
  - "이 키 집합" 에 맞춘 해시 함수
  - 다른 집합엔 충돌 발생 가능

결과:
  Perfect Hashing 은 정적 데이터에만 적용 가능

4.3 Perfect Hashing 의 예시

// 컴파일러의 키워드 인식 (정적 키워드 집합)
const char *keywords[] = {
    "if", "else", "for", "while", "return", ...
};

// gperf 같은 도구로 Perfect Hash 생성
// → 정해진 키워드 집합에 대해 충돌 없음

4.4 동적 데이터엔 사용 불가

HashMap 의 경우:
  - 키가 동적으로 추가됨
  - 어떤 키가 들어올지 미리 모름
  - Perfect Hashing 불가능

해결책:
  - 일반 해시 함수 + 충돌 처리
  - 좋은 해시 함수 + 적절한 LoadFactor + 트리 변환

4.5 Minimal Perfect Hashing

Minimal Perfect Hashing (MPH):
  n 개 키를 정확히 0 ~ n-1 로 매핑.
  
  → 메모리 낭비 없음
  → 가장 효율적인 Perfect Hashing

응용:
  - 사전 (Dictionary)
  - 데이터베이스 인덱스 (정적 부분)
  - 임베디드 시스템

생성 도구:
  - gperf (C)
  - CMPH (C)
  - 자바: 직접 구현 또는 라이브러리

4.6 자바에서 Perfect Hashing 비슷하게

// EnumMap 이 Perfect Hashing 의 일종
public enum ShipmentStatus {
    DRAFT, ACTIVE, COMPLETED, CANCELLED
}

EnumMap<ShipmentStatus, Integer> map = new EnumMap<>(ShipmentStatus.class);

// 내부 구현:
// - Enum 의 ordinal() 을 인덱스로 사용
// - 배열 인덱스 [0, 1, 2, 3]
// - 충돌 절대 없음
// - O(1) 보장

// EnumSet 도 동일 원리 (비트벡터)

→ Enum 타입은 정해진 집합 → Perfect Hashing 가능 → EnumMap/EnumSet 매우 빠름.

4.7 Perfect Hashing 의 트레이드오프

장점:
  ✓ 충돌 0
  ✓ 검색 O(1) 보장 (평균이 아닌 최악도)
  ✓ 메모리 효율

단점:
  ✗ 정적 데이터만
  ✗ 키 집합 미리 알아야
  ✗ 키 변경 시 해시 함수 재생성
  ✗ 일반적 자료구조에 부적합

4.8 일반 해시와의 비교

항목	일반 해시	Perfect 해시
충돌	발생	없음
동적 키	가능	불가
사전 정보	불필요	필수
검색 시간	O(1) 평균	O(1) 보장
메모리	LoadFactor × 1.33	정확히 n
응용	HashMap, HashSet	키워드 인식, 정적 집합

4.9 자기 점검 답변

Perfect Hashing 을 HashMap 에 적용 못 하는 이유는?

답:
1. HashMap 은 동적: 키가 런타임에 추가/제거
2. Perfect Hashing 은 정적 데이터만
3. 만약 동적 적용하려면:

• 매번 해시 함수 재생성 → 비용 ↑↑
• 모든 노드 재해싱 → O(n)

4. 대안:
   • 일반 해시 + 충돌 처리 (체이닝, 오픈 어드레싱)
   • EnumMap (Enum 의 정해진 집합)

---

5️⃣ 두 가지 충돌 — hashCode 충돌 vs 인덱스 충돌

5.1 두 종류의 충돌

충돌의 두 단계:

1. hashCode 충돌
   - 서로 다른 키의 hashCode 가 같음
   - 비둘기집 원리에 의한 진짜 충돌
   - 해시 함수의 한계
   
2. 인덱스 충돌
   - hashCode 는 다르지만 인덱스 계산 후 같은 버킷
   - HashMap 의 capacity 가 작아서 발생
   - 더 흔함

5.2 hashCode 충돌 예시

"Aa".hashCode();   // 2112
"BB".hashCode();   // 2112  ← 진짜 hashCode 충돌

// hashCode 가 같으니 어떤 capacity 여도 같은 버킷

이 경우:

• HashMap 이 어떤 크기든 같은 버킷
• 좋은 해시 함수의 한계
• 비둘기집 원리에 의한 불가피

5.3 인덱스 충돌 예시

"Hello".hashCode();   // 69609650
"World".hashCode();   // 83766130

// capacity 16 일 때:
int idx1 = (69609650 ^ (69609650 >>> 16)) & 15;
int idx2 = (83766130 ^ (83766130 >>> 16)) & 15;

// 두 값이 우연히 같으면 같은 버킷 → 인덱스 충돌

이 경우:

• hashCode 는 다름
• 작은 capacity 에서 같은 인덱스 계산
• capacity 키우면 해결

5.4 인덱스 충돌의 빈도

capacity 16, 좋은 hashCode 분포의 경우:

n = 4:  버킷당 평균 0.25 → 충돌 거의 없음
n = 8:  버킷당 평균 0.5
n = 12: 버킷당 평균 0.75 (LoadFactor 도달 → 확장)
n = 16: 평균 1.0 (확장 후엔 0.5)

핵심:
  LoadFactor 0.75 가 평균 충돌을 통제

5.5 HashMap 의 충돌 처리 흐름

HashMap.put(key, value) 흐름:

Step 1: hash = key.hashCode() ^ (... >>> 16)
  → hashCode 충돌 여부와 무관, 모두 같은 처리

Step 2: index = hash & (n - 1)
  → 인덱스 충돌 여부 결정

Step 3: 버킷[index] 확인
  Case A: null → 새 노드 (충돌 없음)
  Case B: 첫 노드의 key.equals(검색 키) → 덮어쓰기
  Case C: 첫 노드 다름 → 체이닝 (충돌 처리)
    → 다음 노드 검사 → equals 비교 → ...

Step 4: 노드 수 ≥ 8 → 트리 변환 (Java 8+)

5.6 충돌 검사의 비용

// HashMap.getNode 내부 (간략화)
final Node<K, V> getNode(int hash, Object key) {
    Node<K, V>[] tab = table;
    Node<K, V> first = tab[(n - 1) & hash];
    
    if (first.hash == hash &&
        ((k = first.key) == key || (key != null && key.equals(k)))) {
        return first;   // 첫 노드에서 매칭 → 빠름
    }
    
    if (first instanceof TreeNode) {
        return ((TreeNode<K, V>) first).getTreeNode(hash, key);   // 트리 검색 O(log n)
    }
    
    do {
        // 연결 리스트 순회
        if (next.hash == hash &&
            ((k = next.key) == key || (key != null && key.equals(k)))) {
            return next;
        }
    } while ((next = next.next) != null);
    
    return null;
}

핵심:

• 같은 hash 의 다른 키도 일단 비교
• equals 호출이 비용 (특히 String, Object 의 복잡한 equals)

5.7 hashCode 충돌과 인덱스 충돌의 영향

충돌 종류별 성능 영향:

hashCode 충돌:
  - 항상 같은 버킷
  - capacity 키워도 해결 안 됨
  - 좋은 hashCode 함수로 회피

인덱스 충돌:
  - capacity 키우면 분포 개선
  - 좋은 hash() 함수 (HashMap 의 비트 시프트) 가 도움
  - LoadFactor 0.75 로 조기 확장

대응:
  - capacity 미리 크게 (생성자 인자)
  - LoadFactor 조정 (드물게)
  - 좋은 hashCode 오버라이드

5.8 충돌 분포 시각화

public class CollisionAnalyzer {
    public static void main(String[] args) {
        int capacity = 16;
        int[] buckets = new int[capacity];
        
        // String 1000개 생성
        for (int i = 0; i < 1000; i++) {
            String key = "Shipment-" + i;
            int hash = key.hashCode() ^ (key.hashCode() >>> 16);
            int idx = hash & (capacity - 1);
            buckets[idx]++;
        }
        
        // 분포 출력
        System.out.println("Bucket distribution:");
        for (int i = 0; i < capacity; i++) {
            System.out.println("[" + i + "]: " + buckets[i]);
        }
        // 평균: 1000 / 16 ≈ 62.5
        // 좋은 hashCode 면 모든 버킷이 약 62 ± 변동
    }
}

5.9 자기 점검 답변

hashCode 충돌과 인덱스 충돌의 차이는?

답:

• hashCode 충돌:

  • 서로 다른 키의 hashCode 가 정확히 같음
  • 비둘기집 원리에 의한 진짜 충돌
  • capacity 키워도 해결 안 됨
  • 예: "Aa".hashCode() == "BB".hashCode()

• 인덱스 충돌:

  • hashCode 는 다르지만 hash & (n-1) 계산 후 같은 인덱스
  • capacity 가 작아서 발생
  • capacity 키우면 분포 개선
  • HashMap 의 LoadFactor 가 통제

→ 둘 다 같은 버킷 → 같은 처리 (체이닝/트리).

---

6️⃣ 충돌이 성능에 미치는 영향 (O(1) → O(n))

6.1 정상 상태의 성능

좋은 해시 + 적절한 LoadFactor:
  - 평균 버킷당 < 1 노드
  - 검색 시 1번의 equals 호출
  - O(1) 평균
  
HashMap 의 기본 동작:
  hash() → index → bucket[index] → return
  
시간: 약 50ns (Java 21, 표준 하드웨어)

6.2 충돌 1개의 비용

한 버킷에 2개 노드 (1번 충돌):
  - 1번째 노드 equals 비교 → 다름
  - 2번째 노드 equals 비교 → 매칭
  - 약 100ns
  
2배 비용. 여전히 빠름.

6.3 충돌 누적의 비용

한 버킷에 노드 수가 증가하면:

노드 1개: 1 equals → O(1)
노드 5개: 평균 3 equals → 비례
노드 100개: 평균 50 equals → O(n)
노드 1000개: 평균 500 equals → 매우 느림

→ 충돌이 누적되면 해시의 장점 소멸

6.4 최악의 시나리오

모든 키가 같은 hashCode 또는 같은 버킷:

put(k1), put(k2), ..., put(kn) 모두 같은 버킷
  → 연결 리스트 길이 n
  → 매 put: equals 호출 n 번
  → 총 비용: O(n²)

get(k_i):
  → 평균 n/2 번의 equals
  → O(n)

전체 시스템:
  - 100만 개 데이터 + 모두 같은 버킷
  - 단일 get 이 100만 번 equals
  - 약 100ms 소요
  - HashMap 의 의미 상실

6.5 Java 8+ 의 트리 변환

Java 7 까지:
  - 모두 연결 리스트
  - 최악 O(n)

Java 8+ :
  - 버킷의 노드 수 ≥ 8 → Red-Black Tree 로 변환
  - 트리에서 검색은 O(log n)
  - 최악도 O(log n) 보장

트리 변환 조건:
  - 한 버킷의 노드 수 ≥ 8
  - capacity ≥ 64 (그 이전엔 확장 우선)

트리 → 리스트 역변환:
  - 트리 크기 < 6

6.6 트리 변환의 효과

한 버킷에 노드 1000개 가정:

Java 7:
  검색: O(n) = 1000번 비교
  
Java 8+ (트리):
  검색: O(log n) = log2(1000) ≈ 10번 비교

→ 100배 빠름

6.7 실제 성능 측정

import java.util.HashMap;

public class CollisionPerformance {
    
    // 의도적으로 같은 hashCode 반환하는 키
    static class BadKey {
        int value;
        
        BadKey(int v) { this.value = v; }
        
        @Override
        public int hashCode() {
            return 0;   // 모두 같은 hashCode!
        }
        
        @Override
        public boolean equals(Object o) {
            return o instanceof BadKey && ((BadKey) o).value == this.value;
        }
    }
    
    public static void main(String[] args) {
        HashMap<BadKey, Integer> map = new HashMap<>();
        
        long t1 = System.nanoTime();
        for (int i = 0; i < 10000; i++) {
            map.put(new BadKey(i), i);
        }
        long t2 = System.nanoTime();
        
        System.out.println("Put 10k 같은 hashCode: " + (t2 - t1) / 1_000_000 + " ms");
        
        // Java 8 트리 변환 효과
        // Java 7 이었으면 매우 느림
    }
}

6.8 성능 비교

10,000 개 키 삽입:

좋은 hashCode:
  - 약 5 ms
  - 균등 분포

모든 hashCode = 0 (Java 7):
  - 약 500 ms
  - O(n²) 누적

모든 hashCode = 0 (Java 8+):
  - 약 50 ms
  - 트리 변환으로 O(n log n)

→ 100배 차이
→ Java 8+ 의 트리 변환이 핵심 안전장치

6.9 자기 점검 답변

모든 키가 같은 hashCode 일 때 Java 8+ HashMap 이 Java 7 보다 빠른 이유는?

답:

• Java 7:
  • 모든 노드가 연결 리스트
  • 검색 O(n), n 개 삽입 시 O(n²)
• Java 8+:
  • 버킷 노드 ≥ 8 → Red-Black Tree
  • 검색 O(log n), n 개 삽입 시 O(n log n)

→ 약 100배 차이.
→ 트리 변환은 HashDoS 방어 의 핵심.

---

7️⃣ HashDoS 공격과 자바의 방어

7.1 HashDoS 공격의 메커니즘

HashDoS (Hash Denial of Service) 공격:

목표:
  서버의 HashMap 을 의도적으로 최악 상태 (O(n²)) 로 만들어 시스템 마비.

방법:
  1. 서버의 hashCode 알고리즘 분석
  2. 같은 hashCode 가 되는 키들 생성
  3. 이 키들을 요청에 포함
  4. 서버가 HashMap 에 저장 → 모두 같은 버킷
  5. CPU 100% → 응답 불가

7.2 공격 시나리오

시나리오 1 — HTTP 헤더
  공격자가 수천 개의 충돌 헤더 전송
  
  GET / HTTP/1.1
  Header-AA: 1
  Header-BB: 2   ← AA 와 같은 hashCode
  Header-CC: 3
  ...
  
  서버가 Map<String, String> headers 에 저장
  → 모두 같은 버킷 → CPU 폭주

시나리오 2 — JSON 요청
  공격자가 충돌 키들이 포함된 JSON 전송
  
  {
    "Aa": 1,
    "BB": 2,
    "AaAaAaAa": 3,
    "BBBBBBBB": 4,
    ...
  }
  
  서버의 JSON 파서가 Map 으로 변환
  → 모두 같은 버킷 → DoS

시나리오 3 — 폼 데이터
  쿠키나 폼 데이터에 충돌 키들

7.3 역사적 사례

2003년 — Crosby & Wallach 논문
  - HashDoS 개념 정립
  - Perl, Python, PHP, Java 모두 취약

2011년 — 28C3 Conference
  - 실제 공격 시연
  - 수많은 웹 서버 마비 가능 입증
  - Java, PHP, Ruby, ASP.NET 등 영향

2012년 — CVE-2012-2739
  - Tomcat 의 HashDoS 취약점
  - 패치 발표

2012년 — Java 8 트리 변환 도입 결정
  - HashDoS 방어 강화
  - 2014년 Java 8 출시 시 포함

7.4 공격 코드 예시

public class HashDoSDemo {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        
        // 모두 같은 hashCode 인 String 생성
        String[] collidingStrings = generateCollidingStrings(10000);
        
        long start = System.currentTimeMillis();
        for (int i = 0; i < collidingStrings.length; i++) {
            map.put(collidingStrings[i], i);
        }
        long end = System.currentTimeMillis();
        
        System.out.println("10000 충돌 키 삽입: " + (end - start) + " ms");
    }
    
    static String[] generateCollidingStrings(int count) {
        // 알고리즘으로 충돌 문자열 생성
        // "Aa" 패턴 확장: "AaAa", "AaBB", "BBAa", "BBBB" 모두 같은 hashCode
        // ...
    }
}

7.5 자바의 방어 — Java 8+

방어책 1: 트리 변환
  - 한 버킷 노드 ≥ 8 → Red-Black Tree
  - O(n²) → O(n log n)
  - 공격 효과 100배 감소

방어책 2: hash() 함수 개선
  - hashCode ^ (hashCode >>> 16)
  - 상위 비트 활용
  - 인덱스 충돌 줄임

방어책 3: capacity 자동 확장
  - LoadFactor 0.75 에서 2배 확장
  - 분산 개선

방어책 4: Random Seed (일부 언어)
  - 자바는 적용 X
  - Python 3.4+, Perl 5.18+ 등은 적용

7.6 다른 언어의 방어

Python (3.4+):
  - SipHash 알고리즘
  - Random seed (시작 시 무작위)
  - hashCode 가 매 실행마다 다름
  - 공격 패턴 사전 분석 불가

PHP (5.4+):
  - max_input_vars 제한
  - 형태에 따라 다른 처리

Ruby:
  - 외부 충돌 알고리즘 적용
  - Java 와 비슷한 방어

7.7 사용자 코드의 대응

// 위험: 외부 입력을 키로 사용
public class UserInputCache {
    private final Map<String, Object> cache = new HashMap<>();
    
    public void put(String userKey, Object value) {
        cache.put(userKey, value);   // ❌ HashDoS 위험
    }
}

// 안전: 입력 검증 + 크기 제한
public class SafeCache {
    private static final int MAX_SIZE = 1000;
    private final Map<String, Object> cache = new HashMap<>(MAX_SIZE * 2);
    
    public void put(String userKey, Object value) {
        if (cache.size() >= MAX_SIZE) {
            throw new IllegalStateException("Cache full");
        }
        if (userKey.length() > 100) {
            throw new IllegalArgumentException("Key too long");
        }
        cache.put(userKey, value);
    }
}

7.8 자바 8+ 의 효과

실제 공격 효과 측정:

Java 7:
  - 10,000 충돌 키 → ~ 30초 (CPU 100%)
  - 100,000 충돌 키 → 약 50분
  - DoS 성공

Java 8+:
  - 10,000 충돌 키 → ~ 100 ms (트리)
  - 100,000 충돌 키 → ~ 5초
  - DoS 매우 어려움

7.9 자기 점검 답변

HashDoS 공격의 핵심 메커니즘과 Java 8+ 의 방어는?

답:

• 공격 메커니즘:

  • 같은 hashCode 인 키 다수 생성
  • HashMap 에 저장 → 모두 같은 버킷
  • 검색이 O(n²) 로 폭주
  • 서버 CPU 100% → 마비

• Java 8+ 방어:

  • 트리 변환 (버킷 노드 ≥ 8)
  • O(n²) → O(n log n)
  • 100배 빠른 처리
  • 공격 효과 무력화

• 추가 권장:

  • 외부 입력 키는 크기/길이 제한
  • 캐시 크기 상한
  • 의심스러운 패턴 모니터링

---

8️⃣ 충돌 해결법의 두 갈래

8.1 두 가지 주요 방법

충돌 발생 시 처리 방법:

방법 1: 체이닝 (Chaining)
  - 같은 버킷에 여러 노드 보관
  - 연결 리스트 또는 트리
  - 자바 HashMap, HashSet 채택

방법 2: 오픈 어드레싱 (Open Addressing)
  - 다른 빈 버킷 찾기
  - 선형 탐사, 이차 탐사, 이중 해싱
  - Python dict, Ruby Hash 일부 채택

8.2 체이닝의 개념

체이닝 (Chaining):

  버킷[i] 이 가득 차면 → 연결 리스트로 연결
  
  버킷[5]:
    Node("A") → Node("B") → Node("C") → null
  
  검색:
    1. 버킷 인덱스 계산
    2. 그 버킷의 리스트 순회
    3. equals 로 매칭 키 찾기

8.3 오픈 어드레싱의 개념

오픈 어드레싱 (Open Addressing):

  버킷[i] 이 가득 차면 → 다음 빈 버킷 찾기
  
  put("A"): h("A") = 5, 버킷[5] 비어있음 → 저장
  put("B"): h("B") = 5, 버킷[5] 차있음 → 버킷[6] 시도 → 저장
  put("C"): h("C") = 5, 버킷[5], [6] 차있음 → 버킷[7] 시도 → 저장
  
  검색 "B": h("B") = 5, 버킷[5] 다른 키 → [6] 시도 → 매칭

8.4 핵심 비교

항목	체이닝	오픈 어드레싱
충돌 처리	연결 리스트 / 트리	다른 버킷 탐사
메모리	약간 더 (Node 객체)	효율적
캐시 효율	낮음 (분산 메모리)	높음 (연속 메모리)
삭제	단순 (노드 제거)	복잡 (탐사 체인 유지)
LoadFactor 한계	0.75 이상도 가능	0.75 이하 필수
자바 채택	✓ HashMap	부분적 (특수 자료구조)

8.5 체이닝의 장점

1. 단순한 구현
   - 연결 리스트만 추가하면 됨
   - 삭제도 간단

2. LoadFactor 유연
   - 1.0 이상도 가능 (성능 저하 점진적)
   - 메모리 활용 효율

3. 충돌 처리 격리
   - 한 버킷의 충돌이 다른 버킷에 영향 X

4. 트리 변환 가능
   - Java 8+ 의 O(log n) 보장

8.6 오픈 어드레싱의 장점

1. 메모리 효율
   - Node 객체 없음
   - 배열만 사용
   - 더 적은 메모리 (약 30% 절약)

2. 캐시 효율
   - 연속 메모리 접근
   - CPU 캐시 친화적
   - 작은 데이터에 빠름

3. 단순한 구조
   - 배열 + 인덱스만
   - 포인터 추적 없음

8.7 오픈 어드레싱의 단점

1. 클러스터링 (Clustering)
   - 충돌이 누적되면 빈 슬롯 찾기 어려움
   - 검색 시 더 많은 슬롯 검사

2. 삭제의 복잡성
   - 단순 삭제 시 탐사 체인 깨짐
   - "삭제됨" 마커 (tombstone) 필요
   - 또는 재해싱 필요

3. LoadFactor 제약
   - 0.5 ~ 0.75 권장
   - 0.9 이상이면 성능 급락

4. 트리 변환 어려움
   - 체이닝처럼 한 위치에 트리 만들기 어려움

8.8 자바의 선택 — 체이닝

자바가 체이닝을 채택한 이유:

1. 일관성
   - 모든 HashMap 동작이 단순
   - 디버깅 쉬움

2. Java 8+ 트리 변환과 호환
   - 한 버킷에 트리 가능
   - 오픈 어드레싱은 트리 변환 어려움

3. 동적 데이터에 유연
   - 삽입/삭제 단순
   - LoadFactor 변동 허용

4. 안정성
   - 메모리 약간 더 사용 (트레이드오프 수용)
   - 클러스터링 회피

8.9 다른 언어의 선택

Java:
  - HashMap: 체이닝 + Java 8+ 트리
  - ConcurrentHashMap: 체이닝 + 트리

Python:
  - dict: 오픈 어드레싱 (선형 탐사)
  - 메모리 효율 + 캐시 친화적

Ruby:
  - Hash: 오픈 어드레싱 (Ruby 2.4+)
  - 이전엔 체이닝

C++:
  - std::unordered_map: 체이닝 (대부분 구현)

Go:
  - map: 변형된 오픈 어드레싱 (bucket 그룹)

Rust:
  - HashMap: SwissTable 알고리즘 (오픈 어드레싱 변형)

8.10 두 방법의 시각화

체이닝:
  table[]:
    [0] → Node("A") → Node("E") → Node("I")
    [1] → Node("B")
    [2] → null
    [3] → Node("C") → Node("G")
    [4] → null
    ...

오픈 어드레싱 (선형 탐사):
  table[]:
    [0] → "A"
    [1] → "B"
    [2] → "E" (원래 h("E") = 0, 차있어 다음)
    [3] → "C"
    [4] → "G" (h("G") = 3, 다음)
    [5] → "I" (h("I") = 0, 여러 번 다음)
    ...

→ 직관적 차이.

8.11 자기 점검 답변

자바가 오픈 어드레싱이 아닌 체이닝을 채택한 이유는?

답:
1. 삭제의 단순성: 노드만 제거, 탐사 체인 무관
2. 트리 변환 호환: Java 8+ 의 O(log n) 보장 가능
3. LoadFactor 유연성: 0.75 이상도 처리
4. 동적 데이터 친화적: 잦은 삽입/삭제
5. 클러스터링 회피: 한 버킷 문제가 다른 버킷에 영향 X

오픈 어드레싱은 메모리/캐시 효율은 더 좋지만, 자바의 우선순위 (일관성, 안정성, 트리 변환 가능성) 에 더 적합.

---

9️⃣ 면접 + 자기 점검

9.1 면접 단골 질문 매핑

Q	핵심 답변
해시 충돌이란?	서로 다른 키가 같은 해시값
충돌이 불가피한 이유?	비둘기집 원리, 무한 입력 / 유한 출력
비둘기집 원리?	n+1 비둘기 / n 비둘기집 → 한 집에 2마리+
생일 역설의 시사?	√N 정도에서 50% 충돌, 직관보다 빠른 발생
Perfect Hashing?	충돌 없는 해시, 정적 데이터만 가능
EnumMap 의 의미?	Enum 의 정해진 집합 → Perfect Hashing 일종
String "Aa" 와 "BB" 의 충돌?	hashCode = 2112 동일, 31 배수 알고리즘
hashCode 충돌 vs 인덱스 충돌?	진짜 vs capacity 작아서
HashDoS 공격?	충돌 키 다수로 O(n²) 유도, CPU 폭주
Java 8+ 의 방어?	트리 변환으로 O(n²) → O(n log n)
체이닝 vs 오픈 어드레싱?	연결 리스트 vs 다른 버킷 탐사
자바의 선택?	체이닝 + 트리 (Java 8+)

9.2 자기 점검 체크리스트

기본 이해

• 해시 충돌의 정의를 안다
• 비둘기집 원리를 설명할 수 있다
• 생일 역설의 의미를 안다
• Perfect Hashing 의 가능성과 한계를 안다
• hashCode 충돌과 인덱스 충돌의 차이를 안다

실제 사례

• String "Aa" vs "BB" 충돌 원인을 안다
• EnumMap 이 Perfect Hashing 임을 안다
• HashMap 의 LoadFactor 0.75 의미를 안다
• 충돌 분포 검증 코드 작성 가능

성능 영향

• 충돌 누적의 O(n²) 위험을 안다
• Java 8+ 트리 변환의 효과를 안다
• HashDoS 공격 메커니즘을 안다
• 외부 입력 키의 위험 대응 가능

충돌 해결법

• 체이닝과 오픈 어드레싱의 차이를 안다
• 자바의 체이닝 채택 이유 5가지
• 다른 언어의 선택을 안다
• Unit 3.3, 3.4 에 진입 준비

9.3 추가 심화 질문

Q1: HashMap 의 capacity 가 작을 때 어떤 충돌이 주로 발생?

답:

• 인덱스 충돌이 주로 발생
• hashCode 는 다르지만 hash & (n-1) 이 같음
• capacity 키우면 자동 개선
• 해결: 큰 데이터엔 new HashMap<>(initialCapacity)

Q2: capacity 를 매우 크게 (예: 10억) 잡으면 충돌 없는가?

답:

• 인덱스 충돌은 줄어듦 (분포 개선)
• 하지만 hashCode 충돌은 그대로 (해시 함수의 한계)
• 메모리 낭비 발생 (10억 슬롯 = 약 40GB)
• 적절한 capacity (예상 데이터의 1.5배) 가 합리적

Q3: hashCode 가 매번 같은 값을 반환하면?

답:

• 모든 노드가 한 버킷
• Java 7 까지: O(n²) 누적, 매우 느림
• Java 8+: 트리 변환 → O(n log n)
• 여전히 매우 느림 (정상보다 100배)
• → 좋은 hashCode 구현 필수

Q4: equals 가 항상 false 면?

답:

• HashMap.put: 추가 (이미 있어도 새 추가)
• 같은 키로 보이는 객체도 다른 객체로 취급
• 메모리 누수 가능
• 결과는 의도와 다름
• → equals 의 올바른 구현 필수

---

🎯 핵심 요약 — 3줄 정리

1. 해시 충돌은 수학적 필연

• 비둘기집 원리: 무한 입력 / 유한 출력 → 충돌 보장
• 생일 역설: √N 에서 50% 충돌
• Perfect Hashing 은 정적 데이터만

2. 두 가지 충돌

• hashCode 충돌 (진짜): 해시 함수의 한계
• 인덱스 충돌: capacity 작아서
• 둘 다 같은 버킷 → 같은 처리

3. 성능 영향과 대응

• 충돌 누적 → O(1) → O(n²) 위험
• HashDoS 공격의 기초
• Java 8+ 트리 변환으로 O(n log n) 보장
• 자바는 체이닝 채택 (오픈 어드레싱 대안)

---

📚 다음으로...

Unit 3.3 — 충돌 해결법 1: 체이닝 (Chaining)

이번 Unit 에서 충돌의 본질을 봤다면, 다음은 체이닝 방식의 정밀.

• 체이닝의 자료구조 (연결 리스트)
• HashMap.put 의 체이닝 동작 추적
• Java 8+ 의 트리 변환 메커니즘
• 직접 구현해보는 HashMap
• 시간 복잡도와 메모리 트레이드오프

→ 마스터 프롬프트 깊이 Unit — HashMap 직접 구현 가능 수준.

Phase 3 진행 상황

🚀 Phase 3 — 해시(Hash)의 원리
  ✅ Unit 3.1 해시의 탄생 배경
  ✅ Unit 3.2 해시 충돌 ← 여기
  ⏭ Unit 3.3 충돌 해결법 1: 체이닝 (마스터 깊이)
  ⏭ Unit 3.4 충돌 해결법 2: 오픈 어드레싱 (마스터 깊이)

3주차 누적 진행

✅ Phase 1 — Pass by Value (1.1 ~ 1.3 완주)
✅ Phase 2 — 컬렉션 프레임워크 (2.1 ~ 2.6 완주)
🚀 Phase 3 — 해시의 원리 (2/4 진행)

총: 11/43 Unit 작성 (약 26%)

---