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

F-LAB JAVA · 3주차 · Phase 3 · 해시(Hash)의 원리
🎯 마스터 프롬프트 깊이 Unit — HashMap 직접 구현 가능 수준

📌 학습 목표

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

체이닝 (Chaining) 의 정확한 메커니즘과 자료구조는?
HashMap 의 Node 클래스 내부 구조 (4개 필드) 는?
put(key, value) 의 11단계 동작 을 코드 레벨로 추적할 수 있나?
get(key) 의 7단계 동작 을 추적할 수 있나?
remove(key) 의 처리 와 연결 리스트 갱신은?
resize() 의 재해싱 과 비트 트릭 (oldCap) 은?
Java 8+ 트리 변환 의 6가지 조건과 동작은?
TreeNode 의 8개 필드와 Red-Black Tree 균형 조정은?
체이닝의 공간 복잡도 와 메모리 오버헤드는?
HashMap 을 처음부터 구현 할 수 있나?

🎯 핵심 한 문장

체이닝은 "같은 버킷에 충돌한 키들을 연결 리스트 또는 트리로 보관" 하는 해결법이다.
Java 7 까지는 단일 연결 리스트, Java 8+ 부터는 버킷의 노드 수가 8 이상이면 Red-Black Tree 로 변환.
이 단순한 아이디어가 HashMap 의 O(1) 평균과 O(log n) 최악을 모두 보장한다.
이 Unit 을 마치면 HashMap 의 모든 내부 동작 (put, get, remove, resize, 트리 변환) 을 처음부터 구현 가능.

비유 — 같은 우편함을 쓰는 가족

아파트 우편함:
  101호 가족이 같은 우편함을 사용

  우편함[5]: 김씨 → 이씨 → 박씨 → null

편지 받기 (get):
  우편함[5] 에서 가족원 이름표 확인
  "김씨" 편지면 김씨에게
  "이씨" 편지면 다음으로 → 이씨에게

새 편지 (put):
  마지막에 추가 → null 자리에 새 노드

이사 (remove):
  중간 가족원 제거 → 양쪽 노드 직접 연결

→ 체이닝의 핵심: 한 버킷 = 여러 노드의 사슬.

🧭 9개 섹션 로드맵

1. 체이닝의 정의와 역사
2. HashMap 의 Node 자료구조
3. put 메서드의 11단계 동작
4. get 메서드의 7단계 동작
5. remove 메서드와 리스트 갱신
6. resize 의 재해싱과 비트 트릭
7. Java 8+ 트리 변환 메커니즘
8. 직접 구현하는 SimpleHashMap
9. 면접 + 자기 점검

1️⃣ 체이닝의 정의와 역사

1.1 체이닝의 정의

체이닝 (Chaining, Separate Chaining):

  같은 해시값을 갖는 키들을 같은 버킷에 보관하되,
  버킷 내에서 보조 자료구조 (연결 리스트, 트리) 로 연결하는 방법.

  영어 별칭: "Closed Addressing" 또는 "Open Hashing"
  (혼란스러운 용어 — 오픈 어드레싱과 반대)

1.2 역사적 배경

1953년:
  Hans Peter Luhn (IBM) 의 원래 해시 테이블 제안
  → 체이닝이 첫 번째 충돌 해결법

1960년대:
  체이닝 vs 오픈 어드레싱 비교 연구
  - Knuth 의 "The Art of Computer Programming" Volume 3
  - 두 방법의 트레이드오프 분석

1990년대:
  자바 1.0 (1996)
  - Hashtable 이 체이닝 사용
  - 연결 리스트 기반

1998년:
  자바 1.2 - HashMap 도입
  - 체이닝 + 연결 리스트
  - Java 7 까지 동일

2014년:
  자바 8 - 트리 변환 추가
  - 버킷 노드 ≥ 8 → Red-Black Tree
  - O(n²) → O(n log n) 보장
  - HashDoS 방어

1.3 체이닝의 시각적 표현

HashMap.table[]: capacity = 16
  
  ┌───┬───────────────────────────────────────┐
  │ 0 │ → null                                  │
  │ 1 │ → Node("BL-001", s1)                    │
  │ 2 │ → Node("BL-007", s7) → Node("BL-023", s23) → null
  │ 3 │ → Node("BL-005", s5)                    │
  │ 4 │ → null                                   │
  │ 5 │ → Node("BL-002", s2) → Node("BL-018", s18) → Node("BL-099", s99) → null
  │ 6 │ → null                                   │
  │ 7 │ → Node("BL-100", s100)                   │
  │ ...                                          │
  │ 15│ → Node("BL-015", s15)                   │
  └───┴───────────────────────────────────────┘
  
구조:
  - table[i] 는 첫 노드 또는 null
  - 충돌 시 단일 연결 리스트로 연결
  - 새 노드는 끝에 추가
  - Java 8+ 부터 buckets[i] 가 TreeNode 일 수도

1.4 체이닝의 동작 원리

삽입 (put):
  1. hash = key.hashCode() ^ (hashCode >>> 16)
  2. index = hash & (n - 1)
  3. table[index] 위치 확인
     - null 이면: 새 노드 생성, 저장
     - 노드 있으면: 리스트 순회하며 같은 키 검사
       - 같은 키: value 덮어쓰기
       - 다른 키: 리스트 끝에 추가

검색 (get):
  1. hash, index 계산
  2. table[index] 부터 시작
  3. 리스트 순회하며 equals 비교
  4. 매칭하면 value 반환, 끝까지 없으면 null

삭제 (remove):
  1. hash, index 계산
  2. 리스트 순회하며 매칭 노드 찾기
  3. 이전 노드의 next 를 다음 노드로 연결
  4. 매칭 노드 GC 대상

1.5 체이닝의 5가지 강점

1. 단순함
   - 연결 리스트 하나만 다루면 됨
   - 코드 간결

2. LoadFactor 유연성
   - LoadFactor > 1.0 가능 (성능 저하 점진적)
   - 메모리 절약 가능

3. 충돌 격리
   - 한 버킷의 충돌이 다른 버킷에 영향 X
   - 클러스터링 (Open Addressing 의 문제) 없음

4. 삭제 단순
   - 노드만 제거하면 됨
   - tombstone 불필요

5. 트리 변환 가능
   - Java 8+ 의 O(log n) 보장
   - 한 버킷에 트리 가능

1.6 체이닝의 단점

1. 메모리 오버헤드
   - 각 노드마다 next 포인터 (8 bytes on 64-bit)
   - Object Header (16 bytes)
   - 키, 값 외에 추가 메모리

2. 캐시 효율 낮음
   - 노드들이 메모리에 분산
   - 연결 리스트 순회 시 캐시 미스

