HashMap initial capacity를 미리 잡아야 하는 이유

배경

HashMap은 자바에서 가장 자주 사용하는 자료구조 중 하나다.
그런데 생성할 때 아무 생각 없이 기본 생성자를 쓰는 경우가 많다.

Map<String, Integer> map = new HashMap<>();

일반적인 상황에서는 큰 문제가 없지만, 저장할 데이터 수를 어느 정도 예상할 수 있다면 초기 용량(initial capacity)을 미리 지정하는 편이 더 효율적이다. 이유는 단순하다. HashMap은 내부 버킷 배열이 가득 차면 resize와 rehash에 가까운 재배치 작업을 수행하기 때문이다. 이 과정은 단순히 배열만 늘리는 작업이 아니라, 기존 엔트리를 새 배열 기준으로 다시 연결해야 하므로 시간과 메모리 비용이 발생한다.

 

목적

이번 글에서는 아래 내용을 정리해 보겠다.

1. HashMap에서 초기 용량이 왜 중요한지
2. new HashMap<>(100)이 정확히 무엇을 의미하는지
3. resize가 발생할 때 내부에서 어떤 일이 일어나는지
4. 실무에서 초기 용량을 어떻게 계산하면 되는지

 

HashMap의 기본 동작

HashMap은 내부적으로 버킷 배열을 사용한다. 엔트리가 계속 추가되다가 임계치(threshold)를 넘으면 테이블 크기를 늘린다.

기본 설정은 보통 아래와 같다.

• 초기 용량: 16
• load factor: 0.75

즉 내부 capacity가 16이라면, 대략 12개 정도의 엔트리가 들어갔을 때 resize가 발생할 수 있다.

threshold = capacity * loadFactor
          = 16 * 0.75
          = 12

문제는 resize가 공짜가 아니라는 점이다. 새 배열을 만들고, 기존 엔트리들을 새 버킷 위치 기준으로 다시 배치해야 한다. 데이터 수가 많아질수록 이 비용은 무시하기 어렵다. 정리하자면 HashMap의 초기 용량을 적절히 주는 이유는, 중간 resize 횟수를 줄이기 위해서다.

 

많이 헷갈리는 포인트

new HashMap<>(100)은 100개를 안전하게 담는다는 뜻이 아니다

이 부분을 가장 많이 오해한다.

Map<String, Integer> map = new HashMap<>(100);

이 코드의 100은 “원소 100개를 넣어도 resize가 일어나지 않는다”는 뜻이 아니다.
이 값은 내부 capacity의 기준값에 가깝고, 실제 구현에서는 2의 거듭제곱 크기로 맞춰진다.

예를 들어 100을 주더라도 내부에서는 128로 맞춰질 수 있다.
그리고 load factor가 0.75라면 실제 resize 임계치는 대략 96 정도가 된다.

internal capacity = 128
threshold = 128 * 0.75 = 96

즉 “100개를 넣을 예정”이라면 HashMap<>(100)만으로는 부족할 수 있다. 이런 일이 가능한 이유는 HashMap이 내부 테이블 크기를 항상 2의 거듭제곱으로 맞춰서 관리하기 때문이다.

 

실무에서 초기 용량 계산하기

실무에서는 보통 예상 엔트리 수를 n이라고 할 때, 아래처럼 계산하면 된다.

initialCapacity >= ceil(n / 0.75)

예를 들어:

• 10개 예상 → 약 14 이상
• 100개 예상 → 약 134 이상
• 1,000개 예상 → 약 1334 이상

코드로는 보통 이렇게 작성한다.

val expectedSize = 100
val map = HashMap<String, Int>((expectedSize / 0.75f).toInt() + 1)

load factor까지 직접 명시하고 싶다면 이렇게도 가능하다.

val map2 = HashMap<String, Int>(134, 0.75f)

실제로는 이 값이 내부에서 다시 2의 거듭제곱 capacity로 보정된다. 그래도 중요한 것은 “예상 개수보다 조금 넉넉하게 시작해서 중간 resize를 줄인다”는 점이다. 정리하자면, 예상 데이터 수를 알고 있다면 n / 0.75 기준으로 초기 용량을 계산하는 습관이 실무에서 가장 안전하다.

 

Resize 발생 시 비용

resize는 단순히 크기만 늘리는 과정이 아니다. 크게 보면 세 가지 비용이 있다.

1. 새 버킷 배열 할당

resize가 시작되면 먼저 더 큰 배열을 새로 만든다.

Node<K,V>[] newTab = (Node<K,V>[]) new Node[newCap];

