---
title: "해시 테이블: Java HashMap의 bucket·충돌·키 계약을 끝까지 추적하기"
slug: "java-hash-table"
category: "CS"
topic: "cs"
subtopic: "data-structures"
tags: ["Java","HashMap","Hash Table","Hash Collision","JVM Memory"]
status: "published"
created: "2026-08-06"
updated: "2026-08-06"
summary: "키를 bucket 후보로 바꾸는 과정부터 충돌·resize·equals/hashCode 계약·boxing과 node 할당까지 추적하고, 해시를 쓰면 안 되는 조건도 비교한다."
kind: "Deep Dive"
evidence: "Java SE 21 HashMap/Map API와 OpenJDK HashMap 소스를 직접 대조하고 two-sum·record key·overflow 경계를 OpenJDK 21.0.11에서 실행"
series: "Java Essential Algorithms"
---

해시 테이블은 key를 배열 index로 바로 바꾸는 마법이 아니다. `hashCode`로 **bucket 후보**를 좁힌 뒤 같은 bucket 안에서 `equals`로 실제 key를 구분한다. 평균 $O(1)$이라는 결론은 hash 분산과 capacity가 충분하다는 조건부 결과다.

## 1. 문제와 연산 계약

자료구조의 기본 계약은 `put(key,value)`, `get(key)`, `remove(key)`다. 동일 key는 무엇인지, null을 허용하는지, iteration 순서를 보장하는지, 동시 mutation을 허용하는지까지 정해야 한다.

Java `HashMap`은 null key/value를 허용하고 순서를 보장하지 않으며 synchronized 구현이 아니다. value가 null일 수 있으므로 `get(key)==null`만으로 key 부재와 null value를 구분할 수 없고 필요하면 `containsKey`를 써야 한다.

예제 문제는 합이 target인 서로 다른 두 index를 찾는 two-sum이다. 먼저 본 `value -> 첫 index`를 map에 보관한다. 결과가 없으면 빈 배열, null 입력은 계약 위반이다. target과 value의 차이는 `long`으로 계산해 `int` wraparound로 존재하지 않는 보수를 찾는 버그를 막는다.

## 2. 내부 상태: table, bucket, entry

개념 모델에서 capacity가 $m$이면 bucket index는 hash를 $[0,m)$으로 줄인 값이다. 서로 다른 key가 같은 index를 얻는 것이 collision이다. OpenJDK 21 `HashMap`은 power-of-two table을 사용하고 `(n - 1) & hash`로 index를 계산한다. bucket에는 node chain이 놓이고, 충돌이 많은 조건에서는 tree bin으로 전환하는 구현이 있다. 이 상수와 임계값은 API 계약이 아니라 OpenJDK 구현 세부이므로 다른 JDK에 일반화하지 않는다.

| two-sum 단계 | 현재 값 | 필요한 보수 | 조회 결과 | map 상태 |
| ---: | ---: | ---: | --- | --- |
| 0 | 2 | 7 | 없음 | `{2=0}` |
| 1 | 7 | 2 | index 0 | `[0,1]` 반환 |

**불변식:** index `i` 시작 시 map에는 `values[0..i)`에 등장한 각 값의 첫 index가 있다. 보수가 있으면 그 index는 `i`보다 작아 서로 다른 두 원소이고 합 계약을 만족한다. 없으면 현재 값을 저장해 다음 단계의 가능한 왼쪽 원소를 보존한다.

## 3. `hashCode`와 `equals`가 함께 지켜야 하는 것

Java의 일반 계약은 `equals`가 true인 두 객체가 같은 `hashCode`를 반환해야 한다는 것이다. 반대는 필요 없다. 같은 hash라도 `equals`가 false면 별도 key다.

key로 사용한 객체의 동등성에 참여하는 field를 삽입 후 변경하면, 조회 시 새 hash가 다른 bucket을 가리켜 entry를 잃어버린 것처럼 보일 수 있다. immutable `record Key(String tenant, long userId)`는 값 동등성과 불변 field를 함께 제공해 예제 key에 적합하다. 무조건 record가 정답은 아니며 배열 field는 record의 기본 `equals`가 내용 비교를 해주지 않는다는 경계도 있다.

