HashMap 내부 구조와 작동 원리

  1. 데이터 구조

1.7 버전

배열과 연결 리스트의 조합으로, 키-값 쌍은 Entry 내부 클래스 배열에 저장됩니다. 키로부터 계산된 해시값이 배열의 인덱스가 됩니다. 이를 버킷 배열이라고 부르며, 해시 충돌이 발생할 경우 Entry 클래스의 내부 멤버 변수 Entry<k,v> next;를 통해 연결 리스트를 형성합니다. 해시값이 동일한 요소들은 머리 삽입법(head insertion)을 통해 연결 리스트에 추가되는데, 이를 체이닝(Chaining) 방식이라고 합니다.

1.7 버전의 주요 문제점:

  • 머리 삽입법은 다중 스레드 환경에서 확장 시 두 스레드 간에 요소들이 서로를 가리키는 순환 연결 리스트가 발생할 수 있으며, 이로 인해 get() 실행 시 무한 루프에 빠져 CPU 자원을 소모하게 됩니다
  • 연결 리스트의 검색 시간 복잡도는 O(n)으로 비효율적입니다

1.8 버전

  • 배열 + 연결 리스트 + 레드-블랙 트리: 연결 리스트의 노드 수가 8(트리화 임계값)을 초과하고 배열의 길이가 최소 트리화 용량 64를 초과할 경우, 연결 리스트는 레드-블랙 트리로 변환되어 조회 시간 복잡도를 O(logN) 수준으로 유지합니다
  • 꼬리 삽입법(tail insertion)을 채택하여 확장 시 발생할 수 있는 무한 루프 문제를 방지합니다
  • Entry를 상속받는 Node를 키-값 쌍 저장을 위한 내부 클래스로 사용합니다

2.HashMap(1.8) 상세 분석

2.1 상속/구현 관계

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {}

2.2 정적 변수

