🎯 Unit 6.4 — HashMap 내부 구조 ★★★

F-lab Java 1주차 / Phase 6 / Unit 6.4 본격 학습 자료 — Phase 6 의 정점!
9-섹션 마스터 프롬프트 형식으로 깊이 파헤친다.

선수 지식: Phase 4-5 (메모리, GC), Unit 6.1-6.3 (String, 컬렉션 기초)
다음 Unit: 6.5 — TreeMap, LinkedHashMap

이 Unit의 의미: 자바 개발자가 가장 자주 쓰는 자료구조.
면접 최단골 중의 최단골 (★★★) — hashCode + equals, 해시 충돌, Treeification.
모든 캐시, 모든 ID 매핑, 모든 그룹핑의 기반.

---

🌍 1. 세상 속 비유

HashMap = "우체국 사물함"

대형 우체국의 사물함 시스템을 상상해보세요.

시나리오 1 — 사물함 없는 우체국 (List 만 있는 세상)

편지 더미:
[Alice 편지][Bob 편지][Charlie 편지][David 편지]...

• "Charlie 편지 가져와" → 모든 편지를 처음부터 확인
• 1만 명이면 → 평균 5천 번 확인
• → O(n) 시간

---

시나리오 2 — 사물함 있는 우체국 (HashMap)

사물함:
[101] [102] [103] [104] [105] ... [999]
 ↓     ↓     ↓     ↓
Alice  -    Bob   Charlie
편지       편지   편지

규칙: "이름 → 사물함 번호" 변환 함수 (해시 함수)

• "Alice" → hash("Alice") % 1000 = 101
• "Bob" → hash("Bob") % 1000 = 103
• "Charlie" → hash("Charlie") % 1000 = 104

찾기:

• "Charlie 편지" → hash 계산 → 104번 사물함 → 즉시!
• → O(1) 시간

---

시나리오 3 — 사물함 충돌 (해시 충돌)

"Alice"  → 101번
"David"  → 101번 (우연히 같은 번호!)

해결: 한 사물함에 여러 편지 보관 가능

사물함 101:
  [Alice 편지] → [David 편지]
        ↑           ↑
     이름 확인 후 정확한 편지 선택

→ "Alice" 찾기: 사물함 101 → Alice 편지 (이름 비교)

---

핵심 한 문장

"HashMap = 배열 (사물함) + 연결 리스트/트리 (충돌 해결) — O(1) 평균, O(log n) 최악."

비유 정리:

비유	HashMap 개념
사물함 번호	배열 인덱스 (bucket)
이름 → 번호 변환	hashCode() 메서드
같은 사물함에 여러 편지	해시 충돌 (Chaining)
사물함 안에서 이름 비교	equals() 메서드
사물함 늘리기	Rehashing (capacity 확장)

---

또 다른 비유 — "도서관 십진분류법"

책 = key, 분류 번호 = hash, 책장 = bucket

"자바의 정석" → 005 (컴퓨터 분야)
"이상한 나라의 앨리스" → 843 (영문학)
"수학의 정석" → 510 (수학)

찾기:
1. 책 제목 → 분류 번호 계산 (hashCode)
2. 분류 번호 → 책장 위치 (인덱스)
3. 책장에서 책 찾기 (equals 로 정확히 비교)

→ 빠르게 책 찾기.

---

🔥 2. 탄생 배경

"수십만 데이터에서 즉시 찾고 싶다" — 해시 테이블의 등장

1950년대 이전 — 검색은 느렸다

데이터 검색의 옵션:

• 순차 탐색: O(n)
• 정렬 후 이진 탐색: O(log n)
• → 여전히 느림

---

1953년 — 해시 테이블의 발명

IBM 의 Hans Peter Luhn 이 제안:

• 해시 함수 로 키를 인덱스로 변환
• 배열에 직접 저장
• → O(1) 평균 시간

핵심 아이디어:

key → hash(key) → array[hash(key)] = value

---

자바의 답 — HashMap (Java 1.2, 1998)

public class HashMap<K, V> {
    transient Node<K,V>[] table;  // 배열 (bucket)
    transient int size;           // 요소 수
    
    static class Node<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;  // 연결 리스트
    }
}

핵심 구성:
1. 배열 (table): 고정 위치 접근
2. 연결 리스트 (Node.next): 충돌 처리
3. 트리 (Java 8+): 충돌 너무 많을 때

---

핵심 도구 — hashCode + equals

hashCode 의 역할

public class Object {
    public native int hashCode();
    public boolean equals(Object obj) {
        return (this == obj);
    }
}

용도: 객체를 정수 인덱스 로 변환.

"Alice".hashCode()  // 63350368
"Bob".hashCode()    // 66486

---

equals 의 역할

같은 hashCode 인 두 객체가 진짜 같은가? 검증.

String a = "Alice";
String b = "Alice";
a.hashCode() == b.hashCode();  // true (당연)
a.equals(b);                   // true (값 비교)

---

자바 컨벤션 — equals + hashCode 계약

규칙 1: a.equals(b) 가 true 라면, a.hashCode() == b.hashCode() 도 반드시 true.

규칙 2: a.hashCode() == b.hashCode() 라고 해서 a.equals(b) 가 true 인 건 아님 (충돌 가능).

즉:

• equals → hashCode (한 방향만 보장)
• equals 오버라이드 시 → hashCode 도 반드시 오버라이드

---

위반 시 — HashMap 망가짐

// ❌ equals 만 오버라이드, hashCode 안 함
public class Customer {
    private String name;
    
    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Customer)) return false;
        return name.equals(((Customer) o).name);
    }
    // hashCode() 오버라이드 X → Object 의 기본 (메모리 주소 기반)
}

// 사용
Map<Customer, Integer> map = new HashMap<>();
map.put(new Customer("Alice"), 100);
map.get(new Customer("Alice"));  // null! (다른 hashCode)

