“충돌이 많아지면 Tree로 바뀐다”
하지만 이 문장은 너무 많은 걸 생략한다.
- 충돌이 정확히 뭔지
- “많다”는 기준이 뭔지
- 왜 LinkedList로는 부족한지
- 왜 아무 때나 Tree로 안 바꾸는지
이 글에서는 HashMap 소스 코드에 실제로 등장하는 상수와 주석을 기반으로, 충돌 → 성능 문제 → 트리화(Treeify)까지의 흐름을 정리한다.
해시 충돌과 성능 문제
충돌(collision)이란 무엇인가?
HashMap에서 충돌이란,
서로 다른 key들이 같은 버킷(table의 같은 index)에 매핑되는 상황
을 의미한다.
HashMap의 기본 구조는 다음과 같다.
Node<K,V>[] table;- table은 1차원 배열
- table의 각 칸이 하나의 버킷(bucket)
index는 개념적으로 다음과 같이 계산된다.
index = hash & (table.length - 1);key는 많고, table 길이는 유한하기 때문에 충돌은 필연적으로 발생한다.
중요한 점은 이것이다.
충돌은 오류가 아니라 정상 동작이다.
HashMap은 충돌을 전제로 설계된 자료구조다.
충돌이 발생하면 구조는 어떻게 될까?
충돌이 발생한 버킷은 이런 구조가 된다.
table[i] → NodeA → NodeB → NodeC → ...- table[i]에는 Node 하나의 시작점(head) 만 들어 있음
- 나머지는 Node.next로 연결됨
- 즉, 연결리스트(LinkedList) 구조
왜 이게 문제가 될까?
HashMap의 핵심 연산은 get(key)다.
map.get(key);내부 흐름은 다음과 같다.
- key.hashCode() 계산
- index 계산 → table[index]
- Node를 하나씩 따라가며 equals 비교
여기서 성능이 갈린다.
- Node가 1개 → 비교 1번
- Node가 8개 → 최대 8번
- Node가 100개 → 최대 100번
즉,
버킷에 Node가 많아질수록 HashMap의 탐색 성능은 O(1)에서 O(n)으로 무너진다.
이 순간 HashMap은 “빠른 Map”이 아니라 그냥 LinkedList 탐색기가 된다.
최악의 경우는 실제로 발생할 수 있다
HashMap 소스 주석에는 이런 의도가 명확히 드러난다.
performance degrades gracefully under accidental or malicious usages in which hashCode() methods return values that are poorly distributed
즉,
- 실수로 hashCode를 잘못 구현하거나
- 의도적으로 모든 key가 같은 hashCode를 반환하면
👉 모든 Node가 하나의 버킷에 몰릴 수 있다.
이걸 방치하면:
- get / put / remove 전부 O(n)
- HashMap의 존재 이유가 사라진다
그래서 다음 단계(트리화) 가 필요해진다.
Treeify: LinkedList → TreeNode 전환
HashMap 소스에는 다음과 같은 상수들이 있다.
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;이 숫자들은 전부 충돌과 성능 문제를 제어하기 위한 장치다.
언제 Tree로 바뀌는가?
HashMap은 아무 때나 트리화하지 않는다.
다음 두 조건을 동시에 만족할 때만 Tree로 바꾼다.
- 한 버킷의 Node 개수 ≥ 8
- table 크기(capacity) ≥ 64
이 조건은 소스 코드 주석에 그대로 드러나 있다.
/*
* The bin count threshold for using a tree rather than list for a bin.
*/
static final int TREEIFY_THRESHOLD = 8;
/*
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
*/
static final int MIN_TREEIFY_CAPACITY = 64;왜 기준이 8일까?
8은 “마법의 숫자”가 아니다.
리스트 탐색과 트리 탐색의 비용 차이가 확실하게 벌어지기 시작하는 지점이다.
- Node가 적을 때 → LinkedList가 더 단순하고 빠름
- Node가 많아질 때 → O(n) 비용이 부담됨
그래서 자바는 이렇게 판단한다.
“이제는 리스트로 버티는 게 손해다”
그 기준점이 8이다.
그런데 왜 table 크기 조건(64)이 붙을까?
여기서 중요한 질문이 나온다.
“Node가 8개 이상이면 무조건 충돌 문제일까?”
답은 아니다.
자주 발생하는 상황은 이거다.
- table 크기가 너무 작음
- resize가 아직 안 됨
- 그래서 우연히 한 버킷에 몰림
이 경우:
- Tree로 바꾸는 건 과한 비용
- resize 한 번이면 해결 가능
그래서 HashMap은 이렇게 행동한다.
table이 충분히 커지기 전(capacity < 64)에는
트리화하지 말고 resize부터 하라
즉,
- capacity < 64 → resize 우선
- capacity ≥ 64 + 충돌 지속 → treeify
왜 TreeNode는 무거운가?
HashMap 소스 주석에는 이런 설명도 있다.
/*
* Because TreeNodes are about twice the size of regular nodes,
* we use them only when bins contain enough nodes to warrant use
*/TreeNode는:
- 포인터가 많고
- 회전, 재균형 로직이 필요하고
- 메모리 비용이 크다
그래서 정말 필요할 때만 사용한다.
정리: HashMap의 충돌 대응 전략
HashMap의 충돌 대응은 단계적이다.
- 충돌 허용 (기본 구조)
- LinkedList로 처리
- resize로 분산 시도
- 그래도 안 되면 Tree로 전환
이를 한 문장으로 정리하면 다음과 같다.
HashMap은 평균 성능과 최악 성능 사이에서 비용을 최소화하는 방향으로 점진적으로 구조를 강화하는 자료구조다.
