[자바] HashMap 파헤치기: put() 메소드는 어떻게 동작할까?

들어가며

이번 글에서는 HashMap의 put() 메소드의 내부 구현을 단계별로 살펴보며 HashMap이 어떻게 동작하는지 알아보겠습니다.

HashMap의 기본 구조와 핵심 용어

HashMap 클래스의 주석에는 성능에 영향을 미치는 두 가지 중요한 매개변수가 언급됩니다: 바로 초기 용량(initial capacity)과 로드 팩터(load factor)입니다.

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

 

이해를 돕기 위해 주요 용어를 정리해 보겠습니다.

• 버킷 (Bucket)
  • 데이터를 저장하는 개별 공간을 의미합니다.
  • HashMap 내부적으로는 Node[] table 배열의 각 칸(인덱스)이 하나의 버킷에 해당합니다.
  • HashMap의 기본 버킷 개수는 16개입니다.
• 로드 팩터 (Load Factor)
  • 전체 버킷 중 얼마나 많은 버킷이 채워졌을 때 용량 확장이 일어날지를 결정하는 비율입니다.
  • (데이터의 개수) / (버킷의 개수) 가 로드 팩터를 초과하면, 버킷의 개수가 약 2배로 늘어나고, 기존 데이터들을 새 버킷 구성에 맞게 재배치하는 리해시(rehash) 과정이 발생합니다.
  • 기본 로드 팩터 값은 0.75입니다.

예를 들어, HashMap을 기본 설정으로 생성하면 버킷은 16개, 로드 팩터는 0.75입니다. 이때 임계값(threshold)은 16 * 0.75 = 12가 됩니다. 이는 HashMap에 12개의 데이터(Key-Value 쌍)가 저장된 상태에서 13번째 데이터가 삽입될 때, 버킷의 수가 32개로 확장되고 리해시가 일어난다는 의미입니다.

(이미지: 해시 테이블의 기본 구조. 각 버킷은 비어있거나, 하나의 노드를 가리키거나, 여러 노드가 연결된 리스트/트리를 가리킬 수 있습니다.)

해시 테이블은 서로 다른 키가 동일한 해시 값을 가져 같은 버킷으로 충돌(Hash Collision)하는 상황에 대한 대비책이 필요합니다. HashMap은 이러한 충돌을 해결하기 위해 체이닝(Chaining) 기법을 사용합니다. 자바 8부터는 여기에 더해 성능 향상을 위한 추가적인 최적화가 도입되었습니다.

This map usually acts as a binned (bucketed) hash table, but when bins get too large, they are transformed into bins of TreeNodes, each structured similarly to those in java.util.TreeMap. Most methods try to use normal bins, but relay to TreeNode methods when applicable (simply by checking instanceof a node). Bins of TreeNodes may be traversed and used like any others, but additionally support faster lookup when overpopulated. However, since the vast majority of bins in normal use are not overpopulated, checking for existence of tree bins may be delayed in the course of table methods.

 

기본적으로는 각 버킷에서 충돌이 발생하면 데이터를 LinkedList 형태로 연결하여 저장합니다. 하지만 하나의 버킷에 데이터가 과도하게 많아지면 LinkedList의 탐색 성능이 저하(O(N))됩니다. 이를 방지하기 위해 특정 조건이 충족되면 해당 버킷의 자료구조를 TreeNode (Red-Black Tree) 형태로 변경합니다.

• static final int MIN_TREEIFY_CAPACITY = 64;
• static final int TREEIFY_THRESHOLD = 8;

위 상수들이 그 조건입니다.

1. HashMap의 전체 버킷 용량(table.length)이 MIN_TREEIFY_CAPACITY (기본값 64) 이상이고,
2. 하나의 버킷에 연결된 노드의 수가 TREEIFY_THRESHOLD (기본값 8) 이상이면,
   해당 버킷의 LinkedList는 TreeNode 형태로 변환됩니다. 이를 통해 해당 버킷에서의 데이터 탐색 시간을 O(logN)으로 개선할 수 있습니다.