→ HashMap 의 정확성이 깨짐.

---

핵심 통찰

"HashMap 의 마법 = hashCode (위치 결정) + equals (정확성 검증) + 적절한 Bucket 크기."

셋 중 하나만 어긋나도 O(n) 으로 떨어지거나 정확성이 깨진다. 자바의 Object 가 hashCode/equals 두 메서드를 기본 제공하는 이유 — 모든 객체는 HashMap 의 키가 될 수 있어야 한다는 자바의 철학.

---

💣 3. 없으면 생기는 문제

시나리오 1: ILIC 의 고객 캐시 — equals만 오버라이드

// ❌ 운영 사고 코드
public class Customer {
    private String customerId;
    private String name;
    
    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Customer)) return false;
        return customerId.equals(((Customer) o).customerId);
    }
    
    // hashCode() 오버라이드 X
}

@Service
public class CustomerCacheService {
    private Map<Customer, CustomerInfo> cache = new HashMap<>();
    
    public CustomerInfo get(Customer key) {
        return cache.get(key);  // ❌ 항상 null 반환!
    }
}

문제:

• DB 에서 매번 새 Customer 객체 생성
• equals 는 customerId 비교 → true
• 그러나 hashCode 가 다름 → 다른 bucket 검색
• → 캐시 히트율 0%

증상:

• 캐시 안 먹힘 → DB 부하 ↑
• API 응답 시간 느려짐
• 왜인지 모름

해결:

@Override
public int hashCode() {
    return Objects.hash(customerId);
}

---

시나리오 2: 면접 단골 질문

Q: "HashMap 의 내부 구조를 설명해주세요"
A: "음... 키 밸류 저장하는 자료구조에요"  ❌

시니어 답변 (이 Unit 의 목표):
1. 배열 (bucket) + 연결 리스트 + 트리 (Java 8+)
2. hashCode() 로 위치 계산, equals() 로 정확성 검증
3. Load Factor (0.75) 도달 시 Rehashing (2배 확장)
4. TREEIFY_THRESHOLD = 8 — 한 bucket 에 8개 이상이면 Red-Black Tree 로 전환
5. capacity 는 2의 거듭제곱 — 비트 연산 최적화 (hash & (n-1))

---

시나리오 3: 가변 객체를 키로 사용

// ❌ 위험
List<String> key = new ArrayList<>(List.of("A", "B"));
Map<List<String>, Integer> map = new HashMap<>();
map.put(key, 100);

// 키 수정
key.add("C");

// 조회
map.get(key);  // null! (hashCode 변경됨)

문제:

• key 의 hashCode 가 변경됨
• HashMap 은 변경된 hashCode 로 다른 bucket 검색
• 원래 들어있던 위치는 못 찾음 → 메모리 누수

해결: 불변 객체를 키로 사용 (String, Integer, 불변 클래스).

---

시나리오 4: 해시 충돌 공격 (HashDoS)

// 모든 키가 같은 hashCode 반환
public class BadKey {
    private int id;
    
    @Override
    public int hashCode() {
        return 0;  // ❌ 모두 같은 hash
    }
    
    @Override
    public boolean equals(Object o) {
        return ((BadKey) o).id == id;
    }
}

// 사용
Map<BadKey, String> map = new HashMap<>();
for (int i = 0; i < 100000; i++) {
    map.put(new BadKey(i), "value");
}

// 모두 같은 bucket 에 들어감 → 연결 리스트 길이 10만!
// O(1) → O(n)

과거 (Java 7):

• 모든 충돌 → 연결 리스트
• 검색 O(n)
• HashDoS 공격 가능

Java 8+ 의 답:

• 8개 초과 시 → Red-Black Tree 로 전환
• 검색 O(log n)
• HashDoS 완화

---

시나리오 5: 멀티 스레드에서 HashMap

@Service
public class GlobalCacheService {
    private Map<String, String> cache = new HashMap<>();  // ❌ 위험
    
    public void put(String k, String v) {
        cache.put(k, v);  // 여러 스레드 동시 호출 → 데이터 손상
    }
}

문제 (특히 Java 7 이전):

• Rehashing 중 여러 스레드 동시 진입
• 연결 리스트가 순환 으로 변환될 수 있음
• 다음 get() → 무한 루프 + CPU 100%

해결:

private Map<String, String> cache = new ConcurrentHashMap<>();  // ✓

---

시나리오 6: ILIC 의 등급별 카운트

// ❌ 비효율
List<Customer> customers = ...;
Map<String, Integer> gradeCounts = new HashMap<>();

for (Customer c : customers) {
    String grade = c.getGrade();
    if (gradeCounts.containsKey(grade)) {
        gradeCounts.put(grade, gradeCounts.get(grade) + 1);
        // ❌ 3번의 hashCode 계산 + 2번의 equals
    } else {
        gradeCounts.put(grade, 1);
    }
}

문제: 매 반복마다 3번의 해시 연산.

해결 1: getOrDefault

gradeCounts.put(grade, gradeCounts.getOrDefault(grade, 0) + 1);
// 2번의 해시 연산

해결 2: merge (Java 8+)

gradeCounts.merge(grade, 1, Integer::sum);
// 1번의 해시 연산

해결 3: Stream

Map<String, Long> counts = customers.stream()
    .collect(Collectors.groupingBy(
        Customer::getGrade,
        Collectors.counting()));

---

영향 정리

시나리오	모르면	알면
equals/hashCode	캐시 안 먹힘	정확한 동작
면접 답변	표면적	시니어
가변 키	메모리 누수	불변 키 사용
해시 충돌 공격	HashDoS	Tree 로 완화
멀티스레드	무한 루프	ConcurrentHashMap
ILIC 통계	O(n²) 가능	O(n)