이 시점에는 기존 배열과 새 배열이 잠깐 함께 존재할 수 있다. 즉 짧은 순간이지만 피크 메모리 사용량이 증가한다.

대용량 HashMap에서는 이 순간적인 메모리 증가가 꽤 부담이 될 수 있다.

2. 기존 엔트리 재배치

많이 오해하는 부분인데, 자바 8 이후 HashMap의 resize는 예전처럼 모든 엔트리에 대해 새 노드를 대량 생성하는 방식과는 다르다. 핵심은 기존 Node 객체를 최대한 재사용하면서, 새 배열 기준으로 연결만 다시 잡는 데 가깝다는 점이다. 즉 비용의 중심은 “노드 복제”보다는 아래 쪽에 있다.

• 새 배열 생성
• 기존 노드 순회
• 새 위치 기준으로 next 포인터 재연결
• 전체 엔트리 O(n) 재배치

그래서 resize의 본질은 “테이블 복사”가 아니라 “배열 재할당 + 연결 구조 재배치”로 이해하는 편이 맞다.

3. GC 비용

resize가 끝나면 기존 버킷 배열은 더 이상 참조되지 않는다. 이 배열은 이후 가비지 컬렉션 대상이 된다.

즉 resize가 자주 발생하면 아래 흐름이 반복된다.

배열 생성 → 잠깐 사용 → 폐기 → GC 회수

작은 맵에서는 체감되지 않을 수 있다. 하지만 큰 맵에서는 배열 크기 자체가 커지므로, 이런 반복 비용이 성능에 영향을 줄 수 있다.

이런 일이 가능한 이유는 resize가 단순 CPU 작업으로 끝나지 않고, 메모리 할당과 회수까지 동반하기 때문이다.

 

Resize 내부 구현 보기

아래는 resize의 핵심 흐름을 이해하기 쉽게 정리한 코드다.

for (int j = 0; j < oldCap; ++j) {
    Node<K,V> e = oldTab[j];
    if (e == null) continue;

    oldTab[j] = null;

    if (e.next == null) {
        newTab[e.hash & (newCap - 1)] = e;
    } else if (e instanceof TreeNode) {
        ((TreeNode<K,V>) e).split(this, newTab, j, oldCap);
    } else {
        Node<K,V> loHead = null, loTail = null;
        Node<K,V> hiHead = null, hiTail = null;

        do {
            Node<K,V> 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;
            }

            e = next;
        } while (e != null);

        if (loTail != null) {
            loTail.next = null;
            newTab[j] = loHead;
        }

        if (hiTail != null) {
            hiTail.next = null;
            newTab[j + oldCap] = hiHead;
        }
    }
}

겉으로 보면 복잡하지만, 큰 그림은 단순하다.

1. 기존 버킷을 하나씩 순회하고
2. 각 버킷의 노드를 분류한 뒤
3. 새 배열의 적절한 위치에 다시 연결한다

과정 1: 기존 버킷을 하나씩 순회