Node: 데이터 저장의 기본 단위

HashMap은 Key-Value 쌍을 내부적으로 Node라는 정적 중첩 클래스(static nested class)를 통해 관리합니다.

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // 다음 노드를 가리키는 참조

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    // ... (getKey, getValue, setValue, equals, hashCode, toString 메서드들)
}

여기서 주목할 점은 Node<K,V> next; 필드입니다. 이 필드는 다음 Node 객체를 가리키는 포인터 역할을 하며, 이를 통해 Node들은 LinkedList 구조를 형성할 수 있습니다.

HashMap은 실제로 이러한 Node 객체들을 저장하는 배열 table을 핵심 데이터 구조로 사용합니다.

transient Node<K,V>[] table;

table 배열의 각 요소(버킷)는 단일 Node를 가리키거나, 충돌 발생 시 Node들이 연결된 LinkedList의 첫 번째 노드(또는 TreeNode)를 가리킵니다.

map.put(K key, V value) 메소드 심층 분석

이제 HashMap에 데이터를 저장하는 put() 메소드의 내부를 살펴보겠습니다.

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

put() 메소드는 내부적으로 hash(key)를 통해 키의 해시 값을 계산한 뒤, 이 해시 값과 함께 key, value 등의 인자를 putVal() 메소드에 전달하여 실제 데이터 저장 로직을 수행합니다.

putVal() 메소드의 코드는 다소 길지만, 주석을 기준으로 주요 로직을 단계별로 나누어 살펴보겠습니다.

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i; // 변수 선언

    // First: 테이블 초기화
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length; // 테이블이 비어있으면 resize()를 통해 초기화

    // Second: 삽입될 버킷이 비어있는 경우
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null); // 새 노드를 생성하여 해당 버킷에 바로 삽입
    else { // 삽입될 버킷이 비어있지 않은 경우 (해시 충돌 발생)
        Node<K,V> e; K k;

        // Third: 현재 버킷의 첫 번째 노드가 삽입하려는 키와 동일한 경우
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // 기존 노드를 e에 할당 (나중에 값 업데이트용)

        // Fourth: 버킷이 TreeNode(트리) 형태로 되어 있는 경우
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 트리에 값 삽입

        // Fifth: 버킷이 LinkedList 형태로 되어 있는 경우
        else {
            for (int binCount = 0; ; ++binCount) { // LinkedList 순회
                // Sixth: LinkedList의 끝에 도달 (삽입하려는 키가 버킷에 없는 경우)
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null); // 새 노드를 LinkedList의 마지막에 추가
                    if (binCount >= TREEIFY_THRESHOLD - 1) // TREEIFY_THRESHOLD 확인 (0부터 시작하므로 -1)
                        treeifyBin(tab, hash); // 임계값 초과 시 트리로 변환
                    break; // 루프 종료
                }
                // Seventh: LinkedList 내에서 삽입하려는 키와 동일한 키를 찾은 경우
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break; // 루프 종료 (e는 기존 노드를 가리킴)
                p = e; // 다음 노드로 이동
            }
        }

        // Eighth: 기존 키에 대한 매핑이 존재했던 경우 (e가 null이 아님)
        if (e != null) { // 기존 노드(e)의 값을 업데이트
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null) // onlyIfAbsent가 false이거나 기존 값이 null이면
                e.value = value; // 새 값으로 덮어쓰기
            afterNodeAccess(e); // 접근 콜백 (LinkedHashMap 등에서 사용)
            return oldValue; // 이전 값 반환
        }
    }

    ++modCount; // Map의 구조적 변경 횟수 증가
    if (++size > threshold) // 전체 요소 개수가 임계값을 초과하면
        resize(); // 테이블 크기 확장 (리해시)
    afterNodeInsertion(evict); // 삽입 콜백 (LinkedHashMap 등에서 사용)
    return null; // 새로운 키-값 쌍이 삽입된 경우 null 반환
}

