분리 연결법
충돌 발생 시 해당 인덱스에 연결 리스트(또는 트리)로 데이터를 연결하여 저장하는 방식입니다.
핵심 아이디어
각 인덱스가 연결 리스트의 헤드를 가리킴
충돌 발생 시 해당 리스트에 노드 추가
동작 과정
put("apple") → hash % N = 3 → index 3에 저장
put("banana") → hash % N = 3 → index 3 리스트에 추가 (충돌)
put("cherry") → hash % N = 5 → index 5에 저장
index 3 → [apple] → [banana]
index 4 → null
index 5 → [cherry]
Java HashMap의 분리 연결법
// Java 8 이전 - LinkedList만 사용
index 3 → [apple] → [banana] → [grape] ... // O(n)
// Java 8 이후 - 8개 이상이면 Red-Black Tree로 전환
index 3 → Tree 구조 // O(log n)
// HashMap 내부 상수
static final int TREEIFY_THRESHOLD = 8; // Tree로 전환 기준
static final int UNTREEIFY_THRESHOLD = 6; // 다시 List로 전환 기준
성능
| 상황 | 시간복잡도 |
|---|---|
| 충돌 없음 | O(1) |
| 충돌 (LinkedList) | O(n) |
| 충돌 (Tree, Java 8+) | O(log n) |
개방 주소법과 비교
| 분리 연결법 | 개방 주소법 | |
|---|---|---|
| 충돌 처리 | 리스트/트리로 연결 | 빈 슬롯 탐색 |
| 메모리 | 추가 사용 | 배열만 사용 |
| 캐시 효율 | 낮음 | 높음 |
| 로드 팩터 | 1 초과 가능 | 1 초과 불가 |
| 삭제 | 간단 | 복잡 (Dummy 필요) |
| 데이터 많을 때 | 유연하게 대응 | 성능 급격히 저하 |
Java의 HashMap이 분리 연결법을 사용하며, 충돌이 많아질 경우 LinkedList → Red-Black Tree로 자동 전환하여 최악의 경우에도 O(log n) 을 보장합니다.