→ HashMap 이해는 자바 시니어의 핵심 역량.

---

✅ 4. 해결책 — HashMap 의 정확한 이해

기본 사용

Map<String, Customer> map = new HashMap<>();
map.put("alice", new Customer("Alice"));
map.put("bob", new Customer("Bob"));

Customer alice = map.get("alice");  // O(1)
boolean has = map.containsKey("alice");  // O(1)
map.remove("alice");  // O(1)

// 순회
for (Map.Entry<String, Customer> entry : map.entrySet()) {
    String key = entry.getKey();
    Customer value = entry.getValue();
}

---

주요 메서드와 시간 복잡도

HashMap<String, Integer> map = new HashMap<>();

// === 추가 ===
map.put("A", 1);              // O(1) 평균
map.putIfAbsent("A", 100);    // 없으면 추가 — O(1)
map.computeIfAbsent("B", k -> 2);  // 없으면 람다로 계산
map.merge("A", 1, Integer::sum);   // 있으면 합치고, 없으면 추가

// === 조회 ===
map.get("A");                 // O(1) 평균, O(log n) 최악
map.getOrDefault("X", 0);     // 없으면 기본값
map.containsKey("A");         // O(1)
map.containsValue(1);         // O(n) — 모든 value 순회

// === 삭제 ===
map.remove("A");              // O(1)
map.remove("A", 1);           // value 도 일치할 때만

// === 정보 ===
map.size();
map.isEmpty();
map.clear();

// === 순회 (요소 순서는 보장 X) ===
map.keySet();      // Set<K>
map.values();      // Collection<V>
map.entrySet();    // Set<Map.Entry<K,V>>

// === Java 8+ 람다 ===
map.forEach((k, v) -> System.out.println(k + "=" + v));
map.replaceAll((k, v) -> v * 2);

---

비교 표 ⭐⭐ (Map 구현체 선택)

항목	HashMap	Hashtable	ConcurrentHashMap	LinkedHashMap	TreeMap
순서	없음	없음	없음	삽입 순서	정렬
null key	✓	✗	✗	✓	✗
null value	✓	✗	✗	✓	✓
Thread-Safe	✗	✓ (낡음)	✓ ⭐	✗	✗
시간 복잡도	O(1)	O(1)	O(1)	O(1)	O(log n)
권장도	단일 ⭐	❌ Legacy	멀티 ⭐	순서 필요	정렬 필요

---

선택 가이드 ⭐

Map 이 필요하다
        ↓
순서가 중요한가?
├── 정렬된 순서 → TreeMap (Unit 6.5)
├── 삽입 순서 → LinkedHashMap (Unit 6.5)
└── 무관 → 다음 단계
        ↓
멀티 스레드 환경?
├── YES → ConcurrentHashMap ⭐
└── NO  → HashMap ⭐

90% 이상의 경우 → HashMap 또는 ConcurrentHashMap.

---

초기 capacity 와 load factor

// 기본
new HashMap<>();  // capacity 16, loadFactor 0.75

// 큰 데이터
new HashMap<>(1024);  // capacity 1024

// 세밀 조정
new HashMap<>(1024, 0.6f);  // capacity 1024, loadFactor 0.6

계산:

• 100만 개 저장 예상
• loadFactor 0.75
• 필요 capacity: 1,000,000 / 0.75 ≈ 1,333,334
• 2의 거듭제곱: 2,097,152 (2²¹)

new HashMap<>(2_097_152);  // 미리 할당 → rehashing 회피

---

Object 의 equals + hashCode 오버라이드 — 표준 패턴

public class Customer {
    private String customerId;
    private String name;
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Customer)) return false;
        Customer c = (Customer) o;
        return Objects.equals(customerId, c.customerId);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(customerId);  // ★ 반드시 오버라이드
    }
}

또는 IDE 자동 생성:

• IntelliJ: Cmd + N → "equals and hashCode"
• 권장 — 일관성 보장

---

Java 16+ Record — equals/hashCode 자동

public record Customer(String customerId, String name) {
    // equals, hashCode, toString 자동 생성!
    // accessor 메서드 customerId(), name() 자동 생성
}

// 사용
Customer alice = new Customer("C001", "Alice");
Customer alice2 = new Customer("C001", "Alice");

alice.equals(alice2);   // true
alice.hashCode() == alice2.hashCode();  // true

Map<Customer, Integer> map = new HashMap<>();
map.put(alice, 100);
map.get(alice2);  // 100 ✓

→ 불변 데이터 클래스의 표준.

---

🏗️ 5. 내부 동작 원리

HashMap 의 내부 구조

public class HashMap<K, V> {
    // 핵심 필드
    transient Node<K,V>[] table;       // 배열 (bucket)
    transient int size;                // 요소 수
    int threshold;                     // 다음 rehash 임계 (= capacity * loadFactor)
    final float loadFactor;            // 0.75 기본
    
    // 상수
    static final int DEFAULT_INITIAL_CAPACITY = 16;     // 1 << 4
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final int TREEIFY_THRESHOLD = 8;             // 트리화 임계
    static final int UNTREEIFY_THRESHOLD = 6;           // 트리 → 리스트 임계
    static final int MIN_TREEIFY_CAPACITY = 64;         // 트리화 최소 capacity
    
    // Node 정의
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
    }
    
    // Tree Node (Java 8+)
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;
        boolean red;
    }
}

---

put() 의 동작 단계 ⭐⭐⭐

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    //                                                ↑
    //                              상위 16비트 ↔ 하위 16비트 XOR
    //                              (해시 분산 향상)
}