## 실행 재현

아래 코드는 설명용 조각이 아니라 `main`에 정상·빈 입력·중복·경계·실패 계약을 함께 넣은 완전한 Java 21 프로그램이다.

```java
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public final class HashTableDemo {
    record Key(String tenant, long userId) {}

    static int[] twoSum(int[] values, int target) {
        if (values == null) throw new IllegalArgumentException("values must not be null");
        Map<Integer, Integer> indexByValue = HashMap.newHashMap(values.length);
        for (int i = 0; i < values.length; i++) {
            long complement = (long) target - values[i];
            if (complement >= Integer.MIN_VALUE && complement <= Integer.MAX_VALUE) {
                Integer previous = indexByValue.get((int) complement);
                if (previous != null) return new int[] {previous, i};
            }
            indexByValue.putIfAbsent(values[i], i);
        }
        return new int[0];
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    public static void main(String[] args) {
        check(Arrays.equals(twoSum(new int[] {2, 7, 11, 15}, 9), new int[] {0, 1}), "normal");
        check(Arrays.equals(twoSum(new int[] {3, 3}, 6), new int[] {0, 1}), "duplicate");
        check(twoSum(new int[0], 10).length == 0, "empty");
        check(twoSum(new int[] {Integer.MIN_VALUE, -1}, Integer.MAX_VALUE).length == 0, "overflow safe");

        Map<Key, String> owners = new HashMap<>();
        owners.put(new Key("alpha", 42), "sj");
        check("sj".equals(owners.get(new Key("alpha", 42))), "value key equality");
        System.out.println("twoSum=[0, 1], key lookup=sj");
    }
}
```

```bash
javac --release 21 HashTableDemo.java
java HashTableDemo
```

직접 실행한 출력은 다음과 같다.

```text
twoSum=[0, 1], key lookup=sj
```

컴파일러와 런타임은 `javac 21.0.11`, OpenJDK `21.0.11`을 사용했다. `assert` 옵션에 의존하지 않고 실패 시 `AssertionError`를 던지므로 위 명령 그대로 검증된다.


## 4. 정당성과 실패 반례

두 index가 존재하고 오른쪽 index를 `j`라고 하자. loop가 `j`에 도달하기 전 왼쪽 값은 map에 저장되어 있다. `target-values[j]`가 그 값이므로 조회가 성공한다. 따라서 존재하는 pair를 지나치지 않는다. `putIfAbsent`를 써서 중복 값에서도 첫 index를 보존한다.

`target - values[i]`를 `int`로 계산하면 `Integer.MAX_VALUE - (-1)` 같은 식이 overflow한다. Java 정수 연산은 이를 예외로 알리지 않는다. 예제는 `long` 차이를 구하고 int 범위 안일 때만 조회한다.

## 5. 시간·공간 복잡도와 resize

좋은 분산을 가정하면 각 `get`/`put`의 기대 비용은 상수이고 전체는 기대 $O(n)$이다. 최악은 collision과 구현에 따라 커질 수 있으므로 “보장된 $O(1)$”이라고 쓰지 않는다. map에는 최대 $n$개 mapping이 들어가므로 보조 공간은 $O(n)$이다.

OpenJDK 문서에 따르면 entry 수가 load factor와 capacity의 곱을 넘으면 rehash가 일어나 table이 대략 두 배가 된다. 한 번의 resize는 많은 entry를 옮기므로 latency spike가 될 수 있다. Java 19+의 `HashMap.newHashMap(expectedMappings)`은 예상 mapping 수에 맞는 map 생성을 돕는다. 그래도 key/value 객체, table array, node와 padding의 정확한 byte는 JOL로 해당 VM을 측정해야 한다.

## 6. JVM 할당 경로

`Map<Integer,Integer>` 예제는 key와 value가 primitive가 아니므로 boxing이 관여한다. 작은 `Integer` cache에 우연히 들어가는 값만 보고 allocation이 없다고 일반화하면 안 된다. `HashMap` object와 backing table, mapping node는 heap에 있고 local map reference와 loop index는 current frame 관점에서 설명한다.

