HashMap을 공부하다 보면 마주치는 숫자가 있다.
static final int TREEIFY_THRESHOLD = 8;한 버킷(bin)에 노드가 8개 이상이면 LinkedList 대신 TreeNode(레드-블랙 트리)로 전환한다는 뜻이다.
그런데 여기서 가장 중요한 질문은 이것이다.
왜 하필 8일까?
6은 안 되고, 10은 안 되는 걸까?
이 숫자는 임의가 아니다. 확률, 성능, 메모리 비용, 보안 문제까지 고려한 설계 타협점이다.
먼저 전제: HashMap은 원래 LinkedList 구조다
충돌이 발생하면 구조는 이렇게 된다.
table[i] → Node → Node → Node → ...즉, 버킷은 기본적으로 LinkedList다.
LinkedList의 탐색 시간은:
O(n)
노드 수가 많아질수록 선형적으로 느려진다.
그렇다면 왜 바로 트리로 바꾸지 않을까?
트리는 탐색이 빠르다.
| 구조 | 탐색 시간 |
|---|---|
| LinkedList | O(n) |
| Red-Black Tree | O(log n) |
그럼 애초에 트리를 쓰면 되지 않을까?
문제는 이것이다.
HashMap 소스 주석:
TreeNodes are about twice the size of regular nodes
TreeNode는:
- parent
- left
- right
- color(레드/블랙)
추가 포인터가 많다.
즉,
메모리 비용이 약 2배
그래서 노드가 2~3개일 때 트리로 바꾸는 건 과한 최적화다.
확률적으로 8은 거의 발생하지 않는다
HashMap 소스 주석에는 이런 내용이 나온다.
Under random hashCodes, the frequency of nodes in bins follows a Poisson distribution with parameter about 0.5 (load factor 0.75 기준)
기본 load factor = 0.75
resize 직전 평균 λ ≈ 0.5
이때 한 버킷에 k개 노드가 몰릴 확률은:
| 노드 수(k) | 확률 |
|---|---|
| 0 | 60% |
| 1 | 30% |
| 2 | 7.5% |
| 3 | 1.2% |
| 4 | 0.15% |
| 5 | 0.015% |
| 6 | 0.0013% |
| 7 | 0.000094% |
| 8 | 0.000006% |
중요한 지점은 여기다.
8개 이상이 한 버킷에 몰릴 확률은 천만 분의 1 이하
즉, 정상적인 hash 분포라면 8개 이상은 거의 발생하지 않는다.
그렇다면 8의 의미는 무엇인가?
8은 이런 의미를 가진다.
“이 정도면 우연이 아니라 구조적으로 문제가 있는 상황이다.”
예를 들어:
- hashCode를 잘못 구현했거나
- 모든 key가 같은 hashCode를 반환하거나
- 악의적인 충돌 공격(DoS)
이런 경우 한 버킷에 노드가 계속 쌓인다.
Java 8 이전에는 이 상황에서 HashMap이 O(n)으로 무너졌다.
그래서 Java 8에서 Tree 구조를 도입했다.
최종 정리
TREEIFY_THRESHOLD가 8인 이유는:
- 정상적인 해시 분포에서는 거의 발생하지 않는 수준이며
- LinkedList 탐색이 성능 저하를 일으키기 시작하는 지점이고
- TreeNode는 메모리 비용이 크기 때문에 남용할 수 없으며
- 악의적 충돌 공격을 방어하기 위한 안전장치이기 때문이다.
한 문장으로 정리하면:
8은 우연과 비정상을 구분하는 경계선이다.