각 주석 부분을 좀 더 자세히 풀어보겠습니다.

 

먼저 //First 아래에 있는 2줄을 보자.

        //First
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;

HashMap 객체가 생성되고 처음 put 이 일어날때 실행된다.
HashMap이 막 선언된 경우 table 배열이 null 상태이므로 table 배열을 resize() 를 통해 배열을 생성해준다.

 

//Second 아래에 2줄을 보자.

    //Second    
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

put 을 진행할 bucket이 비어있었을 경우 이 if문을 실행하게 된다. 비어있는 배열에 새로운 Node 를 생성해 넣어주게 된다.

그렇다면, 그 아래 else 문에는 해당 bucket 이 비어있지 않은 경우 실행되는 코드들이다.

 

//Third 아래에 있는 코드

         //Third
         if (p.hash == hash &&
           ((k = p.key) == key || (key != null && key.equals(k))))
             e = p;

p 는 해당 버킷 제일 앞에있는 Node 라고 보면 된다.
이번에 put 한 key가 존재하고 있고, 그게 버킷의 맨 앞단에 있다면 해당코드가 실행되게 된다.
Node e = p 를 해준 이유는 조금 뒤에 나온다.

 

//Fourth 아래에 있는 코드

        //Fourth
        else if (p instanceof TreeNode) 
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

만약 해당 버킷이 collision 이 많아져서 tree 형태로 바뀐상황이라면 위의 코드가 실행된다.

            //Fifth
            else {
                for (int binCount = 0; ; ++binCount) {

                    //Sixth
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }

                    //Seventh
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }

//Fifth 에 들어오는 경우는 이번에 put 한 key가 속한 bucket이 비어있지 않고, 버킷의 첫번째 key 가 이번에 put 한 key와 다를 때의 경우다.

 

//Sixth 아래에는 해당 버킷에 이번에 put한 key가 없는 경우에 실행된다.
e = p.next 를 통해 링크드리스트의 다음 노드들을 탐색하면서 끝까지 탐색했을때까지 이번에 put한 key 가 없을 경우 제일 뒤에 이번에 추가한 Node를 달아주게 된다.

    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);

이 코드에서 보이듯이 해당 버킷에서 TREEIFY_THRESHOLD 수 보다 더 많은 Node 가 존재할경우 해당 버킷을 링크드리스트에서 트리형태로 바꿔주게 된다.

 

//Seventh 아래에는 해당 버킷에 이번에 put한 key가 있는 경우 실행된다.

 

//Eighth 아래 코드를 보자.

            //Eighth
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }

원래 버킷에 key가 존재했던 경우에 동작하는 코드이다. 이전 코드를 보면 기존에 존재하던 Node 를 e 에 담아두었었다. Node e 에 value 를 이번에 입력한 value로 업데이트 해주게된다.

if (++size > threshold)
            resize();

마지막으로 위의 코드를 보자. int threshold = 현재 capacity * LOAD_FACTOR 해준 값이 들어있다. 새로운 버킷이 사용되면 로드팩터를 고려해서 캐퍼시티를 늘릴지 말지를 결정 해주는 코드이다.

마치며

지금까지 HashMap의 put() 메소드가 내부적으로 어떻게 동작하는지 단계별로 살펴보았습니다. 테이블 초기화, 해시 충돌 처리, LinkedList와 TreeNode를 활용한 유연한 자료구조 변화, 그리고 동적인 테이블 크기 조절까지, HashMap은 효율적인 데이터 저장을 위해 정교하게 설계되어 있음을 알 수 있습니다.

 

이러한 내부 동작 원리를 이해하면 HashMap을 더욱 효과적으로 사용하고, 초기 용량이나 로드 팩터 설정 등을 통해 잠재적인 성능 문제를 예측하고 최적화하는 데 큰 도움이 될 것입니다.