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") → null5.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 = 이전 + oldCap6.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%)
Software Developer