Java HashMap 내부 구조 — Bucket, Treeification, resize, 그리고 hash 한 줄의 비밀
HashMap은 자바를 처음 배울 때 가장 먼저 만나는 자료구조 중 하나입니다. 그래서 평균 O(1)이라는 한 줄 설명에 익숙해진 채로 넘어가기 쉽지만, 그 안에는 빨강검정 트리, 푸아송 분포, 단 한 줄의 비트 연산으로 압축된 hash 분산 트릭이 숨어 있습니다. 이 글은 OpenJDKHashMap.java소스를 따라가며 자바 8 이후HashMap이 어떤 모양으로 동작하는지 정리합니다. 자바를 어느 정도 다뤄 봤지만 내부를 들여다본 적이 없는 분을 대상으로 합니다.
HashMap이라는 자료구조
java.util.HashMap은 키-값 쌍을 평균 O(1)로 넣고 꺼내는 해시 테이블입니다. 키의 hashCode()로 키가 들어갈 자리(이하 bucket)를 정하고, 해당 자리에 키-값 쌍을 꽂아 두는 방식입니다. 같은 자리에 여러 키가 몰리면(이하 충돌, collision) 그 자리에서 연결 리스트나 트리를 만들어 보관합니다.
자바 8 이전까지 HashMap은 array + linked list 구조였습니다. 충돌이 심한 bucket에서 조회·삽입은 O(n)까지 떨어졌고, 악의적으로 같은 hash를 가지는 키만 골라 집어넣는 hash collision DoS 공격에도 취약했습니다.
자바 8부터 한 bucket의 노드 수가 일정 기준을 넘으면 그 bucket만 빨강검정 트리로 변신합니다(이하 treeification). 최악 시간 복잡도가 O(log n)으로 줄어들고, hash collision DoS 시나리오에서도 응답 시간이 폭발하지 않습니다.
flowchart LR
Key[Key]
Hash["hash = key.hashCode() ^ (h >>> 16)"]
Index["index = hash & (table.length - 1)"]
Bucket["table[index]"]
LinkedList["Linked List<br/>nodes <= 8"]
Tree["Red-Black Tree<br/>nodes > 8 and table.length >= 64"]
Key --> Hash --> Index --> Bucket
Bucket --> LinkedList
Bucket --> Tree
HashMap의 핵심 질문은 결국 두 가지로 좁혀집니다.
hashCode()가 들쭉날쭉할 때 bucket index를 어떻게 고르게 분산시킬 것인가- 한 bucket이 비대해지면 어떻게 대응할 것인가
OpenJDK의 HashMap.java(JDK 21 master 기준)는 이 두 질문에 대한 답을 단 여섯 개의 상수와 200줄 남짓의 핵심 메서드 두 개에 담아 두었습니다.
핵심 필드와 상수
인스턴스 필드
transient Node<K,V>[] table;
transient int size;
int threshold;
final float loadFactor;
transient int modCount;
table: bucket 배열입니다. 길이는 항상 2의 거듭제곱입니다.size: 현재 저장된 key-value 쌍의 개수입니다.threshold:table을 다음으로 resize할 임계점.capacity * loadFactor로 계산합니다.loadFactor: 적재율 한계. 기본 0.75.modCount: 구조가 바뀔 때마다 증가하는 카운터. fail-fast iterator의 핵심입니다.
상수 여섯 개
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
이 여섯 개의 값이 HashMap의 모든 동작을 결정합니다.
DEFAULT_INITIAL_CAPACITY = 16: 첫put시 만들 bucket 배열의 기본 크기. 2의 거듭제곱이라는 제약이 핵심이며, 뒤에서 다룰 비트 연산 트릭 두 가지가 이 제약 위에 세워져 있습니다.MAXIMUM_CAPACITY = 1 << 30:int양수 범위 내 2의 거듭제곱 최댓값.DEFAULT_LOAD_FACTOR = 0.75f: 시간·공간 트레이드오프의 합의점. 0.5보다 충돌이 잦고 1.0보다 메모리가 여유롭습니다.TREEIFY_THRESHOLD = 8: 한 bucket의 노드 수가 이 값을 넘으면 트리로 전환합니다.UNTREEIFY_THRESHOLD = 6: 트리 bucket의 노드 수가 이 값 이하로 줄면 다시 연결 리스트로 돌립니다.MIN_TREEIFY_CAPACITY = 64: 전체table길이가 이 값 미만이면 treeify 대신 resize를 먼저 수행합니다.
8과 6의 간격이 왜 2 이상이어야 하는지는 untreeification 절에서 다시 정리합니다.
Node 한 개의 모양
final int hash;
final K key;
V value;
Node<K,V> next;
hash를 다시 들고 다닌다는 점이 핵심입니다. resize와 lookup 모두 key.hashCode()를 다시 부르지 않고 저장된 hash를 그대로 재사용하므로, 비싼 hash 계산은 put 한 번에서 끝납니다.
hash() 한 줄의 비밀
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
세 줄짜리 메서드가 자바 컬렉션에서 가장 자주 인용되는 한 줄을 품고 있습니다. h ^ (h >>> 16). 왜 이런 형태일까요.
비트 마스킹의 한계
bucket index는 (table.length - 1) & hash로 계산합니다. table.length가 2의 거듭제곱이므로 table.length - 1은 하위 k 비트가 모두 1인 마스크가 됩니다. 즉 bucket index는 hash의 하위 비트만 사용합니다.
문제는 많은 객체의 hashCode()가 상위 비트에만 다양성을 가진다는 점입니다. 예를 들어 Integer.hashCode()는 자기 자신을 반환하므로 1부터 1000까지의 정수를 키로 쓰면 상위 비트는 거의 0이고 하위 비트만 1씩 증가합니다. 작은 table(16, 32 정도)에서는 그래도 큰 문제가 없지만, 키 분포가 특정 패턴을 가지는 순간 충돌이 폭증합니다.
XOR 한 번으로 상위 비트 끌어내리기
h ^ (h >>> 16)은 상위 16비트를 하위 16비트와 XOR하여, 상위 비트의 다양성을 하위 비트로 끌어 내립니다. 비트가 섞이지만 정보가 완전히 사라지진 않습니다.
flowchart LR
H["h: 32-bit hash"]
Upper["h >>> 16<br/>(upper 16 bits, lower zeroed)"]
Lower["h<br/>(unchanged)"]
Mix["h ^ (h >>> 16)<br/>(upper bits mixed into lower)"]
Mask["& (table.length - 1)"]
Index["bucket index"]
H --> Upper
H --> Lower
Upper --> Mix
Lower --> Mix
Mix --> Mask --> Index
자바 7의 hash()는 4번의 shift와 3번의 XOR을 사용해 더 정성껏 섞었지만, 자바 8 이후로는 treeification이 충돌의 최악 비용을 받쳐주므로 저렴하게 한 번만 섞어도 충분합니다. OpenJDK 주석에 그 의도가 한 문장으로 정리되어 있습니다.
Because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way.
put: putVal()의 흐름
put(K, V)는 내부적으로 putVal(hash(key), key, value, ...)을 호출합니다. putVal은 길지만 분기를 따라가면 흐름이 명확합니다.
flowchart TD
Start[putVal entry]
Init["table is null? -> resize()"]
IndexCalc["i = (n - 1) & hash"]
Empty{table[i] empty?}
NewNode["table[i] = newNode<br/>++size, ++modCount"]
Head{key == head.key?}
UpdateHead[replace head value]
IsTree{head is TreeNode?}
TreePut[putTreeVal]
Walk[traverse linked list]
Found{found?}
UpdateMid[replace node value]
Append[append new node at tail]
Check{binCount >= TREEIFY_THRESHOLD - 1?}
Treeify[treeifyBin]
SizeCheck{++size > threshold?}
Resize[resize]
Done[return]
Start --> Init --> IndexCalc --> Empty
Empty -->|yes| NewNode --> SizeCheck
Empty -->|no| Head
Head -->|yes| UpdateHead --> Done
Head -->|no| IsTree
IsTree -->|yes| TreePut --> SizeCheck
IsTree -->|no| Walk --> Found
Found -->|yes| UpdateMid --> Done
Found -->|no| Append --> Check
Check -->|yes| Treeify --> SizeCheck
Check -->|no| SizeCheck
SizeCheck -->|yes| Resize --> Done
SizeCheck -->|no| Done
요약하면 이렇습니다.
table이 비어 있으면resize()로 초기 배열을 만든다.(n - 1) & hash로 index를 구한다.- 그 자리가 비었으면 새 노드를 그대로 박는다.
- 차 있으면 head를 보고, 같은 키면 값을 교체한다.
- 아니면 트리/리스트를 따라가며 같은 키를 찾는다.
- 끝까지 못 찾으면 append 후 카운트가 임계점을 넘었는지 보고 treeify 또는 resize를 호출한다.
여기서 "같은 키"의 판정 기준은 (e.hash == hash) && (k == key || (key != null && key.equals(k)))입니다. hashCode()만으로는 부족하고, 같은 hash가 나와도 equals()가 일치해야 동일 키로 간주합니다. 두 메서드의 계약을 깨면 HashMap은 침묵하며 잘못 동작하게 됩니다.
resize(): 두 리스트로 나누는 비트 트릭
resize는 HashMap에서 가장 자주 호출되면서도 가장 비싼 연산입니다. size가 threshold를 넘으면 table을 두 배로 키우고, 모든 기존 노드를 새 table로 옮깁니다.
단순한 재할당이 아니다
자바 7까지는 모든 노드에 대해 새 capacity로 index를 다시 계산해야 했습니다. 자바 8은 capacity가 2의 거듭제곱이라는 점을 활용해 재계산 없이 노드를 두 그룹으로 가르는 트릭을 도입합니다.
핵심은 한 줄입니다.
if ((e.hash & oldCap) == 0) { /* lo list */ } else { /* hi list */ }
oldCap이 16(0b10000)이라면 e.hash & oldCap은 hash의 다섯 번째 비트가 0인지 1인지를 보는 것입니다. capacity가 두 배가 되면 mask 비트가 하나 늘어나는데, 새로 추가되는 그 비트가 0이면 노드는 같은 index에, 1이면 oldIndex + oldCap으로 이동합니다.
flowchart LR
OldCap["oldCap = 16<br/>mask = 0b01111"]
NewCap["newCap = 32<br/>mask = 0b11111"]
Bit["e.hash & oldCap<br/>(check bit 4)"]
Lo["bit 4 == 0<br/>-> stay at j"]
Hi["bit 4 == 1<br/>-> move to j + oldCap"]
OldCap --> Bit
NewCap --> Bit
Bit --> Lo
Bit --> Hi
두 개의 임시 리스트
각 bucket을 순회하며 lo(원래 자리에 남을 노드)와 hi(새 자리로 갈 노드)로 분리합니다.
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 {
if (hiTail == null) hiHead = e;
else hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
순회를 끝내면 두 개의 단일 연결 리스트가 만들어집니다. 각각의 head를 새 table의 j와 j + oldCap에 꽂아 두면 끝납니다. 노드를 새로 만들지도, hash를 다시 계산하지도 않습니다.
트리 bucket에 대해서도 같은 발상이 적용됩니다. 트리를 분할하다가 한쪽 노드 수가 UNTREEIFY_THRESHOLD = 6 이하로 떨어지면 그 쪽은 연결 리스트로 돌리고, 두 쪽 다 충분히 크면 두 개의 작은 트리로 다시 구성합니다.
resize의 비용
이 트릭이 영리하긴 하지만 결국 모든 노드를 한 번씩 만진다는 사실은 변하지 않습니다. 노드가 100만 개라면 100만 번의 메모리 참조와 비트 연산이 한 번의 put 안에서 일어납니다. 미리 capacity를 잡는 것이 의외로 큰 차이를 만듭니다.
// expectedSize 만큼 들어갈 것을 안다면
int capacity = (int) (expectedSize / 0.75f) + 1;
Map<K, V> m = new HashMap<>(capacity);
이렇게 만들면 적재 도중 resize 호출이 사실상 발생하지 않습니다. 데이터 적재가 끝난 뒤에는 일반 HashMap처럼 동작합니다.
Treeification: 8이라는 숫자의 근거
TREEIFY_THRESHOLD = 8. 왜 7도 9도 아닌 8일까요. OpenJDK 주석은 그 근거를 푸아송 분포로 설명합니다.
Poisson에 기반한 확률
hashCode()가 충분히 무작위라면, load factor 0.75에서 한 bucket의 노드 수는 평균 0.5의 푸아송 분포를 따릅니다. 각 노드 수가 등장할 확률은 다음과 같습니다.
| 노드 수 | 발생 확률 |
|---|---|
| 0 | 0.60653066 |
| 1 | 0.30326533 |
| 2 | 0.07581633 |
| 3 | 0.01263606 |
| 4 | 0.00157952 |
| 5 | 0.00015795 |
| 6 | 0.00001316 |
| 7 | 0.00000094 |
| 8 | 0.00000006 |
노드가 8개에 도달할 확률은 1천만 분의 1 미만입니다. 8 이상의 bucket을 트리로 만든다는 결정은 "정상 분포라면 거의 일어나지 않을 일이고, 만약 발생한다면 그건 hash가 비정상적으로 한쪽으로 쏠렸다는 신호이므로 트리로 보호하자"는 의미입니다.
거꾸로 말하면, 정상적인 워크로드에서는 treeification이 사실상 발생하지 않습니다. treeification은 자바 8 HashMap의 안전망이지 일상이 아닙니다.
MIN_TREEIFY_CAPACITY = 64
그렇다고 무조건 8을 넘으면 트리로 가지는 않습니다. table.length < 64일 때 한 bucket이 8을 넘으면 트리 대신 resize를 합니다.
이유는 단순합니다. 작은 table에서 8개씩 모이는 건 hash 자체의 문제가 아니라 table이 작아서 생긴 충돌일 가능성이 높습니다. table을 두 배로 키우면 hash가 멀쩡한 이상 충돌이 자연스럽게 줄어듭니다. 트리는 일반 노드보다 두 배 가까이 큰 TreeNode를 쓰므로, 굳이 작은 table에서 트리를 만들어 메모리를 두 배로 쓰지 않겠다는 절약입니다.
flowchart TD
Trigger["bin count > TREEIFY_THRESHOLD - 1"]
CheckCap{table.length < MIN_TREEIFY_CAPACITY?}
Resize[resize and rehash]
Convert[convert linked list<br/>to red-black tree]
Trigger --> CheckCap
CheckCap -->|yes, table is small| Resize
CheckCap -->|no, table is large enough| Convert
Untreeification: 8과 6 사이의 간격
트리 bucket에서 노드 수가 줄어 UNTREEIFY_THRESHOLD = 6 이하가 되면 다시 연결 리스트로 돌아갑니다. 트리는 노드당 약 두 배의 메모리를 쓰므로, 크기가 작아진 트리는 비효율적입니다.
여기서 한 가지 디테일이 있습니다. 왜 임계값이 7이 아니고 6일까요. 8 → 7 → 8 → 7 …의 경계에서 진동하면 매 삽입·삭제마다 트리 변환과 리스트 변환이 반복돼 성능이 망가집니다. 트리 변환 임계값(8)과 리스트 변환 임계값(6) 사이에 7이라는 완충 구간을 둠으로써, 한 번 트리화된 bucket이 곧바로 리스트로 돌아가지 않습니다.
이런 종류의 hysteresis(이력 현상)는 시스템에서 자주 만나는 패턴입니다. CPU governor의 frequency 변경 임계값, TCP 혼잡 제어의 cwnd 변동, JVM 코드 캐시의 sweeping 등 모두 같은 발상이 깔려 있습니다.
ConcurrentModificationException과 modCount
HashMap은 thread-safe가 아닙니다. 동시 수정에 대한 방어가 아니라 탐지만 합니다.
transient int modCount;
put, remove, clear, merge 같은 구조 변경 연산은 modCount를 1 증가시킵니다. iterator는 시작 시점의 modCount를 저장해 두고, 매 next()마다 현재 modCount와 비교합니다. 다르면 ConcurrentModificationException을 던집니다.
final HashIterator() {
expectedModCount = modCount;
// ...
}
final Node<K,V> nextNode() {
if (modCount != expectedModCount) throw new ConcurrentModificationException();
// ...
}
이 매커니즘은 "엄격하지 않은 best-effort"입니다. 동시 수정이 있어도 던지지 못할 수 있고(특히 같은 스레드 내에서 iterator 두 개가 서로 모르고 수정하는 경우), 던지더라도 데이터 일관성이 보장되지는 않습니다. 단지 잘못된 사용을 빨리 드러내기 위한 진단 도구입니다.
멀티스레드 환경에서는 Collections.synchronizedMap()이나 ConcurrentHashMap을 써야 합니다.
실전 함정과 권장 사항
내부 구조를 알았으니, 실전에서 자주 만나는 함정들을 정리합니다.
hashCode와 equals 계약 깨기
hashCode()만 오버라이드하고 equals()는 그대로 두거나, 그 반대로 하면 같은 키가 두 번 들어가거나 한 번 들어간 키를 못 찾는 침묵 버그가 생깁니다. IDE 자동 생성 또는 record를 쓰면 두 메서드를 한 번에 안전하게 처리할 수 있습니다.
Mutable 키 사용
HashMap에 넣은 뒤 키 객체의 내부 상태를 바꾸면 hashCode()가 바뀌어 그 키를 영영 찾을 수 없습니다. HashMap은 put 시점의 hash를 노드에 저장하므로, 키가 바뀌어도 노드는 옛 자리에 그대로 남습니다. 키는 사실상 불변이어야 합니다.
초기 capacity 지정
데이터가 얼마나 들어갈지 미리 안다면 new HashMap<>(expectedSize / 0.75 + 1) 형태로 만드세요. JDK 19부터는 같은 의도를 더 명확히 표현하는 정적 팩터리가 있습니다.
// JDK 19+
Map<String, Integer> m = HashMap.newHashMap(1_000_000);
newHashMap(numMappings)은 내부적으로 load factor 0.75를 가정해 적절한 초기 capacity를 계산합니다.
Stream 수집은 toMap을 의식하라
Collectors.toMap은 기본 구현이 HashMap을 만들면서 데이터를 채워 넣습니다. 데이터가 크다면 capacity hint가 없는 toMap은 여러 번 resize를 거쳐 느려질 수 있습니다. 큰 stream을 Map으로 모을 때는 mergeFunction과 mapFactory를 명시한 4-인자 toMap을 사용하세요.
트리 의존성 가정 금지
트리화는 비정상 hash 분포에 대한 안전망이지 정상 워크로드에서 활용할 무언가가 아닙니다. "어차피 8개 넘으면 O(log n)이니 hashCode 대충 짜도 되겠지"는 잘못된 판단입니다. treeification 자체가 비싸고, treeify 대신 resize가 일어나는 케이스도 있으므로, 좋은 hashCode()를 짜는 것이 우선입니다.
HashMap vs ConcurrentHashMap
같은 hash table이지만 두 자료구조는 설계 목표가 다릅니다.
| 항목 | HashMap | ConcurrentHashMap |
|---|---|---|
| 동시성 | 없음 | CAS와 synchronized로 bucket 단위 잠금 |
| null 키/값 | 허용 | 키·값 모두 불허 |
| iterator | fail-fast | weakly consistent |
| resize | 단일 스레드 | stride 기반 협력적 resize |
| size 계산 | 카운터 1개 | LongAdder 스타일 카운터 셀 분산 |
ConcurrentHashMap은 단순한 synchronized HashMap이 아니라, 동시성을 위해 자료구조와 알고리즘을 처음부터 다시 짠 결과물입니다. 이 글에서는 다루지 않지만 별도의 깊은 주제입니다.
정리
HashMap이 단순해 보이지만 핵심을 짚어 보면 다음의 결정들이 쌓여 있습니다.
table.length를 2의 거듭제곱으로 강제 → bucket index를& (length - 1)로 처리 → resize 시 비트 한 개로 lo/hi 분할- 상위 비트를 하위로 XOR하는 한 줄짜리 hash 분산
- load factor 0.75를 기준으로 미리 resize → 평균 충돌 0.5의 푸아송 분포 유지
- 8 노드 이상 bucket을 빨강검정 트리로 → 비정상 분포에서도 O(log n) 유지
- 6과 8 사이에 hysteresis → 경계 진동 방지
MIN_TREEIFY_CAPACITY = 64→ 작은 table에서는 트리 대신 resize 선호modCount기반 fail-fast iterator → 동시 수정의 정적 탐지
각 결정은 독립된 트레이드오프가 아니라 서로 맞물려 있습니다. 푸아송 분포 가정이 깨지면 treeify가 받쳐 주고, treeify가 비대해지면 resize가 분산시키고, resize가 비싸지지 않도록 hash가 한 번만 mix되며, hash가 약하더라도 lower bit 마스킹의 손실을 XOR이 보완합니다. 자료구조 하나가 이만큼의 안전망을 켜켜이 쌓은 사례는 자바 표준 라이브러리에서도 드뭅니다.
내부 구조를 알고 나면 사용 방식도 달라집니다. 좋은 hashCode()를 짜고, 키를 불변으로 두고, 큰 데이터를 채울 땐 capacity를 미리 잡고, 동시성이 필요하면 ConcurrentHashMap으로 갈아타세요. 그것이 자바 8 이후의 HashMap을 가장 빠르게 쓰는 방법입니다.