대량 one-shot 계산에서 primitive-specialized map은 boxing/node를 줄일 수 있지만 Java SE 표준 API가 아니므로 라이브러리 선택과 유지보수 비용을 따로 검토한다. JFR allocation event로 실제 hot allocation site를 확인한 뒤 바꾼다.

## 7. TreeMap·배열·정렬과 비교

| 선택 | 조회 | 순서/range | 메모리·갱신 특성 |
| --- | ---: | --- | --- |
| HashMap | 기대 $O(1)$ | key 순서 없음 | table+node, resize |
| TreeMap | $O(\log n)$ | 정렬·range query | tree node, 회전 |
| 정렬 배열+이진 탐색 | $O(\log n)$ | 정렬 순회 | 연속 저장, 삽입 이동 |
| 직접 주소 배열 | $O(1)$ | 작은 조밀 정수 범위 | 범위 크기만큼 예약 |

정렬된 결과나 prefix/range 질의가 필요하면 HashMap만으로 해결하지 않는다. key 범위가 `[0,1000]`처럼 작고 조밀하면 array/bitset이 더 단순하다. adversarial key를 외부에서 받는 보안 경계라면 collision과 자원 고갈도 threat model에 넣는다.

## 8. 실제 도메인 적용

- **Backend cache/dedup**: key cardinality, hit ratio, eviction, resize, allocation rate를 본다. 동시 접근이면 `ConcurrentHashMap`의 atomic method 계약을 사용하며 check-then-act를 분리하지 않는다.
- **Database hash join**: build-side rows와 distinct keys, spill bytes, skewed bucket을 관측한다. memory budget을 넘으면 disk spill이 평균 상수 시간 모델을 무너뜨린다.
- **Data grouping**: group cardinality와 hot key 비율을 본다. 한 key에 데이터가 몰리면 distributed partition도 skew된다.

## 9. 더 활용할 수 있는 곳

frequency table, memoization, inverted index의 term dictionary, graph 정점 ID mapping으로 확장할 수 있다. 하지만 expiry, ordering, durability, concurrency는 HashMap 자체가 제공하지 않는다. 필요한 운영 계약을 wrapper 이름 뒤에 숨기지 말고 별도 구성 요소로 설계한다.

## 10. 이건 피한다

- **mutable key를 삽입한다.** hash/equals field가 바뀌면 조회·삭제가 실패해 memory leak처럼 남는다. immutable value object를 key로 사용한다.
- **평균 $O(1)$을 최악 보장으로 쓴다.** collision, resize, GC가 tail latency를 만든다. 분포·capacity·allocation을 측정한다.
- **순서가 필요한데 HashMap iteration에 의존한다.** API가 순서를 보장하지 않는다. insertion order면 `LinkedHashMap`, key order면 `TreeMap`을 검토한다.
- **동시 write에 일반 HashMap을 공유한다.** data race와 복합 연산 경쟁이 생긴다. `ConcurrentHashMap.compute` 같은 atomic API나 외부 동기화를 쓴다.
- **`get()==null`만으로 부재를 판정한다.** null value와 구분되지 않는다. null을 금지하거나 `containsKey` 계약을 쓴다.

## Reference

- Oracle, [HashMap — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/HashMap.html)
- Oracle, [Map — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Map.html)
- OpenJDK, [HashMap.java — JDK 21 Update source](https://github.com/openjdk/jdk21u/blob/master/src/java.base/share/classes/java/util/HashMap.java)
- Oracle, [Object.equals and hashCode — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/lang/Object.html)
- Oracle, [The Java Language Specification, Java SE 21 — Integer Operations](https://docs.oracle.com/javase/specs/jls/se21/html/jls-4.html#jls-4.2.2)
- Oracle, [The Java Virtual Machine Specification, Java SE 21 — Heap and Frames](https://docs.oracle.com/javase/specs/jvms/se21/html/jvms-2.html#jvms-2.5)