final V putVal(int hash, K key, V value, ...) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // 1. table 이 null 이면 초기화 (lazy)
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // 2. bucket 위치 계산: hash & (n - 1)
    if ((p = tab[i = (n - 1) & hash]) == null) {
        // 빈 bucket → 그냥 추가
        tab[i] = new Node<>(hash, key, value, null);
    } else {
        // 충돌 발생!
        Node<K,V> e; K k;
        
        // 3. 같은 키인지 확인 (hash + equals)
        if (p.hash == hash && 
            ((k = p.key) == key || (key != null && key.equals(k)))) {
            e = p;  // 같은 키 → 값만 교체
        }
        // 4. Tree Node 인 경우
        else if (p instanceof TreeNode) {
            e = ((TreeNode<K,V>)p).putTreeVal(...);
        }
        // 5. 연결 리스트 순회
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = new Node<>(hash, key, value, null);
                    
                    // 6. 트리화 임계 도달 시 트리로 전환
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && 
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 7. 같은 키였으면 값 교체
        if (e != null) {
            V oldValue = e.value;
            e.value = value;
            return oldValue;
        }
    }
    
    // 8. size 증가, 임계 초과 시 rehash
    ++modCount;
    if (++size > threshold)
        resize();
    return null;
}

---

시각화 — put() 흐름

key = "Alice", value = customerObj
       ↓
[1. hashCode 계산]
"Alice".hashCode() = 63350368

[2. 해시 분산]
hash = 63350368 ^ (63350368 >>> 16) = ...

[3. bucket 인덱스 계산]
n = 16 (capacity)
i = hash & (n - 1) = hash & 15 = 5

[4. table[5] 확인]
table[5] == null?
├── YES → 새 Node 추가
└── NO  → 충돌!
      ↓
   [5. 충돌 처리]
   기존 bucket 의 첫 노드 확인
   ├── 같은 키 (equals) → 값만 교체
   ├── TreeNode → 트리에 삽입
   └── 일반 Node → 연결 리스트 순회
         ↓
      마지막에 추가
      ↓
   [6. binCount >= 7?]
      └── YES → treeifyBin()
      
[7. size++]
[8. size > threshold? → resize()]

---

get() 의 동작

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        
        // 1. 첫 노드가 일치하는가?
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        
        // 2. 그 외는 다음 노드 또는 트리 탐색
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

핵심:
1. hash 계산
2. bucket 위치 (hash & (n-1))
3. 그 bucket 의 첫 노드 → 키 비교
4. 다음 노드 또는 트리 탐색

---

capacity 가 2의 거듭제곱인 이유 ⭐

// 일반적인 % 연산
int index = hash % n;  // 느림 (CPU divide)

// 2의 거듭제곱일 때 — 비트 AND
int index = hash & (n - 1);  // 빠름 (CPU and)

예시 (n = 16):

n - 1 = 15 (이진수: 0000 1111)

hash = 12345678 (이진수: ... 0010 0011 0001 0001 1110)
                              & 0000 0000 0000 0000 1111
                              = 0000 0000 0000 0000 1110 = 14

→ index = 14

효과:

• % 보다 5~10배 빠름
• HashMap 의 핵심 최적화

---

해시 분산 — hash ^ (hash >>> 16)

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

왜?: hashCode 의 상위 비트도 활용 하기 위해.

문제: hash & (n-1) 은 하위 비트만 사용.

예: 두 객체의 hashCode 가

객체 A: 0xABCD0001 (하위 4비트: 0001)
객체 B: 0xFFFF0001 (하위 4비트: 0001)

→ n=16 일 때 둘 다 인덱스 1! (충돌)

해결: 상위 16비트와 XOR

A.hash = 0xABCD0001 ^ 0x0000ABCD = 0xABCDABCC (하위 비트가 다름)
B.hash = 0xFFFF0001 ^ 0x0000FFFF = 0xFFFFFFFE (하위 비트가 다름)

→ 다른 인덱스에 분산!

---

Treeification (Java 8+) ⭐⭐

언제 트리화?

static final int TREEIFY_THRESHOLD = 8;       // 한 bucket 의 노드가 8개 이상
static final int MIN_TREEIFY_CAPACITY = 64;   // 그러나 capacity 가 64 미만이면 rehash 우선

조건: bucket 안의 연결 리스트가 8개 초과 + capacity ≥ 64.

---

Red-Black Tree 로 전환

Before (연결 리스트):

bucket[5]: A → B → C → D → E → F → G → H → I (9개)

After (Red-Black Tree):

bucket[5]:
        E (black)
       / \
      C   G
     / \  / \
    A  D F  I
        / 
       H

효과:

• 연결 리스트 검색: O(n)
• 트리 검색: O(log n)
• HashDoS 공격 완화

---

Untreeification

static final int UNTREEIFY_THRESHOLD = 6;

resize 후 트리 노드가 6개 이하 가 되면 → 연결 리스트로 복귀.

(트리 관리 비용이 더 클 수 있으므로)

---

Rehashing (resize) ⭐

언제?

if (++size > threshold)
    resize();

threshold = capacity × loadFactor = 16 × 0.75 = 12

13번째 추가 시 → resize 발동.

---

어떻게?

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    
    // 1. 새 capacity = 2배
    int newCap = oldCap << 1;  // oldCap * 2
    int newThr = (int)(newCap * loadFactor);
    
    // 2. 새 배열 생성
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    
    // 3. 기존 요소를 모두 새 배열로 재배치
    for (int j = 0; j < oldCap; ++j) {
        Node<K,V> e;
        if ((e = oldTab[j]) != null) {
            // 단일 노드
            if (e.next == null) {
                newTab[e.hash & (newCap - 1)] = e;
            }
            // 트리 노드
            else if (e instanceof TreeNode) {
                ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
            }
            // 연결 리스트
            else {
                // ... 두 그룹으로 분리 (lo, hi)
            }
        }
    }
    return newTab;
}

---

Java 8 의 resize 최적화

기존 방식 (Java 7):