3. 포인터 추적 비용
   - CPU 가 분기 예측 어려움
   - 작은 데이터엔 오픈 어드레싱이 빠를 수도

1.7 체이닝 vs 오픈 어드레싱 메모리 비교

n = 1000 개 키, capacity = 1365 (LoadFactor 0.73):

체이닝 (HashMap):
  table[]: 1365 × 4 bytes (참조) = ~5.5 KB
  Node × 1000: ~32 bytes × 1000 = 32 KB
  총: 약 38 KB

오픈 어드레싱:
  table[]: 1365 × 16 bytes (Entry 직접 저장) = ~22 KB
  추가 메모리 없음
  총: 약 22 KB

→ 오픈 어드레싱이 약 40% 적은 메모리
→ 그러나 자바는 일관성/유연성 위해 체이닝 선택

1.8 자기 점검 답변

체이닝을 채택한 자료구조의 5가지 강점은?

답:
1. 단순함 — 연결 리스트 하나의 구조
2. LoadFactor 유연성 — > 1.0 도 가능
3. 충돌 격리 — 클러스터링 없음
4. 삭제 단순 — 노드 제거 후 연결만 갱신
5. 트리 변환 가능 — Java 8+ 의 O(log n) 보장

→ 자바의 HashMap, HashSet, LinkedHashMap, ConcurrentHashMap 모두 채택.

2️⃣ HashMap 의 Node 자료구조

2.1 Node 클래스의 정의

// HashMap 내부 (실제 코드)
static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;       // 키의 해시값 (캐싱)
    final K key;           // 키 (final, 변경 불가)
    V value;               // 값
    Node<K, V> next;       // 다음 노드 (체이닝)
    
    Node(int hash, K key, V value, Node<K, V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
    
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
    
    public final boolean equals(Object o) {
        if (o == this) return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

2.2 4개 필드의 의미

1. hash (int, final)
   - key.hashCode() 의 결과 + 비트 시프트 처리
   - 캐싱 → 재계산 안 함
   - 재해싱 시 인덱스 계산에 직접 활용

2. key (K, final)
   - final → 변경 불가
   - 키 가변하면 HashMap 깨짐 → final 로 보장

3. value (V)
   - final 아님 → put 으로 덮어쓰기 가능
   - setValue() 로 변경 가능

4. next (Node<K,V>)
   - 같은 버킷의 다음 노드
   - null 이면 마지막 노드
   - 체이닝의 핵심

2.3 메모리 레이아웃

Node 객체 (64-bit JVM):
  ┌──────────────────────────┐
  │ Object Header (16 bytes)  │
  │   - Mark Word              │
  │   - Class Pointer          │
  ├──────────────────────────┤
  │ hash (int, 4 bytes)       │
  ├──────────────────────────┤
  │ key reference (8 bytes)   │
  ├──────────────────────────┤
  │ value reference (8 bytes) │
  ├──────────────────────────┤
  │ next reference (8 bytes)  │
  ├──────────────────────────┤
  │ Padding (~4 bytes)        │
  └──────────────────────────┘
  
  총: 약 48 bytes

비교:

키와 값 자체는 별도 객체 (Heap)
Node 는 참조만 보유
실제 메모리 = Node + key 객체 + value 객체

2.4 hash 필드 캐싱의 효과

hash 캐싱 안 했다면:
  매 작업마다 key.hashCode() 호출 필요
  
  - put: 1 회
  - get: 1 회  
  - resize: n 회 (모든 노드)
  - 트리 변환: n 회
  - 트리 → 리스트 역변환: n 회

hash 캐싱 효과:
  resize 시 거대 절약
  - 1만 노드 → 1만 회 호출 회피
  - String.hashCode() 가 50ns 라면 → 0.5ms 절약

→ hash 캐싱은 성능 핵심.

2.5 ConcurrentHashMap 의 Node

// ConcurrentHashMap 내부
static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    volatile V val;          // volatile! (멀티스레드 가시성)
    volatile Node<K, V> next; // volatile!
    
    // ...
}

차이:

value, next 가 volatile
멀티스레드 환경에서 변경 즉시 다른 스레드에 보임
CAS (Compare-And-Swap) 와 함께 lock-free 동작

2.6 TreeNode (Java 8+ 트리 변환용)

// HashMap 내부
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;              // Red-Black 색상
    
    // ... 메서드들
}

특징:

일반 Node 보다 더 많은 포인터 (parent, left, right, prev, red)
약 56 bytes (메모리 더 사용)
노드 수가 적을 때는 Linked List 가 효율적
노드 수가 많을 때 트리로 변환

2.7 자기 점검 답변

HashMap Node 의 4개 필드와 그 역할은?

답:
1. hash (int, final) — 해시값 캐싱, 재해싱 시 활용
2. key (K, final) — 키, 변경 불가 보장
3. value (V) — 값, 덮어쓰기 가능
4. next (Node) — 다음 노드 참조, 체이닝의 핵심

추가:

ConcurrentHashMap: value, next 가 volatile
TreeNode: parent, left, right, prev, red 추가

3️⃣ put 메서드의 11단계 동작

3.1 put 메서드의 실제 코드 (간략화)

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K, V>[] tab; Node<K, V> p; int n, i;
    
    // 1. 테이블 초기화 (필요시)
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // 2. 버킷 인덱스 계산
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 3. 빈 버킷 → 새 노드 직접 저장
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K, V> e; K k;
        
        // 4. 첫 노드와 키 비교
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;  // 같은 키 발견 → 나중에 덮어쓰기
        
        // 5. TreeNode 면 트리 put
        else if (p instanceof TreeNode)
            e = ((TreeNode<K, V>)p).putTreeVal(this, tab, hash, key, value);
        
        // 6. 연결 리스트 순회
        else {
            for (int binCount = 0; ; ++binCount) {
                // 6-1. 다음 노드가 null → 리스트 끝
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 6-2. 트리 변환 조건 (TREEIFY_THRESHOLD = 8)
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                // 6-3. 중간에 같은 키 발견
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // 7. 기존 키 발견 시 value 덮어쓰기
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);  // LinkedHashMap 용 hook
            return oldValue;
        }
    }
    
    // 8. modCount 증가 (CME 검출용)
    ++modCount;
    
    // 9. size 증가 + 임계값 검사
    if (++size > threshold)
        resize();  // 2배 확장
    
    afterNodeInsertion(evict);  // LinkedHashMap 용 hook
    return null;
}

3.2 put 의 11단계 분해

Step 1 — 테이블 초기화
  최초 put 시 table 이 null
  → resize() 로 capacity 16 생성