/**
 * 기본 초기 용량 - 반드시 2의 거듭제곱이어야 합니다.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16과 동일
static final int MAXIMUM_CAPACITY = 1 << 30; // 최대 용량
  • 기본 버킷 배열 초기 용량: 16(1 << 4, 반드시 (2^{n}) 형식), 최대 (2^{30})
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 확장 로드 팩터
static final int TREEIFY_THRESHOLD = 8; // 트리화 임계값
static final int UNTREEIFY_THRESHOLD = 6; // 연결 리스트화 임계값
static final int MIN_TREEIFY_CAPACITY = 64; // 최소 트리화 용량

2.3 데이터 저장 구조

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        ...
}
transient Node<K,V>[] table;

내부 정적 클래스 Node는 Entry를 상속받아 키-값 쌍, 해시값, 다음 노드에 대한 참조를 저장합니다. 이 노드들이 모여 table 배열을 형성합니다.

2.4 해시값 계산

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 비트 AND 연산
i = (n-1) & hash // 더 빠른 나머지 연산

HashMap은 Null 저장을 허용하며, 이를 강제로 인덱스 0의 버킷에 위치시킵니다. key가 null이 아닐 경우, 먼저 정상적으로 hashCode를 호출하여 int 타입(4바이트, 32비트) 값을 얻습니다. 그 다음 비트 오른쪽 시프트 연산 >>를 사용해 상위 32비트를 하위 16비트로 이동시키고, 자기 자신과 ^ 비트 XOR 연산을 수행하여 해시값을 얻습니다. 최종적으로 이 해시값과 (n-1)을 비트 AND 연산하여 배열의 최종 인덱스 위치를 결정합니다.

& AND 연산: 두 비트가 모두 1일 때 결과가 1이 됩니다 ^ XOR 연산: 두 비트가 같으면 0, 다르면 1이 됩니다

위 처리 방식은 해시 함수(Hash Function) 또는 **분산 함수(Distribution Function)**라고도 불리며, 계산된 해시값을 더 균일하게 만들어 무작위성을 증가시키고 해시 충돌의 확률을 낮추는 것을 목표로 합니다. 구체적으로 설명하면, 32비트 해시코드를 15=16-1과 직접 비트 AND 연산할 경우 해시값의 상위 비트들이 모두 버려져 0이 되어 해시 충돌이 심각해질 수 있습니다. 그러나 위 해시 함수 처리를 통해 비트 시프트를 통해 상위 절반과 하위 절반을 XOR 연산으로 혼합하면 하위 비트에 상위 비트의 차이 특성이 혼입되어 하위 비트의 무작위성이 증가합니다. 이를 통해 나중에 계산되는 i 인덱스가 더 균일하게 분포하게 됩니다. 다른 표현으로 요약하면:

일부 데이터의 해시값 차이가 주로 상위 비트에 존재하는 반면, HashMap의 해시 주소 지정 시 용량 이상의 상위 비트는 무시되기 때문에, 해시 처리를 통해 이러한 경우의 해시 충돌을 효과적으로 방지할 수 있습니다

여기에는 숨겨진 문제가 있는데, 왜 n이 2의 거듭제곱이어야 하는지입니다. (2^{n}-1)는 이진수로 표현 시 첫 번째 비트 1부터 모든 비트가 1로 채워져 있어 0 비트가 없습니다. 이와 AND 연산을 수행하면 각 비트 위치에 두 가지 가능성이 생깁니다. 만약 다른 값이라면 0 비트가 많아져 인덱스 i의 범위가 크게 제한됩니다. 따라서 목적은 버킷 배열의 분포를 더 균일하게 만드는 것입니다.

2.5 초기화 - 생성자

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

초기 용량과 로드 팩터가 지정되지 않은 경우 기본값은 로드 팩터 0.75, 용량=16입니다. 이때는 저장 컨테이너 table의 초기화가 즉시 수행되지 않고, 첫 번째 put 연산 시에 이루어집니다. 이를 지연 초기화(Lazy Initialization)라고 합니다. table 초기화는 resize() 메소드를 사용하여 길이 16의 배열로 초기화됩니다. 특정 용량이 지정된 경우, tableSizeFor()를 호출하여 지정된 값보다 큰 최소 (2^{n}) 값으로 실제 용량이 설정됩니다.

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

2.6 확장(Resize)

확장은 초기화와 용량 확장 두 가지 기능을 모두 수행합니다(본질적으로 동일한 작업이며, 초기화도 0에서 16으로 확장하는 것과 같습니다). 주요 매개변수는 로드 팩터로, 현재 버킷 배열 요소가 용량 * 로드 팩터를 초과하면 용량이 두 배로 확장됩니다.

확장 후, 기존 배열의 요소들을 새로운 인덱스로 재계산하여 배치합니다. 새로운 인덱스는 기존 인덱스 oldIndex이거나 oldIndex + oldCapacity(기존 배열 용량)일 수 있습니다. 이는 다음과 같이 이해할 수 있습니다:

확장 과정에서 기존 인덱스 2에 있던 요소들은 원래 위치에 머무르거나 인덱스 18 위치로 이동합니다. 이유를 생각해보면, 예를 들어 어떤 해시값의 하위 5비트가 00010이라고 가정해봅시다(이 경우 하위 5비트만 중요하며, 해시 최적화 알고리즘에 대해 모르는 독자는 이전 글을 참조하시기 바랍니다).

0 0010 (해시값)

0 1111 (n - 1 = 16 -1 = 15)

0 0010

이는 확장 전(초기 용량 16)에서 계산된 인덱스가 2임을 의미합니다. 이때 용량이 확장되면 32가 되고, 재해시(rehash) 결과는 다음과 같습니다:

0 0010 (해시값)

1 1111 (n - 1 = 32 -1 = 31)

0 0010

재해시 결과, 인덱스는 여전히 2로 변하지 않습니다.

그렇다면 만약 해시값의 하위 5비트가 10010이라면 어떻게 될까요?

1 0010 (해시값)

0 1111 (n - 1 = 16 -1 = 15)

0 0010

즉, 10010 & 15 = 2이므로 이 경우 확장 후 재해시는 다음과 같습니다:

1 0010 (해시값)

1 1111 (n - 1 = 32 -1 = 31)

1 0010

1 0010의 십진수는 18입니다. 여기서 18이 특별한 의미를 가지는지 생각해봅시다.

18 = 2 + 16 = 2 + oldCap 임을 알 수 있습니다. 즉, 재해시 후 요소들은 원래 위치에 머무르거나 원래 인덱스 + 원래 배열 길이 위치로 이동합니다. 이는 초기화 시 (16 - 1)과 AND 연산을 할 때 하위 4비트의 해시값만 의미가 있지만, 용량이 32로 확장되면 (32 - 1)과 AND 연산을 할 때 하위 5비트도 연산에 참여하게 됩니다. 따라서 하위 5비트 값이 재해시 후 새 인덱스를 결정합니다. 하위 5비트가 0이면 인덱스 값은 변하지 않고, 1이면 인덱스가 변하며 기존 값에 2의 4제곱인 16이 더해집니다.

이와 같은 방식으로 32에서 64로 확장될 경우, 하위 6비트가 인덱스 변화를 결정하며, 변화할 경우 기존 값에 2의 5제곱인 32가 더해집니다.

요약: resize 메소드에서 배열을 재해시할 때, 요소들은 원래 위치에 머무르거나 oldIndex + oldCap 위치로 이동합니다.

2.7 Put 메소드

  1. 초기화 여부를 확인하고, 초기화되지 않았다면 resize()를 먼저 호출합니다;
  2. key에 대한 해시코드를 계산하고 인덱스를 구합니다;
  3. 해시 충돌이 없으면 버킷에 추가하고, 충돌이 있으면 연결 리스트의 꼬리에 추가합니다;
  4. 연결 리스트의 길이가 트리화 임계값 8을 초과하고 배열의 길이가 64를 초과하면 연결 리스트를 레드-블랙 트리로 변환합니다. 반대로 연결 리스트의 길이가 6 미만이면 레드-블랙 트리를 다시 연결 리스트로 변환합니다;
  5. 노드의 key가 이미 존재하면 value를 업데이트합니다;
  6. 용량이 64 미만이고 총 용량의 0.75를 초과하면 용량을 확장합니다.

2.8 Get 메소드

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

    /**
     * Map.get 및 관련 메소드 구현
     *
     * @param hash key의 해시값
     * @param key 키
     * @return 노드, 없으면 null
     */
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // 첫 번째 노드는 항상 확인
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).findTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