• 모든 노드의 새 인덱스를 다시 계산
• O(n) 비용

Java 8 의 영리한 방식:

• capacity 2배 확장 시 → 비트 1개 추가
• 노드는 두 그룹 으로 갈라짐:
  • (hash & oldCap) == 0 → 같은 인덱스 유지
  • (hash & oldCap) != 0 → 인덱스 + oldCap 으로 이동

효과: 인덱스 재계산 없이 분류 → 빠름.

---

메모리 그림

HashMap 의 내부:

table = [
  null,
  Node(key=A, value=1) → Node(key=B, value=2),  // 충돌 → 연결리스트
  null,
  null,
  Node(key=C, value=3),
  TreeNode(...),  // 8개 초과 → Tree
  null,
  ...
]

capacity = 16 (table.length)
size = 5 (현재 요소 수)
threshold = 12 (capacity * 0.75)

---

💻 6. 실전 코드 예시

예시 1: ILIC 의 고객 캐시

@Service
public class CustomerCacheService {
    
    // ✓ 큰 capacity 미리 설정 — Rehashing 회피
    private final Map<String, Customer> cache = new HashMap<>(10000);
    
    public void put(Customer customer) {
        cache.put(customer.getCustomerId(), customer);
    }
    
    public Customer get(String customerId) {
        return cache.get(customerId);  // O(1) 평균
    }
    
    public Optional<Customer> findByName(String name) {
        // ⚠️ value 검색은 O(n) — 비효율
        return cache.values().stream()
            .filter(c -> c.getName().equals(name))
            .findFirst();
    }
    
    // 더 좋은 방법: 별도 인덱스
    private final Map<String, String> nameToIdIndex = new HashMap<>();
    
    public void putWithIndex(Customer customer) {
        cache.put(customer.getCustomerId(), customer);
        nameToIdIndex.put(customer.getName(), customer.getCustomerId());
    }
    
    public Optional<Customer> findByNameFast(String name) {
        String id = nameToIdIndex.get(name);  // O(1)
        return id == null ? Optional.empty() : Optional.of(cache.get(id));
    }
}

---

예시 2: equals + hashCode 표준 구현

public class Cargo {
    private final String cargoId;
    private final String name;
    private final int weight;
    
    // ✓ Java 16+ 권장: Record 사용
    // public record Cargo(String cargoId, String name, int weight) {}
    
    // 또는 일반 클래스 + 명시적 구현
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Cargo)) return false;
        Cargo cargo = (Cargo) o;
        return Objects.equals(cargoId, cargo.cargoId);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(cargoId);
    }
    
    // toString 도 권장
    @Override
    public String toString() {
        return "Cargo{cargoId='" + cargoId + "', name='" + name + "'}";
    }
}

---

예시 3: ILIC 의 등급별 매출 집계

public class SalesAggregator {
    
    // ✓ Java 8+ merge 활용
    public Map<String, Long> aggregateByGrade(List<Order> orders) {
        Map<String, Long> result = new HashMap<>();
        
        for (Order order : orders) {
            // grade 별 매출 합계
            result.merge(
                order.getCustomerGrade(),
                order.getAmount(),
                Long::sum
            );
        }
        
        return result;
    }
    
    // ✓ 더 우아한 방법: Stream
    public Map<String, Long> aggregateByGradeStream(List<Order> orders) {
        return orders.stream()
            .collect(Collectors.groupingBy(
                Order::getCustomerGrade,
                Collectors.summingLong(Order::getAmount)
            ));
    }
    
    // ✓ 다중 키 그룹핑
    public Map<String, Map<String, Long>> aggregateByGradeAndPort(List<Order> orders) {
        return orders.stream()
            .collect(Collectors.groupingBy(
                Order::getCustomerGrade,
                Collectors.groupingBy(
                    Order::getOriginPort,
                    Collectors.summingLong(Order::getAmount)
                )
            ));
    }
}

---

예시 4: 멀티스레드 캐시 — ConcurrentHashMap

@Service
public class FareCache {
    
    // ✓ 멀티스레드 안전
    private final ConcurrentHashMap<String, BigDecimal> cache = new ConcurrentHashMap<>();
    
    public BigDecimal getFare(String routeKey) {
        // computeIfAbsent — atomic 연산
        return cache.computeIfAbsent(routeKey, this::calculateFare);
    }
    
    private BigDecimal calculateFare(String routeKey) {
        // 무거운 계산 (DB 조회, API 호출 등)
        return fareCalculator.calculate(routeKey);
    }
    
    public void invalidate(String routeKey) {
        cache.remove(routeKey);
    }
    
    public void invalidateAll() {
        cache.clear();
    }
}

computeIfAbsent 의 마법:

• 키가 없으면 → 람다 실행 → 결과 저장
• 키가 있으면 → 값 반환 (람다 실행 X)
• 원자성 보장 (스레드 안전)

---

예시 5: HashMap 의 함정 시연

public class HashMapPitfalls {
    
    // ❌ 함정 1: equals 만 오버라이드
    public static void pitfall1() {
        Map<BadKey, String> map = new HashMap<>();
        BadKey k1 = new BadKey("A");
        BadKey k2 = new BadKey("A");
        
        map.put(k1, "value");
        System.out.println(map.get(k2));  // null!
        // (BadKey 가 hashCode 오버라이드 X)
    }
    
    // ❌ 함정 2: 가변 키
    public static void pitfall2() {
        Map<List<Integer>, String> map = new HashMap<>();
        List<Integer> key = new ArrayList<>(List.of(1, 2));
        
        map.put(key, "value");
        key.add(3);  // hashCode 변경!
        
        System.out.println(map.get(key));  // null!
        System.out.println(map.containsKey(key));  // false!
    }
    
