충돌한 항목들을 버킷에 연결 리스트로 매달아 보관하는 방식(separate chaining).
구조
버킷 [0] → null [1] → ["banana"|3] → ["grape"|7] → null ← 충돌한 둘이 함께 매달림 [2] → ["apple"|1] → null [3] → null
조회하면 해당 버킷의 리스트를 순회하며 equals로 진짜 키를 찾는다.
- get("grape")
- 1번 버킷 → "banana"? 아니다 → "grape"? 맞다 → 7 반환
시간복잡도
| 평균 | 최악 | |
|---|---|---|
| 조회·삽입·삭제 | O(1) | O(n) — 전부 한 버킷에 몰릴 때 |
평균이 O(1)인 근거는 부하율이 상수로 유지되기 때문이다. 부하율 0.75면 버킷당 평균 0.75개, 리스트를 한두 번만 보면 된다.
자바 8의 개선 — 트리화
한 버킷의 항목이 8개를 넘고 전체 버킷이 64개 이상이면 연결 리스트를 레드-블랙 트리로 바꾼다.
최악 O(n) → 최악 O(log n)
항목이 6개 이하로 줄면 다시 리스트로 되돌린다(잦은 전환을 막기 위해 임계값이 다르다). 해시 DoS 공격에 대한 방어이기도 하다.
개방 주소법과 비교
| 체이닝 | 개방 주소법 | |
|---|---|---|
| 충돌 처리 | 버킷에 매달기 | 다른 빈 칸으로 |
| 부하율 | 1을 넘어도 동작 | 1을 넘을 수 없음 |
| 삭제 | 간단 (노드 제거) | 까다로움 (묘비 필요) |
| 캐시 효율 | 나쁨 (노드가 흩어짐) | 좋음 (배열 내부) |
| 메모리 | 포인터 오버헤드 | 빈 슬롯 낭비 |
왜 자바·파이썬 표준 라이브러리가 갈렸나
- 자바 HashMap — 체이닝. 삭제가 잦고 부하율 관리가 단순하다
- 파이썬 dict — 개방 주소법. 캐시 효율과 메모리 밀도를 택했다
정답이 있는 게 아니라 무엇을 중시하느냐의 선택이다.
실무 포인트
체이닝의 실제 약점은 캐시 미스다. 노드가 힙 여기저기 흩어져 있어 리스트를 따라갈 때마다 메모리를 새로 읽는다. 그래서 성능이 극도로 중요한 곳(고성능 라이브러리)에서는 개방 주소법을 쓰는 경우가 많다.