HashMap의 동작 원리 — put 하면 내부에서 무슨 일이 벌어질까

map.put("name", "sim") 한 줄을 호출하면, 내부에서는 해시 계산 -> 비트 연산 -> 버킷 탐색 -> 충돌 처리까지 여러 단계가 실행됩니다. 이 과정을 이해해야 HashMap을 제대로 쓸 수 있습니다.

HashMap은 key-value 쌍을 해시 함수 기반으로 O(1) 에 저장하고 조회하는 자료구조입니다. 하지만 "O(1)"이라는 숫자 뒤에는 해싱, 충돌 해결, 리사이징이라는 복잡한 메커니즘이 숨어 있습니다.

개념 정의

HashMap 은 key의 해시값을 이용해 버킷(배열 인덱스)을 결정하고, 해당 버킷에 key-value 쌍을 저장하는 해시 테이블 기반 자료구조입니다. 평균 O(1)의 삽입/조회 성능을 제공하지만, 해시 충돌이 발생하면 성능이 저하될 수 있습니다.

핵심 구조

HashMap은 내부적으로 배열(bucket array) 을 가지고 있습니다. 이 배열의 각 칸을 "버킷"이라고 부릅니다.

버킷 배열 (초기 크기: 16)
[0] → null
[1] → null
[2] → Node(key="name", value="sim", next=null)
[3] → null
[4] → Node(key="age", value=28, next=null)
...
[15] → null

key를 넣으면 해시 함수로 버킷 인덱스를 계산하고, 해당 버킷에 Node를 저장합니다.

put() 호출 시 동작 원리

map.put("name", "sim")을 호출하면 3단계를 거칩니다.

1단계: 해시 계산

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

key.hashCode()로 해시값을 구한 뒤, 상위 16비트와 하위 16비트를 XOR 합니다. 버킷 배열의 크기가 작을 때(16, 32 등) 하위 비트만으로 인덱스를 결정하면 상위 비트의 차이가 무시되어 충돌이 잦아지기 때문에, XOR로 상위 비트의 정보를 하위 비트에 반영하는 것입니다.

2단계: 버킷 인덱스 결정

int index = (n - 1) & hash;  // n은 배열 크기

hash % n 대신 비트 AND 연산을 사용합니다. HashMap의 배열 크기는 **항상 2의 거듭제곱 **(16, 32, 64, ...)으로 유지되므로, (n - 1) & hash는 hash % n과 동일한 결과를 주면서 연산 속도가 더 빠릅니다. 배열 크기를 2의 거듭제곱으로 강제하는 이유가 바로 이 비트 연산 최적화입니다.

3단계: 버킷에 저장

해당 버킷이 비어있으면 새 Node를 생성해서 넣습니다. 이미 다른 Node가 있으면 ** 해시 충돌 **이 발생한 것이고, 충돌 해결 로직으로 넘어갑니다.

해시 충돌 해결

서로 다른 key가 같은 버킷 인덱스로 계산되면 충돌이 발생합니다. Java HashMap은 두 가지 방식으로 처리합니다.

Separate Chaining (체이닝)

같은 버킷의 노드들을 ** 연결 리스트 **로 이어붙입니다.

[2] → Node("name", "sim") → Node("email", "test@test.com") → null

• put() 시: 같은 버킷의 노드를 순회하며 equals()로 key 비교. 같은 key면 값 갱신, 없으면 리스트 끝에 추가.
• get() 시: 버킷을 찾고, 리스트를 순회하면서 equals()로 key를 비교.

Treeify: 리스트 -> Red-Black Tree

Java 8부터, 하나의 버킷에 ** 노드가 8개 이상** 쌓이면 연결 리스트를 Red-Black Tree 로 변환합니다. 이렇게 하면 해당 버킷의 탐색 성능이 O(n)에서 O(log n)으로 개선됩니다.

[2] → LinkedList (노드 7개 이하)     → O(n) 탐색
[2] → Red-Black Tree (노드 8개 이상) → O(log n) 탐색

임계값이 8인 이유는, 잘 분포된 해시 함수에서 한 버킷에 8개 이상 쌓일 확률이 약 0.00000006으로 극히 낮기 때문입니다. 이 정도면 트리 변환의 오버헤드를 감수할 만합니다.

노드가 6개 이하 로 줄어들면 다시 리스트로 복원됩니다. 8과 6 사이에 차이를 둔 것은 경계값에서 반복적인 변환/역변환을 방지하기 위함입니다.

리사이징 (Rehash)

버킷이 많이 차면 충돌 확률이 높아지고 성능이 떨어집니다. HashMap은 load factor 를 기준으로 배열을 확장합니다.

static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int DEFAULT_INITIAL_CAPACITY = 16;
// threshold = 16 x 0.75 = 12 → 요소가 12개를 넘으면 리사이징

리사이징 과정은 다음과 같습니다.

1. 기존 배열의 2배 크기로 새 배열을 생성합니다.
2. 모든 노드의 버킷 인덱스를 ** 새 배열 크기 기준으로 재계산 **하여 재배치합니다(rehash).
3. 기존 배열을 폐기합니다.

이 과정이 O(n)이므로, 대량 데이터를 넣을 것을 알고 있다면 초기 용량을 지정하는 것이 좋습니다.

// 1000개를 넣을 예정이면: 1000 / 0.75 ≈ 1334
Map<String, String> map = new HashMap<>(1400);

주의할 점

equals()만 오버라이드하고 hashCode()를 빠뜨리면

HashMap은 key를 저장할 때 hashCode()로 버킷을 결정하고, 조회할 때 equals()로 key를 비교합니다. 이 두 메서드의 계약은 명확합니다.

1. equals()가 true면 hashCode()도 반드시 같아야 합니다 (필수)
2. hashCode()가 같다고 equals()가 true일 필요는 없습니다 (충돌 허용)

다음 코드에서 문제가 발생합니다.

class Person {
    String name;
    @Override
    public boolean equals(Object o) {
        return this.name.equals(((Person) o).name);
    }
    // hashCode()를 오버라이드하지 않음!
}

Person p1 = new Person("sim");
Person p2 = new Person("sim");
map.put(p1, "hello");
map.get(p2);  // null이 반환될 수 있음

p1과 p2는 equals()로는 같지만, hashCode()가 다르면(Object 기본 구현은 메모리 주소 기반) ** 다른 버킷에 저장 **됩니다. get(p2)는 p2의 hashCode에 해당하는 버킷을 찾아가므로, p1이 저장된 버킷에 도달하지 못합니다.

멀티스레드 환경에서 HashMap 사용

HashMap은 thread-safe하지 않습니다. 여러 스레드가 동시에 put()을 호출하면 데이터가 유실되거나, Java 7 이전에는 리사이징 중 연결 리스트가 순환 참조를 형성하여 ** 무한 루프 **에 빠지기도 했습니다.

load factor와 초기 용량 미지정

기본값(초기 16, load factor 0.75)은 소규모 데이터에 적합합니다. 수만 건 이상의 데이터를 넣으면서 초기 용량을 지정하지 않으면, 16 -> 32 -> 64 -> 128 -> ... 으로 반복 리사이징이 발생하여 불필요한 O(n) 복사가 여러 번 일어납니다.

정리