오늘의 예제는 이렇게 생겼다.
public static void main(String[] args) {
final HashMap<String, Object> objectObjectHashMap = new HashMap<>();
objectObjectHashMap.put("key1", "value1");
final Object value = objectObjectHashMap.get("key1");
System.out.println("value = " + value);
}
이 단순한 코드를 디어셈블링하여 보면 아래와 같다.
public class Main {
public Main();
Code:
0: aload_0
1: invokespecial #1 // Method java/lang/Object."<init>":()V
4: return
public static void main(java.lang.String[]);
Code:
0: new #2 // class java/util/HashMap
3: dup
4: invokespecial #3 // Method java/util/HashMap."<init>":()V
7: astore_1
8: aload_1
9: ldc #4 // String key1
11: ldc #5 // String value1
13: invokevirtual #6 // Method java/util/HashMap.put:(Ljava/lang/Object;Ljava/lang/Object;)Ljava/lang/Object;
16: pop
17: aload_1
18: ldc #4 // String key1
20: invokevirtual #7 // Method java/util/HashMap.get:(Ljava/lang/Object;)Ljava/lang/Object;
23: astore_2
24: getstatic #8 // Field java/lang/System.out:Ljava/io/PrintStream;
27: aload_2
28: invokedynamic #9, 0 // InvokeDynamic #0:makeConcatWithConstants:(Ljava/lang/Object;)Ljava/lang/String;
33: invokevirtual #10 // Method java/io/PrintStream.println:(Ljava/lang/String;)V
36: return
}
1) HashMap 생성
0: new #2 // java/util/HashMap 객체 메모리 할당
3: dup // 스택에 있는 참조를 복사 (생성자 호출 후에도 참조 유지하려고)
4: invokespecial #3 // HashMap.<init>() 생성자 호출
7: astore_1 // 로컬 변수 1에 저장 (map 변수)
2) put 호출
8: aload_1 // map 로드
9: ldc #4 // "key1" (상수 풀에서 로드)
11: ldc #5 // "value1"
13: invokevirtual #6 // map.put(key, value)
16: pop // 반환값(Object, 이전 값) 버림
3) get 호출
17: aload_1 // map 로드
18: ldc #4 // "key1"
20: invokevirtual #7 // map.get(key)
23: astore_2 // result 변수에 저장
명령어를 잘 몰라도 대충 보면 astore는 저장하고, aload는 적재하고 invoke~는 실행한다는걸 알 수 있다.
invokespecial과 invokevirtual의 차이는 다음과 같다.
| 구분 | invokespecial | invokevirtual |
| 바인딩 시점 | 컴파일 시점(고정) | 런타임(동적) |
| 사용 대상 | 생성자, private, super 호출 | 인스턴스 메서드(오버라이드 가능) |
| 오버라이드 영향 | 받지 않음 | 받음 |
| 성능 | 디스패치 과정 없음(고정 호출) | 가상 메서드 테이블 탐색 필요 |
| 대표 예 | super() 생성자 호출 | obj.method() |
그래서 HashMap 생성할때는 invokespecial, get과 put을 호출할때는 invokevirtual을 사용한다.
invokespecial는 컴파일 시점에 호출할 메서드가 고정 되는 정적 바인딩 방식이고, invokevirtual는 런타임에 객체의 실제 타입을 보고 호출할 메서드를 결정한다. 보통 오버라이딩 된 메스드를 호출 할 경우 사용 된다.
기껏 디어셈블링하여 봤지만, 결국 오버라이딩 된 메서드를 호출한다는것 말고는 옵코드를 봐도 알 수 있는 것이 없다.
HashMap.java를 확인해 보자.
HashMap은 java.util 패키지에 위치하며 AbstractMap<K,V>를 확장하고 Map<K,V>와 Cloneable, Serializable을 구현한다.
오래되었지만 자주 사용되는 클래스인 만큼 주석이 엄청 자세하고 길게 적혀 있다.
이것만 읽어도 HashMap 공부는 뚝딱일것 같다.
LLM에 번역을 시키고 딸깍 복붙만 해본다. 이 주석에 모든 중요한 내용이 다 있다.
1. 클래스 개요
• 자료구조: 해시 테이블 기반의 Map 구현체.
• 특징:
• 모든 선택적 Map 연산(get, put, remove 등)을 지원.
• null key와 null value 허용.
• 동기화되지 않음 → 멀티스레드 환경에서는 외부에서 동기화 필요.
• 요소의 순서 보장 안 함 (시간이 지나면 순서가 변할 수 있음).
• Hashtable과 비슷하지만:
• HashMap은 동기화되지 않음.
• HashMap은 null 허용.
⸻
2. 성능 특성
• get, put: 평균적으로 O(1) 시간 복잡도 (좋은 해시 함수 가정).
• iteration: capacity(버킷 수) + size(키-값 쌍 수)에 비례하는 시간 소요.
• 초기 용량(capacity)와 부하율(load factor)에 따라 성능이 달라짐.
⸻
3. 초기 용량과 부하율
• capacity: 해시 테이블의 버킷 개수 (항상 2의 거듭제곱).
• load factor: 버킷이 얼마나 차면 크기를 두 배로 늘릴지 결정.
• 기본값: 0.75 (성능과 메모리 효율의 균형점)
• 현재 size가 capacity × load factor를 초과하면 rehash 발생.
• 초기 용량을 너무 크게 주면 메모리 낭비, 너무 작게 주면 rehash 잦음.
⸻
4. 재해싱(rehash)
• trigger: size > (capacity × load factor)
• 동작: 버킷 수를 2배로 늘리고, 모든 엔트리를 새 버킷에 다시 배치.
⸻
5. 해시 충돌 처리
• 기본적으로 체이닝(Linked List) 사용.
• TREEIFY_THRESHOLD(8) 이상 충돌 발생 시 빨강-검정 트리로 변환.
• 성능: 최악 O(log n) 보장.
• 리스트로 되돌리는 기준(UNTREEIFY_THRESHOLD)은 6 이하.
⸻
6. Comparable 키 처리
• 키들이 Comparable이면 hash 충돌 시 비교 결과를 tie-breaker로 사용해 정렬.
• 특정 조건에서 TreeNode 모드에서 성능 향상.
⸻
7. 스레드 안전성
• 멀티스레드 환경에서 안전하지 않음.
• 동시에 쓰기 작업이 발생하면 외부 동기화 필요:
Map m = Collections.synchronizedMap(new HashMap(...));
⸻
8. Fail-Fast Iterator
• Iterator로 순회 중 구조적 변경(put, remove)이 발생하면
즉시 ConcurrentModificationException 발생.
• 단, 완벽하게 보장되진 않음(“best-effort”).
⸻
9. 용도 요약
• 키-값 저장소로서 빠른 접근이 필요한 경우.
• 키나 값에 null 허용이 필요한 경우.
• 순서 유지가 필요 없고, 스레드 안전성이 요구되지 않는 경우.
다 중요하고, 봐야할 내용이 많기 때문에 이 중 3~6번 내용만 보겠다.
HashMap이기 때문에 Hash 기반의 Map인건 1번 설명을 읽지 않았더라도 유추 할 수 있다.
HashMap에 값을 넣을때는 key를 hash 함수를 통해 hashing하여 값을 저장한다.
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
이때 key가 null이 아니면
1. key의 hashCode()함수를 호출한 결과를 준비,
0b101100101010000000000000000011112. hashCode 값을 우측 16비트 시프트(왼쪽 16개 비트가 0으로 차면서 값이 오른쪽으로 밀림)
0b000000000000000010110010101000003. 두 값을 XOR 연산(^)을 하여 hash key로 사용하고, 이 과정을 hash 값을 퍼트린다 하여 스프레딩(spreading)이라 한다.
XOR 연산
0 ^ 0 = 0
1 ^ 0 = 1
0 ^ 1 = 1
1 ^ 1 = 0
원본 h : 10110010101000000000000000001111
h >>> 16 : 00000000000000001011001010100000
XOR 결과 : 10110010101000001011001010101111
이렇게 계산 된 key를 Node<K,V>[] 타입의 필드에 저장해두고 관리하게 된다.
transient Node<K,V>[] table; // 해시 테이블(버킷 배열)
Node<K,V> 배열의 인덱스 하나가 버킷(bucket) 이고, 해시 충돌이 나면 같은 버킷에 여러 노드가 연결된다.
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // key의 해시 값 (스프레딩 이후)
final K key; // 키
V value; // 값
Node<K,V> next; // 같은 버킷의 다음 노드(연결 리스트)
}
hash: 위에서 확인한 hash(key)함수의 반환 값
key: 실제 키 객체
value: 매핑된 값
next: 같은 버킷 내 다음 엔트리(충돌 해결용)
지금까지 알아본 내용을 바탕으로 HashMap에 값을 넣어보자.
put(key, value) 실행
1. hash 계산
int hash = hash(key); // key.hashCode() 스프레딩
2. 버킷 인덱스 계산
int i = (n - 1) & hash; // n = table.length (항상 2^k)
- 해당 버킷 확인
- 비어 있으면 새 Node 저장.
- 이미 있으면:
- 같은 키인지 확인 (hash와 equals() 비교)
- 같으면 값 덮어쓰기
- 다르면 next에 저장 LinkedList 또는 트리(TreeNode)에 추가
- 트리 변환 조건
- 같은 버킷에 8개 이상 엔트리가 쌓이면 TreeNode(Red-Black Tree)로 변환.
- 반대로 줄어들면 LinkedList 로 복귀
위와 같은 방식 때문에 put으로 값을 넣을때는 조회가 일어난 뒤 삽입이 일어난다.
조회시와 삽입, 그리고 삭제 시에는 Node 배열의 인덱스로 접근하기 때문에(O(1))의 시간 복잡도를 갖는다.
하지만 충돌이 날 경우에는 LinkedList 혹은 TreeNode로 변환하기 때문에 O(log n)을 보장한다.
기존에 Java7까지는 LinkedList만 사용 했기 때문에 최악의 경우 O(n)의 시간 복잡도로 성능이 떨어졌었다.
하지만 Java 8부터 버킷의 entry가 특정 개수 이상이 되면 Red-Black Tree로 변환하여 시간 복잡도를 최대 O(log n)을 보장한다.
table[] (버킷 배열)
+---+ +------------------+
| 0 | -> null
| 1 | -> Node(hash, keyA, valA) -> Node(hash, keyB, valB) -> null
| 2 | -> null
| 3 | -> TreeNode(hash, keyC, valC) ... (레드-블랙 트리)
| 4 | -> Node(hash, keyD, valD) -> null
...
단순히 put 메서드 한번 호출하는데 뭐가 많다.
HashMap의 필드를 보면 더 자세한 내용을 알 수 있다.
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // == 16
기본 초기 용량
HashMap을 만들 때 별도 capacity 지정이 없으면 기본 크기 16으로 생성됩니다.
2의 제곱수여야 해시 분배 효율이 좋고, 해시 충돌 처리를 빠르게 할 수 있습니다.
static final int MAXIMUM_CAPACITY = 1 << 30;
최대 용량
HashMap의 테이블 크기가 가질 수 있는 최대 값 = 2^30 = 1,073,741,824
이 값보다 더 크게 늘어나지 않습니다.
메모리 한계와 해시 알고리즘 설계상 이 이상 커지면 이득이 거의 없어서 제한합니다.
static final float DEFAULT_LOAD_FACTOR = 0.75f;
기본 부하율(load factor)
“버킷이 몇 % 차면 리사이즈할지”를 결정하는 값
0.75f는 공간과 성능(해시 충돌 빈도) 사이에서 절충한 값
예: capacity가 16이면, 16 × 0.75 = 12개의 entry가 들어가면 resize 발생
static final int TREEIFY_THRESHOLD = 8;
체이닝(LinkedList) → 트리(Red-Black Tree)로 변환되는 기준
같은 버킷(bucket)에 8개 이상의 노드가 모이면 O(n)에서 O(log n)으로 성능 개선을 위해 트리화.
단, 용량이 작으면 대신 리사이즈를 먼저 시도합니다.
static final int UNTREEIFY_THRESHOLD = 6;
트리 → LinkedList로 되돌리는 기준
리사이즈나 삭제로 버킷의 노드 수가 6개 이하가 되면, 굳이 트리 구조를 유지할 필요가 없어 다시 단순 연결리스트로 변경.
이유: 트리 유지 비용이 연결리스트보다 커서, 노드 수가 적으면 오히려 비효율적.
static final int MIN_TREEIFY_CAPACITY = 64;
트리화가 일어날 최소 테이블 크기
즉, capacity가 64 미만이면, 노드가 많아도 트리화 대신 먼저 리사이즈를 시도.
이유: 버킷이 적어서 노드가 몰리는 것은 구조 문제보다는 전체 용량 부족 문제일 가능성이 높기 때문.
요약하자면, 최소 크기 16으로 Map을 생성하고 엔트리에 75%의 값이 찰때 크기가 64보다 작으면 리사이즈를, 64보다 크고 버킷의 노드가 8개 이상이면 해당 버킷은 TreeNode로 변환, 6개 이하면 LinkedList로 변환한다는 뜻이다.
** 이때 리사이즈는 기존 용량의 2배로한다.
해시 충돌이 발생 했을 때 다음 빈 슬롯을 찾는 선형 탐사(Linear Probing)방식과 이중 해싱(Double Hashing)방식과 함께 체이닝(Chaining) 방식이 주로 사용되는데, HashMap은 기본적으로 Separate Chaining + (Java 8부터) Treeified Chaining 구조이다.
HashMap을 그냥 쓰기나 했지 제대로 알지는 못했는데, 내부 구현을 이제서야 확인해 봤다는게 아쉽다.
그리고 역시, 개발에서 쉽고 간단해보일수록 그 내부 구현이 복잡하고 잘 짜여졌다는걸 느낄 수 있었다.
** TreeNode쪽 코드는 복잡해서 아직은 이해가 잘 안된다.
참고자료
graalvm-jdk-21
'공부 기록' 카테고리의 다른 글
| TIL의 의미가 바뀌었습니다. (1) | 2026.01.04 |
|---|---|
| 자바에서 HashSet에 값 넣고 꺼내기 (5) | 2025.08.10 |
| 자바에서 Stack 클래스는 언제 쓰나? (9) | 2025.08.05 |
| 자바에서 배열은 클래스인가? (7) | 2025.08.04 |
| [NEXTSTEP] ATDD 과정 4주차 피드백, 5주차 시작[끝] (0) | 2023.08.19 |
댓글