    // ❌ 함정 3: 멀티스레드 + HashMap
    public static void pitfall3() {
        Map<Integer, Integer> map = new HashMap<>();
        
        // 여러 스레드가 동시 put
        IntStream.range(0, 100).parallel().forEach(i -> {
            map.put(i, i * 2);  // 데이터 손상 가능
        });
        // 결과: size 가 100 미만이거나, 무한 루프 발생 가능
    }
    
    // ✓ 안전
    public static void safe() {
        Map<Integer, Integer> map = new ConcurrentHashMap<>();
        IntStream.range(0, 100).parallel().forEach(i -> {
            map.put(i, i * 2);  // 안전
        });
    }
}

---

예시 6: 양방향 매핑

public class BidirectionalMap {
    
    // ILIC: 고객 ID ↔ 이메일 매핑
    private final Map<String, String> idToEmail = new HashMap<>();
    private final Map<String, String> emailToId = new HashMap<>();
    
    public void put(String customerId, String email) {
        // 기존 매핑 제거
        String oldEmail = idToEmail.put(customerId, email);
        if (oldEmail != null) {
            emailToId.remove(oldEmail);
        }
        
        String oldId = emailToId.put(email, customerId);
        if (oldId != null) {
            idToEmail.remove(oldId);
        }
    }
    
    public String getEmail(String customerId) {
        return idToEmail.get(customerId);
    }
    
    public String getId(String email) {
        return emailToId.get(email);
    }
}

---

예시 7: HashMap 순회 패턴

public class HashMapIteration {
    
    public void iterate(Map<String, Customer> map) {
        // 1. entrySet — 가장 효율
        for (Map.Entry<String, Customer> entry : map.entrySet()) {
            String key = entry.getKey();
            Customer value = entry.getValue();
            // ...
        }
        
        // 2. keySet — 키만 필요할 때
        for (String key : map.keySet()) {
            // ...
        }
        
        // 3. values — 값만 필요할 때
        for (Customer customer : map.values()) {
            // ...
        }
        
        // 4. forEach (Java 8+)
        map.forEach((key, value) -> {
            System.out.println(key + " = " + value.getName());
        });
        
        // 5. Stream
        map.entrySet().stream()
            .filter(e -> e.getValue().isVip())
            .forEach(e -> System.out.println(e.getKey()));
    }
    
    // ❌ 함정: 순회 중 수정
    public void unsafeRemoval(Map<String, Customer> map) {
        for (String key : map.keySet()) {
            if (map.get(key).isExpired()) {
                map.remove(key);  // ConcurrentModificationException!
            }
        }
    }
    
    // ✓ Iterator
    public void safeRemoval1(Map<String, Customer> map) {
        Iterator<Map.Entry<String, Customer>> iter = map.entrySet().iterator();
        while (iter.hasNext()) {
            if (iter.next().getValue().isExpired()) {
                iter.remove();
            }
        }
    }
    
    // ✓ Java 8+ removeIf
    public void safeRemoval2(Map<String, Customer> map) {
        map.entrySet().removeIf(e -> e.getValue().isExpired());
    }
}

---

⚠️ 7. 주의사항 & 흔한 실수

실수 1: equals 만 오버라이드, hashCode 안 함

// ❌ 위험
public class Customer {
    @Override
    public boolean equals(Object o) { /* customerId 비교 */ }
    // hashCode() 오버라이드 X
}

해결: 둘 다 오버라이드 (또는 Record 사용).

---

실수 2: 가변 객체를 키로 사용

// ❌ 위험
Map<List<String>, Integer> map = new HashMap<>();
List<String> key = new ArrayList<>();
map.put(key, 1);
key.add("X");  // hashCode 변경 → 메모리 누수

해결: 불변 객체 (String, Integer, 불변 클래스).

---

실수 3: 멀티스레드 + HashMap

// ❌ 데이터 손상 + 무한 루프 가능
Map<String, String> map = new HashMap<>();

해결: ConcurrentHashMap.

---

실수 4: containsValue 남용

// ❌ O(n)
if (map.containsValue(target)) { ... }

해결: value → key 인덱스 별도 유지 (양방향 매핑).

---

실수 5: Iterator 없이 순회 중 수정

// ❌ ConcurrentModificationException
for (String key : map.keySet()) {
    map.remove(key);
}

해결: Iterator.remove() 또는 removeIf.

---

실수 6: capacity 미설정

// ❌ 100만 데이터에 기본 capacity
Map<String, String> map = new HashMap<>();
for (int i = 0; i < 1_000_000; i++) {
    map.put(...);  // 약 17번 rehashing!
}

해결:

Map<String, String> map = new HashMap<>(2_097_152);  // 2의 거듭제곱

---

실수 7: null 키/값 혼동

HashMap<String, String> hm = new HashMap<>();
hm.put(null, "value");  // ✓ 가능

Hashtable<String, String> ht = new Hashtable<>();
ht.put(null, "value");  // NullPointerException

ConcurrentHashMap<String, String> chm = new ConcurrentHashMap<>();
chm.put(null, "value");  // NullPointerException

원칙: ConcurrentHashMap 은 null 키/값 허용 X.

---

실수 8: 순서 기대

HashMap<Integer, String> map = new HashMap<>();
map.put(1, "A");
map.put(2, "B");
map.put(3, "C");

for (Map.Entry<Integer, String> e : map.entrySet()) {
    System.out.println(e.getKey());  // 순서 보장 X!
}

해결:

• 삽입 순서 → LinkedHashMap (Unit 6.5)
• 정렬 순서 → TreeMap (Unit 6.5)

---

🔗 8. 연관 개념 맵

Phase 6 (데이터 다루기) 에서의 위치

[Unit 6.1: String + Constant Pool] ✓
        ↓
[Unit 6.2: StringBuilder vs StringBuffer] ✓
        ↓
[Unit 6.3: ArrayList vs LinkedList] ✓
        ↓