Step 2 — hash 계산
  hash(key) = key.hashCode() ^ (key.hashCode() >>> 16)

Step 3 — 인덱스 계산
  i = (n - 1) & hash

Step 4 — 버킷 확인
  Case A: 비어있음 → 직접 저장 (충돌 없음)
  Case B: 노드 있음 → 다음 단계

Step 5 — 첫 노드와 비교
  hash 같고 key.equals 이면 → 같은 키 발견
  → value 덮어쓰기 준비

Step 6 — 트리 노드 처리
  첫 노드가 TreeNode 이면
  → 트리 put 로직 호출

Step 7 — 연결 리스트 순회
  모든 노드를 순회하며:
  - 같은 키 발견 → 덮어쓰기
  - 끝까지 못 찾음 → 새 노드 끝에 추가

Step 8 — 트리 변환 검사
  binCount ≥ 8 → treeifyBin() 호출
  - capacity < 64 면 resize 우선
  - capacity ≥ 64 면 진짜 트리 변환

Step 9 — value 덮어쓰기
  기존 키 발견 시 oldValue 반환

Step 10 — modCount 증가
  ConcurrentModificationException 검출용

Step 11 — size 증가 + resize 검사
  size > threshold (capacity × LoadFactor)
  → 2배 확장

3.3 충돌 시나리오 시각화

초기 상태 (capacity = 16):
  table[5]: null

put("A", 1) — h("A") & 15 = 5
  table[5]: Node("A", 1) → null

put("B", 2) — h("B") & 15 = 7 (다른 버킷)
  table[5]: Node("A", 1) → null
  table[7]: Node("B", 2) → null

put("C", 3) — h("C") & 15 = 5 (인덱스 충돌!)
  table[5]: Node("A", 1) → Node("C", 3) → null
  
put("A", 99) — h("A") & 15 = 5, 같은 키
  table[5]: Node("A", 99) → Node("C", 3) → null
  (덮어쓰기, oldValue = 1 반환)

put("D", 4) — h("D") & 15 = 5 (또 충돌)
  table[5]: Node("A", 99) → Node("C", 3) → Node("D", 4) → null

... (계속 충돌하면 리스트 길어짐)

put 으로 8개 노드 도달 (binCount = 7):
  treeifyBin() 호출
  - capacity 16 < 64 → resize 우선 (트리 변환 대신)
  
put 으로 다시 8개 (capacity 64 이상에서):
  table[5]: TreeNode (Red-Black Tree)

3.4 put 동작 추적 코드

public class PutTrace {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        
        // 의도적 충돌 키 생성
        String[] keys = {"Aa", "BB", "AaAa", "AaBB", "BBAa", "BBBB"};
        
        for (String k : keys) {
            map.put(k, k.length());
            System.out.println(k + " hashCode: " + k.hashCode() + 
                              ", index: " + ((k.hashCode() ^ (k.hashCode() >>> 16)) & 15));
        }
        
        // 출력:
        // Aa hashCode: 2112, index: 0
        // BB hashCode: 2112, index: 0  ← 같은 버킷!
        // AaAa hashCode: 2031744, index: 0
        // AaBB hashCode: 2031744, index: 0
        // BBAa hashCode: 2031744, index: 0
        // BBBB hashCode: 2031744, index: 0
        // → 모두 같은 버킷
    }
}

3.5 onlyIfAbsent 파라미터

// 일반 put: onlyIfAbsent = false
map.put("A", 1);   // 덮어쓰기 가능

// putIfAbsent: onlyIfAbsent = true
map.putIfAbsent("A", 1);   // 이미 있으면 변경 안 함

// 내부 putVal 의 분기:
if (!onlyIfAbsent || oldValue == null)
    e.value = value;

이 분기로 두 메서드를 같은 코드에서 지원.

3.6 afterNodeAccess / afterNodeInsertion 훅

// HashMap 의 빈 메서드
void afterNodeAccess(Node<K, V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K, V> p) { }

LinkedHashMap 이 오버라이드:

// LinkedHashMap
void afterNodeAccess(Node<K, V> e) {
    LinkedHashMap.Entry<K, V> last;
    if (accessOrder && (last = tail) != e) {
        // 노드를 이중 연결 리스트의 끝으로 이동 (LRU)
        // ...
    }
}

→ HashMap 이 LinkedHashMap 의 추가 동작을 위한 hook 제공.

3.7 자기 점검 답변

put 메서드가 같은 키를 발견했을 때의 동작은?

답:
1. hash 같음 검사 (빠른 필터)
2. key == existingKey || key.equals(existingKey) 검사
3. 같으면 → value 덮어쓰기
4. size 증가 안 함 (기존 항목 갱신)
5. oldValue 반환 (put 의 반환값)
6. resize 검사 안 함

→ "put 은 추가 또는 덮어쓰기" 의 동작.

4️⃣ get 메서드의 7단계 동작