for (int j = 0; j < oldCap; ++j) {
    Node<K,V> e = oldTab[j];
    if (e == null) continue;

여기서 j는 기존 테이블의 버킷 인덱스다. 즉 oldTab[0], oldTab[1], oldTab[2]처럼 전체 버킷을 순회한다.

비어 있는 버킷은 건너뛴다.

과정 2: 기존 배열 참조 정리

oldTab[j] = null;

이 코드는 기존 배열 쪽 참조를 끊는 동작이다. 이후 노드들은 새 배열 쪽으로 다시 연결될 예정이므로, 예전 버킷은 점차 비워진다.

과정 3: 노드가 하나면 바로 이동

if (e.next == null) {
    newTab[e.hash & (newCap - 1)] = e;
}

해당 버킷에 노드가 하나뿐이라면 분류 작업이 필요 없다. 새 capacity 기준으로 인덱스만 다시 계산해서 바로 넣으면 된다.

과정 4: low 그룹과 high 그룹으로 분리

Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;

이 부분이 resize의 핵심이다. capacity가 2배로 증가하면, 기존 버킷 j에 있던 노드들은 새 테이블에서 오직 두 위치 중 하나로만 이동한다.

• 그대로 j
• 또는 j + oldCap

즉 노드를 완전히 새로 흩뿌리는 것이 아니라, 두 그룹으로만 나누면 된다.

• lo: 원래 위치 유지
• hi: oldCap만큼 뒤로 이동

이 구조 덕분에 resize 과정이 비교적 효율적으로 동작한다.

과정 5: 왜 hash & oldCap만 보면 되는가

가장 중요한 분기 조건은 이것이다.

if ((e.hash & oldCap) == 0)

이게 가능한 이유는 HashMap의 capacity가 항상 2의 거듭제곱이기 때문이다. 버킷 인덱스는 보통 아래처럼 계산된다.

index = hash & (capacity - 1)

예를 들어 old capacity가 16이라면:

oldCap     = 16  = 00010000
oldCap - 1 = 15  = 00001111

resize 후 new capacity가 32라면:

newCap     = 32  = 00100000
newCap - 1 = 31  = 00011111

즉 새 마스크는 기존보다 비트 한 자리를 더 본다.
그 추가된 한 자리가 바로 oldCap 비트다.

그래서 기존 버킷 j에 있던 노드는 아래 둘 중 하나로만 이동한다.

• 해당 비트가 0이면 그대로 j
• 해당 비트가 1이면 j + oldCap

정리하자면, resize 시 재배치가 비교적 효율적인 이유는 “capacity를 2배로 늘릴 때 새 인덱스가 완전히 새로 계산되는 것이 아니라, 기존 인덱스 기준으로 두 갈래만 나뉘기 때문”이다.

과정 6: 기존 노드를 새로 만들지 않고 다시 연결

예를 들어 low 그룹에 속한 노드는 아래처럼 처리된다.

if (loTail == null) loHead = e;
else loTail.next = e;
loTail = e;

이 코드는 연결 리스트 뒤에 노드를 붙이는 전형적인 방식이다. 예를 들어 기존 체인이 아래와 같고,

A -> B -> C -> D

분류 결과가 아래처럼 나왔다면,

• A: low
• B: high
• C: low
• D: high

resize 후에는 다음처럼 재구성된다.

low  = A -> C
high = B -> D

여기서 중요한 점은 A, B, C, D라는 노드를 새로 만들지 않는다는 것이다.
기존 노드를 그대로 사용하고, next 연결만 다시 잡는다.

과정 7: 새 테이블에 배치

마지막에는 분리된 두 리스트를 새 배열에 넣는다.

if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}

if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

여기서 tail.next = null을 해 주는 이유도 중요하다. 이전 연결이 남아 있으면 잘못된 체인이 유지될 수 있기 때문이다. 즉 resize는 “노드 이동”이라기보다 “연결 구조 재구성”에 더 가깝다.

 

주의점

1. 작은 맵에서는 과도한 최적화가 의미 없을 수 있다

데이터가 몇 개 안 들어가는 맵이라면 기본 생성자를 사용해도 충분하다. 초기 용량 지정은 “성능에 민감한 경로”나 “대량 데이터 삽입”에서 더 의미가 있다.

2. 너무 크게 잡아도 메모리 낭비가 생긴다

resize를 피하겠다고 지나치게 큰 초기 용량을 주면, 사용하지 않는 버킷 배열 공간이 남는다. 즉 무조건 크게 잡는 것이 정답은 아니다. 예상 크기를 어느 정도 신뢰할 수 있을 때만 적용하는 편이 좋다.

3. HashMap<>(n)과 “n개 저장 가능”은 다르다

이건 다시 한 번 강조할 필요가 있다.

new HashMap<>(100)

이 값은 저장 개수 보장이 아니라 capacity 계산의 시작점이다. 실제 resize 발생 시점은 내부 capacity와 load factor에 따라 달라진다.

 

결과

1. 저장 개수를 대략 예상할 수 있다면 초기 용량을 미리 준다.
2. 계산은 보통 expectedSize / 0.75 기준으로 잡는다.
3. 이렇게 하면 resize, 재배치, GC 부담을 줄일 수 있다.

예를 들어 대량 데이터를 한 번에 담는 코드라면 아래처럼 시작하는 편이 더 낫다.

val expectedSize = 1000
val map = HashMap<String, Int>((expectedSize / 0.75f).toInt() + 1)

 

 

정리

HashMap의 초기 용량 지정은 사소한 옵션처럼 보이지만, 내부 동작을 이해하면 꽤 실용적인 최적화 포인트다.

특히 resize는 단순한 배열 확장이 아니라,

• 새 배열 할당
• 기존 엔트리 O(n) 재배치
• 이전 배열 GC 대상화

까지 함께 일어나는 작업이다. 그래서 예상 데이터 수를 알고 있다면 초기 용량을 적절히 지정하는 것이 더 효율적이다. 정리하자면 HashMap 초기 용량 튜닝의 핵심은 “정확한 숫자를 맞추는 것”보다 “불필요한 resize를 피할 정도로 합리적으로 예측하는 것”에 있다.

 

출처

HashMap 구현코드 - https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/HashMap.java