[Unit 6.4: HashMap 내부 구조] ★★★ ← 지금 여기 (Phase 6 정점)
        ↓
[Unit 6.5: TreeMap, LinkedHashMap]

---

Phase 4-5 와의 연결

Phase	연결
4.1 (JVM 메모리)	HashMap 의 배열은 Heap 에
5.1 (GC)	큰 HashMap 의 GC 부담
6.1 (String)	String 의 hashCode 캐싱
6.3 (ArrayList)	bucket 안의 연결 리스트

---

자바 컬렉션의 위치

Map (인터페이스)
├── HashMap ⭐ (이 Unit)
├── LinkedHashMap (Unit 6.5)
├── TreeMap (Unit 6.5)
├── ConcurrentHashMap (멀티스레드)
└── Hashtable (legacy)

---

면접 단골 질문 매핑

질문	이 Unit 에서의 답
HashMap 내부 구조?	배열 + 연결 리스트 + 트리
equals + hashCode 관계?	계약 (equals 같으면 hashCode 같아야)
해시 충돌 처리?	Chaining + Treeification (Java 8+)
Load Factor 의미?	0.75 — 시간/공간 trade-off
Treeification 임계?	TREEIFY_THRESHOLD = 8
capacity 가 2^n 인 이유?	hash & (n-1) 비트 연산
HashMap vs ConcurrentHashMap?	동시성 차이

---

다른 언어와 비교

언어	Map 구현
Java	HashMap
Python	dict
JavaScript	Map, Object
C++	std::unordered_map
Go	map[K]V
Rust	HashMap<K, V>

→ 거의 모든 언어에 해시 테이블 존재.

---

📝 9. 핵심 요약 — 3줄 정리

1️⃣ HashMap = 배열 + 연결 리스트 + 트리 (Java 8+).

배열 (bucket) 으로 O(1) 접근. 연결 리스트 로 충돌 처리. Red-Black Tree 로 충돌 폭증 시 O(log n) 보장 (TREEIFY_THRESHOLD=8). capacity 는 2의 거듭제곱 — hash & (n-1) 비트 연산으로 빠른 인덱스 계산. Load Factor 0.75 도달 시 Rehashing (2배 확장).

2️⃣ hashCode + equals 계약 — 같으면 hashCode 도 같아야.

a.equals(b) → a.hashCode() == b.hashCode() 반드시 보장. 역은 성립 X (충돌 가능). equals 오버라이드 시 hashCode 도 반드시 오버라이드. 위반 시 → HashMap 망가짐 (캐시 안 먹힘, 메모리 누수). Record (Java 16+) 또는 Objects.hash() + IDE 자동 생성 권장. 불변 키 사용 (가변 키는 메모리 누수 위험).

3️⃣ 실무 원칙 — capacity 미리 설정, 멀티스레드 시 ConcurrentHashMap, Java 8+ 메서드 활용.

큰 데이터는 new HashMap<>(예상크기 / 0.75) 로 미리 할당 → Rehashing 회피. 멀티스레드 환경 = ConcurrentHashMap (HashMap 은 무한 루프 위험). merge(), computeIfAbsent() 등 Java 8+ 메서드로 1번의 해시 연산. 순서 필요 = LinkedHashMap (Unit 6.5). 정렬 필요 = TreeMap. ILIC 의 모든 캐시/인덱스/그룹핑의 핵심 도구.

---

🎓 학습 자기 점검

기본 이해

• HashMap 의 내부 구조를 그림으로 그릴 수 있다 (배열 + 연결 리스트)
• hashCode + equals 의 계약을 정확히 안다
• capacity 가 2의 거듭제곱인 이유를 안다 (hash & (n-1))
• Load Factor 와 Rehashing 의 관계를 안다

실전 적용

• equals + hashCode 를 항상 함께 오버라이드한다
• 큰 데이터 시 capacity 를 미리 설정한다
• 멀티스레드 환경에서 ConcurrentHashMap 을 선택한다
• Java 8+ 메서드 (merge, computeIfAbsent) 를 활용한다

면접 대비 (5분 답변)

• "HashMap 내부 구조?" 답변 가능 (배열 + 리스트 + 트리)
• "Java 8+ Treeification?" 답변 가능 (TREEIFY_THRESHOLD=8)
• "Load Factor 0.75 의미?" 답변 가능
• "ConcurrentHashMap 차이?" 답변 가능

자기 점검 질문 답변

Q1: hashCode 만 같고 equals 가 false 인 두 객체를 HashMap 에 넣으면 어떻게 되는가?

한 줄 답: 같은 bucket 의 연결 리스트 에 둘 다 저장됨. 검색 시 hashCode 로 bucket 찾고, equals 로 정확한 노드 식별.

상세 설명:

시나리오 설정

public class Customer {
    private String customerId;
    
    @Override
    public int hashCode() {
        return 5;  // 모두 5 반환 (극단적 예)
    }
    
    @Override
    public boolean equals(Object o) {
        return customerId.equals(((Customer) o).customerId);
    }
}

Map<Customer, Integer> map = new HashMap<>();
map.put(new Customer("C001"), 100);
map.put(new Customer("C002"), 200);
map.put(new Customer("C003"), 300);

---

put 시 동작

iteration 1: put(C001, 100)

1. hashCode = 5
2. bucket index = 5 & (16-1) = 5
3. table[5] == null → 새 Node 추가

table[5]: Node(C001, 100)

iteration 2: put(C002, 200)

1. hashCode = 5
2. bucket index = 5
3. table[5] != null → 충돌!
4. 첫 노드 (C001) 와 equals 비교: false
5. next == null → 새 Node 를 끝에 추가

table[5]: Node(C001, 100) → Node(C002, 200)

iteration 3: put(C003, 300)

table[5]: Node(C001, 100) → Node(C002, 200) → Node(C003, 300)