4.1 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;
    
    // 1. table 확인
    if ((tab = table) != null && (n = tab.length) > 0 &&
        // 2. 버킷 첫 노드 확인
        (first = tab[(n - 1) & hash]) != null) {
        
        // 3. 첫 노드 매칭 검사
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;  // 가장 흔한 경우 - 빠른 반환
        
        if ((e = first.next) != null) {
            // 4. TreeNode 분기
            if (first instanceof TreeNode)
                return ((TreeNode<K, V>)first).getTreeNode(hash, key);
            
            // 5. 연결 리스트 순회
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

4.2 get 의 7단계

Step 1 — hash 계산
  hash(key) = key.hashCode() ^ (key.hashCode() >>> 16)

Step 2 — table 확인
  table 이 null 이거나 길이 0 → null 반환

Step 3 — 버킷 인덱스
  index = (n - 1) & hash

Step 4 — 첫 노드 검사
  Case A: 첫 노드 매칭 (90% 케이스) → 반환
  Case B: 다음 단계

Step 5 — TreeNode 분기
  첫 노드가 TreeNode → getTreeNode() 호출 → O(log n)

Step 6 — 연결 리스트 순회
  do-while 로 next 따라가며 hash + equals 비교

Step 7 — 못 찾음
  null 반환

4.3 빠른 종료 최적화

// 첫 노드 검사:
if (first.hash == hash &&
    ((k = first.key) == key || (key != null && key.equals(k))))
    return first;

핵심:

first.hash == hash 먼저 검사 (int 비교, 매우 빠름)
k == key 참조 비교 (같은 객체)
위 둘 중 하나도 만족 못 하면 → equals 호출 (가장 비쌈)

순서가 중요:
1. hash 비교 (빠름) — 다르면 즉시 종료
2. == 비교 (빠름) — 같은 객체면 즉시 매칭
3. equals 호출 (느림) — 마지막 수단

→ String.equals 가 길이 검사 후 char 비교라 비용 ↑.

4.4 충돌 시 get 추적

table[5]: Node("Aa", 1) → Node("BB", 2) → Node("AaAa", 3) → null

get("BB") 호출 시:

Step 1: hash("BB") = ... (Aa, BB 모두 2112)
Step 2: index = 0 (간략화)
Step 3: 첫 노드 Node("Aa", 1) 가져옴
Step 4: hash 같음 (둘 다 2112), key "Aa" != "BB"
        equals("Aa", "BB") = false
        → 첫 노드 매칭 실패
Step 5: TreeNode 아님
Step 6: next 따라감 → Node("BB", 2)
        hash 같음, equals("BB", "BB") = true
        → 매칭! 반환 Node("BB", 2)
Step 7: e.value = 2 반환

→ 충돌 노드 1개씩 검사. 노드가 많을수록 시간 ↑.

4.5 null 키와 null 값 처리

// null 키
map.put(null, "value");  
// hash(null) = 0
// 버킷 [0] 에 저장

map.get(null);  
// hash(null) = 0
// 버킷 [0] 첫 노드부터 검색
// key == null 인 노드 찾기

// HashMap 의 hash 메서드
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

특징:

null 키는 항상 hash = 0
버킷 [0] 에 저장 (보통)
비교 시 key == null 분기

4.6 getOrDefault, containsKey 와의 관계

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

// containsKey
public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

→ 모두 getNode() 재사용.
→ "찾으면 노드, 못 찾으면 null" 의 단일 동작.

4.7 자기 점검 답변

get 메서드의 빠른 종료 최적화 3단계는?

답:
1. hash 비교 (int, 매우 빠름) — 다르면 즉시 다음 노드
2. == 비교 (참조, 빠름) — 같은 객체면 즉시 매칭
3. equals 호출 (느림) — 마지막 수단

순서:

first.hash == hash 
&& (k == key || key.equals(k))

&& 는 short-circuit:

첫 조건 false → 두 번째 검사 안 함
첫 조건 true → 두 번째 검사
두 번째도 || short-circuit (== 먼저)

→ CPU 분기 예측 + 캐시 효율 모두 고려한 코드.

5️⃣ remove 메서드와 리스트 갱신

5.1 remove 메서드 코드

public V remove(Object key) {
    Node<K, V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node<K, V> removeNode(int hash, Object key, Object value,
                             boolean matchValue, boolean movable) {
    Node<K, V>[] tab; Node<K, V> p; int n, index;
    
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        
        Node<K, V> node = null, e; K k; V v;
        
        // 1. 첫 노드 매칭 검사
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        
        else if ((e = p.next) != null) {
            // 2. TreeNode 검색
            if (p instanceof TreeNode)
                node = ((TreeNode<K, V>)p).getTreeNode(hash, key);
            else {
                // 3. 연결 리스트 순회
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;  // 이전 노드 추적
                } while ((e = e.next) != null);
            }
        }
        
        // 4. 노드 발견 시 제거
        if (node != null && (!matchValue || (v = node.value) == value ||
                              (value != null && value.equals(v)))) {
            // 4-1. TreeNode 제거
            if (node instanceof TreeNode)
                ((TreeNode<K, V>)node).removeTreeNode(this, tab, movable);
            
            // 4-2. 버킷 첫 노드 제거
            else if (node == p)
                tab[index] = node.next;
            
            // 4-3. 리스트 중간 제거
            else
                p.next = node.next;
            
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

5.2 연결 리스트의 제거 시각화

초기 상태:
  table[5]: Node("A") → Node("B") → Node("C") → null
            ↑           ↑
            p           e

remove("B"):
  1. 순회: p = Node("A"), e = Node("B") 매칭
  2. p.next = e.next
     → Node("A").next = Node("C")
  3. 결과:
     table[5]: Node("A") → Node("C") → null
     (Node("B") 는 누구도 안 가리킴 → GC)

5.3 첫 노드 제거의 특별 처리

remove("A") 의 경우:
  table[5]: Node("A") → Node("B") → ...
            ↑
            node == p (첫 노드)
  
  처리:
    tab[index] = node.next
    → tab[5] = Node("B")
  
  결과:
    table[5]: Node("B") → ...

→ 첫 노드 제거 시 tab[index] 직접 갱신.
→ 그 외 노드는 p.next = node.next.

5.4 끝 노드 제거

remove("C") 의 경우:
  table[5]: Node("A") → Node("B") → Node("C") → null
                                     ↑
                                     node, e
                       ↑
                       p
  
  처리:
    p.next = node.next
    → Node("B").next = null
  
  결과:
    table[5]: Node("A") → Node("B") → null

5.5 matchValue 옵션

public boolean remove(Object key, Object value) {
    return removeNode(hash(key), key, value, true, true) != null;
}

matchValue = true:

키 매칭 + 값도 매칭해야 제거
키만 같고 값 다르면 제거 안 함
멀티스레드 시나리오에 안전

5.6 size 감소 vs modCount 증가

++modCount;   // 변경 카운트 (CME 검출)
--size;       // 요소 수 감소

modCount:

변경 발생 시마다 증가
Iterator 가 사용 (ConcurrentModificationException)

size:

실제 요소 수
size() 메서드의 반환값

5.7 remove 의 시간 복잡도

평균 케이스:
  - 첫 노드 매칭: O(1)
  - 평균 노드 1개 / 버킷 (LoadFactor 0.75)
  - 평균 O(1)

최악 케이스:
  - Java 7: 연결 리스트 끝 → O(n)
  - Java 8+: 트리 → O(log n)

비교 vs put:
  - put 도 같은 패턴
  - 단, put 은 size 증가 + resize 검사
  - remove 는 size 감소

5.8 remove 후 트리 → 리스트 역변환

// TreeNode 의 removeTreeNode 내부
// 트리 크기 < UNTREEIFY_THRESHOLD (6) 이면 리스트로 역변환

if (root == null || root.right == null ||
    (rl = root.left) == null || rl.left == null) {
    tab[index] = first.untreeify(map);   // 리스트로 변환
    return;
}

→ 트리에서 노드 제거 시 크기 < 6 이면 리스트로 역변환.
→ 메모리 절약.

5.9 자기 점검 답변

연결 리스트의 중간 노드 제거 시 갱신 동작은?

답:

이전 노드 p 와 제거 대상 e 추적
p.next = e.next 로 양쪽 연결
제거 대상은 누구도 안 가리킴 → GC 대상

특수 케이스:

첫 노드 제거: tab[index] = node.next (배열 슬롯 직접 갱신)
끝 노드 제거: p.next = null
중간 제거: p.next = node.next

6️⃣ resize 의 재해싱과 비트 트릭

6.1 resize 메서드 코드 (간략화)

final Node<K, V>[] resize() {
    Node<K, V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 최대 capacity 도달
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1;  // 2배
    }
    else if (oldThr > 0) // 초기 capacity 지정 시
        newCap = oldThr;
    else {
        // 처음 초기화
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K, V>[] newTab = (Node<K, V>[])new Node[newCap];
    table = newTab;
    
    // 모든 노드 재배치
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K, V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;  // GC 도움
                
                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 {
                    // 연결 리스트 분할
                    Node<K, V> loHead = null, loTail = null;
                    Node<K, V> hiHead = null, hiTail = null;
                    Node<K, V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            // 같은 인덱스 유지
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            // 새 인덱스 (oldCap 만큼 떨어진 곳)
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

6.2 비트 트릭 — (hash & oldCap)

핵심 트릭:
  capacity 가 2배 늘면, 노드의 새 위치는 두 가지 중 하나
  
  Case A: 같은 인덱스 (j)
  Case B: j + oldCap

이를 결정하는 조건:
  (hash & oldCap) == 0 ? Case A : Case B

수학적 증명:

oldCap = 16 = 0b10000
newCap = 32 = 0b100000

oldCap - 1 = 0b01111 (4 비트)
newCap - 1 = 0b11111 (5 비트)

이전 인덱스: hash & 0b01111 (하위 4비트)
새 인덱스: hash & 0b11111 (하위 5비트)

차이:
  새 인덱스의 4번째 비트 = hash 의 4번째 비트
  
  - hash 의 4번째 비트 = 0 → 새 인덱스 = 이전 인덱스
  - hash 의 4번째 비트 = 1 → 새 인덱스 = 이전 인덱스 + 16

비트 검사:
  hash & oldCap == hash & 0b10000 == hash 의 4번째 비트만 추출

6.3 시각화

hash = 0b...11010110 (예시)
oldCap = 16 = 0b10000

hash & (oldCap - 1) = hash & 0b01111 = 0b0110 = 6
hash & (oldCap)     = hash & 0b10000 = 0b00000 = 0
hash & (newCap - 1) = hash & 0b11111 = 0b00110 = 6

→ 새 인덱스 = 6 (이전과 같음)


hash = 0b...11110110
oldCap = 16

hash & (oldCap - 1) = hash & 0b01111 = 0b0110 = 6
hash & (oldCap)     = hash & 0b10000 = 0b10000 = 16
hash & (newCap - 1) = hash & 0b11111 = 0b10110 = 22

→ 새 인덱스 = 22 = 6 + 16 = 이전 + oldCap

6.4 리스트 분할 알고리즘

// 연결 리스트를 두 리스트로 분할
Node<K, V> loHead = null, loTail = null;  // 같은 인덱스 유지
Node<K, V> hiHead = null, hiTail = null;  // 새 인덱스 (j + oldCap)
Node<K, V> next;

do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        // low 그룹
        if (loTail == null)
            loHead = e;       // 첫 노드
        else
            loTail.next = e;  // 추가
        loTail = e;
    }
    else {
        // high 그룹
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);

→ 단일 순회로 두 리스트 분리.
→ Java 7 까지는 매 노드마다 새 hashCode 호출 + 새 인덱스 계산 → 비효율.

6.5 시각화

Before resize (oldCap = 16):
  table[5]: Node1 → Node2 → Node3 → Node4 → null
  
  Node1.hash & 16 = 0  (low)
  Node2.hash & 16 = 16 (high)
  Node3.hash & 16 = 0  (low)
  Node4.hash & 16 = 16 (high)

분할:
  low:  Node1 → Node3 → null
  high: Node2 → Node4 → null

After resize (newCap = 32):
  table[5]:  Node1 → Node3 → null   (이전 인덱스)
  table[21]: Node2 → Node4 → null   (이전 + 16)

→ 한 버킷의 노드들이 두 버킷으로 균등 분배.

6.6 resize 의 비용

시간 복잡도:
  - 모든 노드 순회: O(n)
  - 각 노드: hash 캐싱 사용 (재계산 안 함)
  - 트리도 같은 원리로 분할

공간 복잡도:
  - 새 배열 할당: O(newCap)
  - 일시적으로 옛 + 새 배열 모두 존재
  - GC 후 옛 배열 회수

전체 비용:
  - n 개 노드: O(n) 시간
  - 메모리 일시 ~ 2배

→ resize 는 비용 큰 작업. 초기 capacity 지정으로 회피 가능.

6.7 resize 발생 조건

조건 1: 최초 put (table = null)
  → 기본 capacity 16

조건 2: size > threshold
  - threshold = capacity × LoadFactor
  - 기본: 16 × 0.75 = 12
  - 12 초과 → resize (32 로)

조건 3: 트리 변환 시 capacity < 64
  - 트리 변환 대신 resize 우선
  - 자세한 건 다음 섹션

6.8 capacity 증가 시퀀스

초기: 16
1차 resize: 32
2차: 64
3차: 128
4차: 256
5차: 512
...
n차: 16 × 2^n

최대: 2^30 = 1,073,741,824

→ 항상 2의 거듭제곱.
→ (n-1) & hash 트릭 유지.

6.9 Java 7 의 단점 (Java 8 개선)

Java 7 resize:
  - 모든 노드 재해싱 (key.hashCode() 다시 호출)
  - 새 인덱스 매번 계산
  - 멀티스레드 시 무한 루프 가능 (concurrent modification)

Java 8 resize:
  - hash 캐싱 활용 (Node.hash 필드)
  - (hash & oldCap) 비트 트릭
  - 멀티스레드 안전성 약간 개선 (여전히 thread-unsafe)

→ Java 8 의 큰 성능 개선.

6.10 자기 점검 답변

Java 8 resize 의 (hash & oldCap) == 0 비트 트릭의 의미는?

답:

capacity 가 2배 늘면 노드의 새 위치는 두 가지:
- 그대로 (이전 인덱스)
- 이전 + oldCap
이를 결정하는 건 hash 의 특정 비트
hash & oldCap 으로 그 비트만 추출
0 이면 같은 인덱스, 비0 이면 oldCap 만큼 이동

이점:

hash 재계산 없음
단순 비트 연산
O(n) 으로 모든 노드 재배치

7️⃣ Java 8+ 트리 변환 메커니즘

7.1 트리 변환의 동기

Java 7 까지의 문제:
  - 모든 충돌이 연결 리스트
  - 최악의 경우 O(n) 검색
  - HashDoS 공격 취약
  - 100만 노드 같은 버킷 → 검색 100만 비교

Java 8 의 해결:
  - 버킷 노드 ≥ 8 → Red-Black Tree
  - 최악 O(log n) 보장
  - HashDoS 효과 100배 감소

7.2 트리 변환의 6가지 조건

1. binCount >= TREEIFY_THRESHOLD - 1 (= 7)
   - 한 버킷의 노드 수가 8 이상
   - 8번째 노드 추가 시 트리 변환 시도

2. capacity >= MIN_TREEIFY_CAPACITY (= 64)
   - 작은 HashMap (capacity < 64) 은 트리 변환 대신 resize 우선
   - 트리 자체보다 분산이 더 효과적

3. 트리 변환은 한 버킷씩
   - 전체 HashMap 이 아닌 충돌 빈번한 버킷만
   - 나머지 버킷은 연결 리스트 유지

4. 트리 → 리스트 역변환 (UNTREEIFY_THRESHOLD = 6)
   - 트리 크기 < 6 으로 줄면 다시 연결 리스트
   - 메모리 절약

5. resize 시 트리 분할
   - 트리도 두 버킷으로 분할
   - 분할 후 크기 < 6 이면 리스트로 역변환

6. 비교 가능한 키만 트리 사용
   - Comparable 이거나 같은 클래스
   - 비교 안 되면 일반 정렬 (해시값 + 임의 순서)

7.3 treeifyBin 메서드

// HashMap 내부
final void treeifyBin(Node<K, V>[] tab, int hash) {
    int n, index; Node<K, V> e;
    
    // capacity 64 미만이면 resize 우선
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K, V> hd = null, tl = null;
        do {
            // Node → TreeNode 변환 (모든 노드)
            TreeNode<K, V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        
        // 이중 연결 리스트 (prev/next) 완성 후
        if ((tab[index] = hd) != null)
            // 진짜 트리로 변환
            hd.treeify(tab);
    }
}

7.4 treeify 메서드 (실제 트리 구축)

// TreeNode 내부
final void treeify(Node<K, V>[] tab) {
    TreeNode<K, V> root = null;
    for (TreeNode<K, V> x = this, next; x != null; x = next) {
        next = (TreeNode<K, V>)x.next;
        x.left = x.right = null;
        
        if (root == null) {
            // 첫 노드는 루트, BLACK
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            
            // 루트부터 내려가며 위치 찾기
            for (TreeNode<K, V> p = root;;) {
                int dir, ph;
                K pk;
                
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);
                
                TreeNode<K, V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    
                    // 균형 조정 (Red-Black Tree)
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    
    // root 가 tab[index] 의 첫 노드가 되도록
    moveRootToFront(tab, root);
}

7.5 트리에서의 검색 (getTreeNode)

// TreeNode.getTreeNode
final TreeNode<K, V> getTreeNode(int h, Object k) {
    return ((parent != null) ? root() : this).find(h, k, null);
}

final TreeNode<K, V> find(int h, Object k, Class<?> kc) {
    TreeNode<K, V> p = this;
    do {
        int ph, dir; K pk;
        TreeNode<K, V> pl = p.left, pr = p.right, q;
        
        // hash 비교로 방향 결정
        if ((ph = p.hash) > h)
            p = pl;
        else if (ph < h)
            p = pr;
        // 같은 hash + 같은 key
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        // hash 같지만 key 다름
        else if (pl == null)
            p = pr;
        else if (pr == null)
            p = pl;
        // Comparable 비교
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr;
        // 양쪽 모두 검색 (재귀)
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        else
            p = pl;
    } while (p != null);
    
    return null;
}

핵심:

hash 비교 → 트리 탐색 (O(log n))
hash 같으면 → Comparable 또는 equals
양쪽 모두 검색 가능 (최악 O(n) 회피)

7.6 트리 노드 메모리 비교

Node (Java 7 까지 + Java 8+ 일반):
  ┌──────────────────────────┐
  │ Header (16 bytes)         │
  ├──────────────────────────┤
  │ hash (4 bytes)            │
  ├──────────────────────────┤
  │ key (8 bytes)             │
  ├──────────────────────────┤
  │ value (8 bytes)           │
  ├──────────────────────────┤
  │ next (8 bytes)            │
  │ Padding (4 bytes)         │
  └──────────────────────────┘
  총: 48 bytes

TreeNode (Java 8+ 트리):
  ┌──────────────────────────┐
  │ Header (16 bytes)         │
  ├──────────────────────────┤
  │ hash (4 bytes)            │
  ├──────────────────────────┤
  │ key (8 bytes)             │
  ├──────────────────────────┤
  │ value (8 bytes)           │
  ├──────────────────────────┤
  │ next (8 bytes)            │
  ├──────────────────────────┤
  │ before (8 bytes) — LinkedHashMap 용
  ├──────────────────────────┤
  │ after (8 bytes) — LinkedHashMap 용
  ├──────────────────────────┤
  │ parent (8 bytes)          │
  ├──────────────────────────┤
  │ left (8 bytes)            │
  ├──────────────────────────┤
  │ right (8 bytes)           │
  ├──────────────────────────┤
  │ prev (8 bytes)            │
  ├──────────────────────────┤
  │ red (1 byte) + Padding    │
  └──────────────────────────┘
  총: 약 88-96 bytes

→ TreeNode 가 약 2배 메모리.
→ 노드 수가 많을 때만 트리 변환 (≥ 8).

7.7 트리 변환의 효과

1000 노드 가정:

Java 7:
  - 모두 연결 리스트
  - 검색 평균 500번 비교 → O(n)
  - 최악 1000번

Java 8+ 트리:
  - log2(1000) ≈ 10번 비교
  - O(log n)
  - 100배 빠름

7.8 트리 → 리스트 역변환

// 트리 크기 줄면 리스트로 역변환
// UNTREEIFY_THRESHOLD = 6

final Node<K, V> untreeify(HashMap<K, V> map) {
    Node<K, V> hd = null, tl = null;
    for (Node<K, V> q = this; q != null; q = q.next) {
        Node<K, V> p = map.replacementNode(q, null);
        if (tl == null)
            hd = p;
        else
            tl.next = p;
        tl = p;
    }
    return hd;
}

→ remove 후 크기 < 6 이면 호출.
→ 메모리 절약.

7.9 자기 점검 답변

트리 변환의 6가지 조건은?

답:
1. 버킷 노드 수 ≥ 8 (TREEIFY_THRESHOLD)
2. capacity ≥ 64 (MIN_TREEIFY_CAPACITY)
3. 버킷별 독립: 모든 버킷이 아닌 충돌 버킷만
4. 역변환 조건: 트리 < 6 노드 → 리스트
5. resize 시 분할: 트리도 두 그룹으로 분할
6. 비교 가능 키: Comparable 또는 같은 클래스 → 순서 결정

→ 변환은 비용 있으므로 신중한 조건.

8️⃣ 직접 구현하는 SimpleHashMap

8.1 구현 목표

구현할 기능:
  1. put(key, value)
  2. get(key)
  3. remove(key)
  4. size()
  5. containsKey(key)
  6. resize (확장)
  
제외 기능:
  - 트리 변환 (복잡)
  - LinkedHashMap hook
  - Iterator
  - 멀티스레드

8.2 Node 클래스

public class SimpleHashMap<K, V> {
    
    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next;
        
        Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        
        @Override
        public String toString() {
            return key + "=" + value;
        }
    }
    
    // 필드
    private Node<K, V>[] table;
    private int size;
    private int threshold;
    private static final float LOAD_FACTOR = 0.75f;
    private static final int DEFAULT_CAPACITY = 16;
    
    // 생성자
    @SuppressWarnings("unchecked")
    public SimpleHashMap() {
        this.table = (Node<K, V>[]) new Node[DEFAULT_CAPACITY];
        this.threshold = (int) (DEFAULT_CAPACITY * LOAD_FACTOR);
    }
}

8.3 hash 메서드

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

private int indexFor(int hash) {
    return hash & (table.length - 1);
}

8.4 put 메서드

public V put(K key, V value) {
    int hash = hash(key);
    int idx = indexFor(hash);
    
    // 빈 버킷이면 직접 저장
    if (table[idx] == null) {
        table[idx] = new Node<>(hash, key, value, null);
        if (++size > threshold) resize();
        return null;
    }
    
    // 첫 노드부터 순회
    Node<K, V> current = table[idx];
    Node<K, V> prev = null;
    
    while (current != null) {
        // 같은 키 발견 시 덮어쓰기
        if (current.hash == hash &&
            (current.key == key || 
             (key != null && key.equals(current.key)))) {
            V oldValue = current.value;
            current.value = value;
            return oldValue;
        }
        prev = current;
        current = current.next;
    }
    
    // 리스트 끝에 새 노드 추가
    prev.next = new Node<>(hash, key, value, null);
    
    if (++size > threshold) resize();
    return null;
}

8.5 get 메서드

public V get(Object key) {
    int hash = hash(key);
    int idx = indexFor(hash);
    
    Node<K, V> current = table[idx];
    while (current != null) {
        if (current.hash == hash &&
            (current.key == key ||
             (key != null && key.equals(current.key)))) {
            return current.value;
        }
        current = current.next;
    }
    return null;
}

public boolean containsKey(Object key) {
    return getNode(key) != null;
}

private Node<K, V> getNode(Object key) {
    int hash = hash(key);
    int idx = indexFor(hash);
    
    Node<K, V> current = table[idx];
    while (current != null) {
        if (current.hash == hash &&
            (current.key == key ||
             (key != null && key.equals(current.key)))) {
            return current;
        }
        current = current.next;
    }
    return null;
}

8.6 remove 메서드

public V remove(Object key) {
    int hash = hash(key);
    int idx = indexFor(hash);
    
    Node<K, V> current = table[idx];
    Node<K, V> prev = null;
    
    while (current != null) {
        if (current.hash == hash &&
            (current.key == key ||
             (key != null && key.equals(current.key)))) {
            // 찾음! 제거
            if (prev == null) {
                // 첫 노드
                table[idx] = current.next;
            } else {
                // 중간 또는 끝
                prev.next = current.next;
            }
            size--;
            return current.value;
        }
        prev = current;
        current = current.next;
    }
    return null;
}

8.7 resize 메서드

@SuppressWarnings("unchecked")
private void resize() {
    Node<K, V>[] oldTable = table;
    int oldCap = oldTable.length;
    int newCap = oldCap * 2;
    
    Node<K, V>[] newTable = (Node<K, V>[]) new Node[newCap];
    
    // 모든 노드 재배치 — Java 8 비트 트릭 활용
    for (int j = 0; j < oldCap; j++) {
        Node<K, V> e = oldTable[j];
        if (e == null) continue;
        
        oldTable[j] = null;
        
        // 단일 노드면 직접 재배치
        if (e.next == null) {
            newTable[e.hash & (newCap - 1)] = e;
            continue;
        }
        
        // 리스트 분할 (low/high)
        Node<K, V> loHead = null, loTail = null;
        Node<K, V> hiHead = null, hiTail = null;
        Node<K, V> next;
        
        do {
            next = e.next;
            if ((e.hash & oldCap) == 0) {
                // low: 같은 인덱스
                if (loTail == null) loHead = e;
                else loTail.next = e;
                loTail = e;
            } else {
                // high: 인덱스 + oldCap
                if (hiTail == null) hiHead = e;
                else hiTail.next = e;
                hiTail = e;
            }
        } while ((e = next) != null);
        
        if (loTail != null) {
            loTail.next = null;
            newTable[j] = loHead;
        }
        if (hiTail != null) {
            hiTail.next = null;
            newTable[j + oldCap] = hiHead;
        }
    }
    
    table = newTable;
    threshold = (int) (newCap * LOAD_FACTOR);
}

public int size() {
    return size;
}

8.8 사용 예시

public class SimpleHashMapTest {
    public static void main(String[] args) {
        SimpleHashMap<String, Integer> map = new SimpleHashMap<>();
        
        // 기본 동작
        map.put("apple", 1);
        map.put("banana", 2);
        map.put("cherry", 3);
        
        System.out.println(map.get("apple"));   // 1
        System.out.println(map.get("banana"));  // 2
        System.out.println(map.size());         // 3
        
        // 덮어쓰기
        Integer old = map.put("apple", 99);
        System.out.println(old);                 // 1
        System.out.println(map.get("apple"));    // 99
        
        // 제거
        Integer removed = map.remove("banana");
        System.out.println(removed);              // 2
        System.out.println(map.size());           // 2
        
        // 충돌 강제
        map.put("Aa", 1);
        map.put("BB", 2);   // Aa 와 같은 hashCode
        System.out.println(map.get("BB"));        // 2
        
        // 대량 데이터 (resize 발생)
        for (int i = 0; i < 100; i++) {
            map.put("key" + i, i);
        }
        System.out.println(map.size());           // 102
        System.out.println(map.get("key50"));     // 50
    }
}

8.9 자바 HashMap 과의 차이

SimpleHashMap (이 구현):
  - 트리 변환 없음 (최악 O(n))
  - Iterator 없음
  - LinkedHashMap hook 없음
  - 멀티스레드 안전성 없음
  - 일부 메서드 누락 (entrySet 등)

자바 HashMap:
  - Java 8+ 트리 변환 (O(log n) 보장)
  - 완전한 Map 인터페이스
  - LinkedHashMap 상속 가능
  - Iterator + Stream 지원
  - 멀티스레드는 ConcurrentHashMap 별도

8.10 더 깊은 학습 — 직접 추가 가능한 기능

1. Iterator 추가
   - keySet(), values(), entrySet()
   - 변경 검출 (modCount)

2. 트리 변환
   - 노드 ≥ 8 시 Red-Black Tree
   - balanceInsertion 등 트리 로직

3. ConcurrentHashMap 만들기
   - segment 또는 노드 락
   - CAS 활용

4. 성능 최적화
   - 비트 시프트
   - hashCode 캐싱
   - 캐시 친화적 노드 배치

5. 통계 측정
   - 충돌 분포
   - 평균 버킷 길이
   - 검색 비교 횟수

8.11 자기 점검 답변

SimpleHashMap 의 resize 가 자바 8 의 비트 트릭을 어떻게 활용하나?

답:

(e.hash & oldCap) == 0 으로 그룹 결정
0 이면 low (같은 인덱스), 비0 이면 high (이전 + oldCap)
단일 순회로 두 리스트 분리
hash 재계산 불필요 (캐싱된 hash 활용)

핵심:

O(n) 시간
O(newCap) 추가 메모리
멀티스레드 X (HashMap 도 같음)

9️⃣ 면접 + 자기 점검

9.1 면접 단골 질문 매핑

Q	핵심 답변
체이닝의 정의?	같은 버킷의 충돌 키들을 연결 리스트/트리로
HashMap Node 구조?	hash, key, value, next (4개 필드)
Node 의 hash 캐싱 이유?	재해싱 시 재계산 회피
put 의 11단계?	초기화 → hash → 인덱스 → 버킷 → 순회 → 추가 → resize
get 의 최적화 순서?	hash == → == → equals (빠른 순)
remove 의 리스트 갱신?	prev.next = node.next
resize 비트 트릭?	hash & oldCap == 0 → 같은 인덱스
트리 변환 조건?	binCount ≥ 8 + capacity ≥ 64
트리 → 리스트?	노드 < 6 시 역변환
TreeNode 메모리?	약 88 bytes (Node 의 ~2배)
HashMap 직접 구현 가능?	본 Unit 의 SimpleHashMap

9.2 자기 점검 체크리스트

Node 자료구조

Node 의 4개 필드를 안다
hash 가 final 인 이유를 안다
key 가 final 인 이유를 안다
TreeNode 의 추가 필드를 안다
메모리 비용을 안다

put / get / remove

put 의 11단계를 설명 가능
get 의 빠른 종료 최적화를 안다
remove 의 리스트 갱신을 안다
첫/중간/끝 노드 제거의 차이를 안다
modCount 의 역할을 안다

resize

resize 의 트리거 조건을 안다
(hash & oldCap) == 0 비트 트릭을 안다
리스트 분할 (low/high) 알고리즘을 안다
Java 7 vs 8 의 차이를 안다
resize 비용 (O(n)) 을 안다

트리 변환

트리 변환 조건 6가지를 안다
capacity < 64 면 resize 우선임을 안다
treeify 알고리즘을 안다
트리 검색 (O(log n)) 을 안다
UNTREEIFY_THRESHOLD 를 안다

직접 구현

SimpleHashMap 의 put 을 처음부터 작성 가능
get/remove 도 작성 가능
resize 비트 트릭으로 작성 가능
충돌 시나리오 테스트 가능
트리 변환은 복잡 (개념만)

9.3 추가 심화 질문

Q1: put 호출 시 발생하는 GC 객체는?

답:

새 Node 객체 1개 (충돌이든 아니든)
만약 resize 트리거 시:
- 새 Node 배열 (size × 8 bytes 참조)
- 옛 배열은 GC 대상
트리 변환 시:
- 모든 Node → TreeNode 변환
- 옛 Node 들 GC 대상

→ HashMap 사용은 GC 부담 있음.

Q2: get 이 null 반환 시 두 가지 의미?

답:

키가 없음
또는 키가 있지만 값이 null

구분 방법:

if (map.containsKey(key)) {
    // 키 존재 + 값 null
} else {
    // 키 없음
}

// 또는
V v = map.getOrDefault(key, MISSING);
if (v == MISSING) { ... }

ConcurrentHashMap 은 null 값 거부 → 이 모호성 회피.

Q3: 트리 변환 후 다시 리스트로 안 돌아가는 경우?

답:

노드 수가 6 미만으로 줄지 않으면 트리 유지
resize 시 트리도 분할 가능
분할 후 한쪽 < 6 이면 그쪽만 리스트로

Q4: HashMap 의 size() 가 O(1) 인 이유?

답:

size 필드를 별도로 관리
put/remove 시 매번 갱신
size() 호출 = 필드 읽기 O(1)

ConcurrentHashMap 의 size() 는 다름:

O(1) 이지만 정확하지 않음
멀티스레드 변경 중일 수 있음
정확한 카운트 필요시 LongAdder 사용

🎯 핵심 요약 — 3줄 정리

1. 체이닝 = 연결 리스트 또는 트리

같은 버킷의 충돌 키를 보관
Node: hash (캐싱), key (final), value, next
Java 8+: 노드 ≥ 8 → Red-Black Tree

2. 핵심 알고리즘

put: 11단계 (해시 → 인덱스 → 버킷 → 순회 → 추가)
get: 빠른 종료 (hash → == → equals)
resize: (hash & oldCap) 비트 트릭으로 O(n) 재배치

3. 트리 변환

조건: binCount ≥ 8 + capacity ≥ 64
효과: O(n) → O(log n)
HashDoS 방어의 핵심

📚 다음으로...

Unit 3.4 — 충돌 해결법 2: 오픈 어드레싱 (Open Addressing)

이번 Unit 에서 체이닝의 정밀 메커니즘을 봤다면, 다음은 다른 방향의 해결책.

오픈 어드레싱의 정의와 종류
선형 탐사 (Linear Probing)
이차 탐사 (Quadratic Probing)
이중 해싱 (Double Hashing)
Robin Hood Hashing
삭제의 함정 (tombstone)
클러스터링 (Clustering) 문제
Python dict 의 구현
자바 EnumMap, IdentityHashMap 의 오픈 어드레싱

→ 마스터 프롬프트 깊이 Unit — 다양한 알고리즘과 실제 구현.

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 — 해시의 원리 (3/4 진행)

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

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

댓글