HashMap 상세 분석

HashMap은 Java에서 가장 널리 사용되는 키-값 컨테이너 중 하나입니다. JDK 8 이후 내부 구조가 "배열 + 연결 리스트 + 레드-블랙 트리"의 조합으로 바뀌었으며, Java 컬렉션 프레임워크의 핵심 컴포넌트입니다.

핵심 필드는 다음과 같이 추상화할 수 있습니다:

Java

        public class HashMap<K, V> {
    transient Node<K, V>[] table;  // 해시 버킷 배열
    transient int size;            // 키-값 쌍의 수
    int threshold;                 // 리사이즈 임계값
    final float loadFactor;        // 부하 계수
}

각 버킷에는 연결 리스트 노드 또는 레드-블랙 트리 노드가 저장됩니다:

Java

        static class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;
}

해시 버킷이란 무엇인가

table을 일렬로 나열된 슬롯으로 상상해 보세요. 각 슬롯이 하나의 "버킷"입니다.

put(key, value)를 호출하면 HashMap은:

키의 해시값을 계산합니다
해시값으로 버킷 인덱스를 구합니다
해당 버킷에 키-값 쌍을 저장합니다

버킷 인덱스 계산식은 대략:

Java

        int index = hash & (table.length - 1);

나머지 연산 대신 비트 연산을 사용합니다. 이를 위해 table.length는 항상 2의 거듭제곱이어야 합니다. HashMap의 용량이 항상 2의 거듭제곱인 이유가 바로 이것입니다.

hash() 메서드는 무엇을 하는가

HashMap은 key.hashCode()를 직접 사용하지 않고 "교란(perturbation)" 단계를 추가합니다:

Java

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

상위 16비트와 하위 16비트를 XOR하여 해시값의 상위 비트도 버킷 인덱스 계산에 참여하게 만들어 해시 충돌을 줄입니다.

이 처리를 하지 않으면 많은 상위 비트 패턴이 & (n-1)에서 버려져 충돌이 증가합니다.

해시 충돌은 어떻게 해결되는가

서로 다른 키가 같은 버킷에 매핑될 수 있습니다. 이것이 해시 충돌입니다.

HashMap은 체이닝 방식으로 해결합니다:

같은 버킷의 여러 엔트리는 연결 리스트로 연결됩니다
JDK 8 이후, 리스트 길이가 8을 초과하고 배열 길이가 64 이상이면 리스트가 레드-블랙 트리로 변환됩니다

장점:

연결 리스트는 단순하고, 충돌이 적을 때 오버헤드가 작습니다
리스트가 길어지면 조회가 O(n)이 되지만, 레드-블랙 트리는 O(log n)으로 줄일 수 있습니다

레드-블랙 트리는 노드 수가 <= 6이 되면 연결 리스트로 되돌아갑니다.

put은 어떻게 동작하는가

map.put(key, value)의 대략적인 흐름:

Java

        public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

putVal 내부 로직 개요:

table이 비어 있으면 리사이즈로 초기화
버킷 인덱스 계산 i = (n-1) & hash
버킷이 비어 있으면 새 노드를 만들어 배치
버킷이 비어 있지 않은 경우:
- 첫 번째 노드의 키가 동일하면 값을 덮어씁니다
- 트리 노드이면 트리 삽입 로직으로 이동
- 그렇지 않으면 리스트를 순회: 일치하는 키를 찾으면 덮어쓰고, 끝까지 없으면 추가
추가 후 리스트 길이가 >= 8이 되면 레드-블랙 트리로의 변환을 검토
size가 threshold를 초과하면 리사이즈 실행

get은 어떻게 동작하는가

map.get(key)의 대략적인 흐름:

Java

        public V get(Object key) {
    Node<K, V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

getNode 로직:

해시로 버킷 인덱스를 계산
버킷의 첫 번째 노드의 키가 일치하는지 확인
일치하지 않으면 트리인지 연결 리스트인지 판단하여 각 검색 로직으로 이동

해시가 균일하게 분산되고 충돌이 적을 때 get의 시간 복잡도는 O(1)에 가깝습니다.

기본 용량과 부하 계수

Java

        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;

기본 초기 용량: 16
기본 부하 계수: 0.75

리사이즈 임계값(threshold) = 용량 × 부하 계수.

즉, size가 16 × 0.75 = 12를 초과하면 리사이즈가 발생합니다.

왜 0.75인가?

시간과 공간의 균형을 맞춘 경험적 값입니다:

너무 낮으면 (예: 0.5): 충돌은 적지만 배열 공간이 낭비됩니다
너무 높으면 (예: 1.0): 공간 효율은 높지만 충돌이 많아져 성능이 저하됩니다

0.75는 두 요소 사이의 합리적인 균형점입니다.

리사이즈는 어떻게 이루어지는가

size > threshold일 때 resize()가 실행됩니다.

리사이즈의 핵심 로직:

Java

        // 새 용량은 기존의 2배
int newCap = oldCap << 1;
int newThr = oldThr << 1;

리사이즈 후 모든 기존 노드를 새 버킷 위치에 재배치해야 합니다(rehash).

JDK 8은 rehash를 최적화했습니다:

Java

        // 노드의 새 위치는 둘 중 하나:
// 1. 기존 인덱스 그대로
// 2. 기존 인덱스 + 기존 용량
if ((e.hash & oldCap) == 0) {
    // 낮은 위치 리스트 (기존 인덱스)
} else {
    // 높은 위치 리스트 (기존 인덱스 + oldCap)
}

이 최적화는 2의 거듭제곱 용량 특성을 활용합니다. 해시값의 특정 비트 하나만 확인하면 새 버킷을 결정할 수 있어 전체 해시 매핑을 재계산할 필요가 없습니다.

null 키는 어떻게 처리되는가

HashMap은 null을 키로 허용하며, 항상 버킷 인덱스 0에 배치됩니다:

Java

        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

키가 null이면 hash는 0을 반환하고, 버킷 인덱스도 0이 됩니다.

스레드 안전성

HashMap은 스레드 안전하지 않습니다.

동시에 put을 호출하면 다음 문제가 발생할 수 있습니다:

데이터 덮어쓰기 (두 스레드가 동시에 같은 버킷에 쓰기)
JDK 7의 순환 연결 리스트로 인한 무한 루프 (JDK 8에서 수정됨)

스레드 안전한 대안:

Collections.synchronizedMap(map): 모든 작업을 synchronized로 감싸며 단순하지만 처리량이 낮습니다
ConcurrentHashMap: JDK 8은 버킷 수준에서 CAS + synchronized를 사용하여 훨씬 높은 동시성을 제공합니다

실제 개발에서 동시성 시나리오에서는 ConcurrentHashMap 사용을 권장합니다.

Fonnpo

Spring 프레임워크 완전 가이드

LinkedList 상세 분석

ArrayList 상세 분석