---

get 시 동작

Customer key = new Customer("C002");
map.get(key);

1. hashCode = 5
2. bucket index = 5
3. table[5] 의 첫 노드 확인
4. 첫 노드 C001 과 equals 비교: false
5. next 로 이동 → C002 와 equals 비교: true!
6. 그 노드의 value 반환: 200

→ equals 로 정확한 노드 식별.

---

시간 복잡도

• 충돌 없으면: O(1)
• 충돌 1개: O(2) ≈ O(1)
• 충돌 8개: O(8) ≈ O(1)
• 충돌 100개: O(100) → 트리화 시 O(log 100)

---

Java 8+ 의 구원

8개 초과 시 → Red-Black Tree 로 전환.

Before (8개 이하):
table[5]: A → B → C → D → E → F → G → H

After (9개째 추가 시):
table[5] (Tree):
        E
       / \
      C   G
     / \  / \
    A  D F  I
        / 
       H

→ 검색 O(n) → O(log n).

---

결론

"hashCode 가 같으면 같은 bucket 에 저장. equals 로 정확한 노드 식별.
일반적으로 충돌은 거의 없으므로 O(1).
충돌이 많아도 Java 8+ 의 트리화로 최악 O(log n) 보장.
단, equals 를 잘못 구현하면 HashMap 자체가 망가짐."

---

Q2: Java 8+ 의 Treeification 은 왜 필요한가?

한 줄 답: HashDoS 공격 완화 + 최악의 성능 보장. 충돌 폭증 시 O(n) → O(log n).

상세 설명:

1. Java 7 의 문제 — HashDoS 공격

공격 시나리오:

// 악의적 사용자가 모두 같은 hashCode 를 가진 키 1만 개 전송
for (int i = 0; i < 10000; i++) {
    map.put(maliciousKey(i), value);  // 모두 hashCode = 0
}

// HashMap 의 결과:
// table[0]: Node1 → Node2 → Node3 → ... → Node10000 (연결 리스트)

검색 비용:

• O(10000) per 조회
• 1만 번 조회 → 1억 번 비교
• → CPU 100% + 서비스 마비

실제 사건:

• 2011년 Java 7 의 해시 충돌 공격 발견
• 웹 서버 마비 사례 다수

---

2. Java 8 의 답 — Red-Black Tree

조건:

• bucket 의 노드 수 > 8 (TREEIFY_THRESHOLD)
• table 의 capacity ≥ 64 (MIN_TREEIFY_CAPACITY)
  • capacity 작으면 rehash 가 더 효과적

전환:

9번째 노드 추가 시:
연결 리스트 → Red-Black Tree

효과:

검색 O(n) → O(log n)
1만 개 노드:
- 연결 리스트: 평균 5천 번 비교
- Red-Black Tree: 약 13번 비교 (log₂ 10000 ≈ 13)

---

3. 왜 8개 이상부터?

이론적 분석:

• hashCode 가 잘 분포되면 (좋은 hash function)
• 8개 이상 충돌 확률 = 포아송 분포 기준 0.00000006
• 거의 일어나지 않음

즉, 8개 이상 = "비정상" 상황:

• 의도적 공격
• 매우 나쁜 hashCode 구현

→ 그때만 트리화 (오버헤드 회피).

---

4. 왜 Red-Black Tree?

선택지:

• AVL Tree: 더 균형, 그러나 회전 더 많음
• Red-Black Tree: 약간 덜 균형, 회전 적음 (삽입/삭제 빠름)
• B-Tree: 디스크 친화 (메모리에는 불필요)

Red-Black Tree 의 강점:

• 삽입 O(log n)
• 검색 O(log n)
• 삭제 O(log n)
• 균형 보장: 최악 깊이 ≤ 2 × log n

---

5. Untreeification

resize 후 bucket 의 노드 수가 6 이하 (UNTREEIFY_THRESHOLD) 가 되면:

Tree → 연결 리스트

왜?:

• 트리는 메모리 오버헤드 큼 (TreeNode 가 Node 보다 큼)
• 적은 노드는 연결 리스트가 더 효율
• Hysteresis (이력 효과) — 6과 8의 간격으로 잦은 변환 회피

---

6. 트리화의 한계

충돌이 많아도 capacity 가 작으면:

if (tab.length < MIN_TREEIFY_CAPACITY) {
    resize();  // 트리 대신 rehash
}

이유: 작은 table 에서 충돌 = capacity 가 부족할 가능성 → rehash 가 더 효과적.

---

7. 실측 — Java 7 vs Java 8

// 모든 키가 같은 hashCode (HashDoS 시뮬레이션)
Map<BadKey, Integer> map = new HashMap<>();
for (int i = 0; i < 100000; i++) {
    map.put(new BadKey(i), i);
}

// 1만 번 조회
long start = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
    map.get(new BadKey(i % 100000));
}
long elapsed = System.currentTimeMillis() - start;

// Java 7: ~ 60초 (사실상 멈춤)
// Java 8: ~ 100ms (트리화)

차이: 600배 성능 차이.

---

8. 결론

"Treeification 은 HashMap 의 안전망.
정상 상황에서는 거의 트리화되지 않음 (8개 이상 충돌 확률 1억분의 1).
그러나 HashDoS 공격이나 잘못된 hashCode 구현 에 대비해 최악 O(log n) 보장.
Java 8+ 의 가장 중요한 컬렉션 개선 중 하나.
시니어 차별화 키워드: TREEIFY_THRESHOLD=8, MIN_TREEIFY_CAPACITY=64, Red-Black Tree, HashDoS."

---

다음 Unit으로

• TreeMap, LinkedHashMap 학습 준비 완료
• 정렬된 Map 의 사용처가 궁금하다
• 삽입 순서 유지의 활용을 만날 준비 완료