key를 사용하여 앞서 설명한 해시 함수 computeHash로 해시값을 계산하고, getNode를 통해 노드를 가져옵니다. 노드가 null이면 null을 반환하고, 그렇지 않으면 노드의 값을 반환합니다.

getNode() 메소드에서 (n-1) & hash로 인덱스, 즉 버킷 위치를 얻습니다. 그 다음 첫 번째 노드가 비어있는지와 key가 일치하는지 확인합니다. 첫 번째 노드가 아닌 경우, 연결 리스트를 순회하며 equals 메소드로 key가 일치하는지 확인합니다. 레드-블랙 트리인 경우 findTreeNode를 호출하여 검색합니다.

객체를 key로 사용할 경우, key의 hashcode와 equals 메소드를 오버라이드하는 것이 좋습니다.

추가 정보:

HashMap 1.8은 꼬리 삽입법을 사용하여 무한 루프 문제를 방지했지만, 여전히 스레드에 안전하지 않습니다. 동시성 환경에서는 ConcurrentHashMap이나 HashTable을 사용해야 합니다.

오류가 있다면 토론을 통해 지적해주시기 바랍니다.

참고 자료

  1. HashMap 내부 구조 분석
  2. HashMap get 메소드 동작 원리
  3. HashMap 작동 방식 심층 분석
  4. HashMap put 및 get 메소드 구현 원리

태그: 자바 HashMap 데이터 구조 해시 테이블 레드-블랙 트리

6월 3일 17:20에 게시됨

인기 태그

©2026 괴물 클럽