해시 테이블: Java HashMap의 bucket·충돌·키 계약을 끝까지 추적하기

해시 테이블은 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 프로그램이다.

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");
    }
}

javac --release 21 HashTableDemo.java
java HashTableDemo

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

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
Oracle, Map — Java SE 21 API
OpenJDK, HashMap.java — JDK 21 Update source
Oracle, Object.equals and hashCode — Java SE 21 API
Oracle, The Java Language Specification, Java SE 21 — Integer Operations
Oracle, The Java Virtual Machine Specification, Java SE 21 — Heap and Frames