[Java] HashMap의 데이터 관리?! Linked List와 Red-Black Tree의 전환 과정!

Java

 제 블로그는 대체로 즉흥적으로 글 쓰는 용도라 이전 포스트에 이어서 시리즈가 연재가 되지 않는다 싶으면 다른 관심사가 생긴 것입니다. 그래도 이렇게 지나가면서 이어나가니까 기다려주시면 감사하겠습니다. 꼼꼼하게 준비하려다 보니 늦어질 때도 있어요.

 

2024.09.14 - [Study/Java] - [Java] HashSet과 HashMap 성능 차이

[Java] HashSet과 HashMap 성능 차이

 

예전 게시글에서 HashSet과 HashMap의 성능 차이에 대해서 알아보았습니다. 이번에는 HashMap의 내부 구조를 조금 더 깊이 들어가서 탐구해 보려고 합니다. HashMap이 사용하는 배열, 연결 리스트(Linked List), 그리고 레드-블랙 트리(Red-Black Tree)의 결합이 성능에 미치는 영향을 중점적으로 다뤄보겠습니다.

 

---

HashMap의 내부 구조

1. 배열(Array)

 HashMap의 기본 구조는 해시 버킷(hash bucket)으로 구성된 배열입니다. 해시 함수를 통해 각 키의 해시 값을 계산하고, 이를 기반으로 버킷의 위치를 결정합니다. 이때, 해시 값 충돌을 최소화하기 위해 배열의 크기를 2의 제곱수로 설정합니다.

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 초기 크기: 16
static final int MAXIMUM_CAPACITY = 1 << 30;       // 최대 크기

배열을 물건을 담는 “양동이(table)“로 생각해 봅시다. 각 양동이는 특정 해시 값을 가진 데이터를 담습니다. 만약 양동이 안에 데이터가 너무 많아지면(충돌 발생), 이를 해결하기 위해 연결 리스트 또는 트리 구조를 사용합니다.

 

2. 연결리스트(Linked List)

 해시 충돌이 발생하면, 동일한 해시 값을 가진 데이터들이 같은 버킷에 저장됩니다. 이 경우, HashMap은 데이터를 연결 리스트(Node 구조)로 관리합니다.

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;
    }
}

여기서 코드를 보면 next라는 인스턴스 변수가 있는데 충돌이 났을 때? 요기에 쭉쭉 이어주는 겁니다. 연결 리스트는 충돌이 적을 때 적합하지만 충돌이 많아지면 성능이 저하됩니다. 최악의 경우 O(n)의 탐색 시간이 소요될 수 있습니다.

 

table

버킷은 table 배열의 요소이고.. 이 요소가 연결 리스트의 첫 번째 노드를 참조해요.

 

3. 레드-블랙 트리(Red-Black Tree)

 연결 리스트의 길이가 일정 임계치(TREEIFY_THRESHOLD - 기본 값 : 8)에 도달하면, 성능을 개선하기 위해 연결 리스트가 레드-블랙 트리로 변환됩니다. 레드-블랙 트리가 되기 위한 조건은 다음과 같아요.

1. 연결 리스트의 길이가 8 이상일 경우 변환.
2. 버킷 크기가 충분히 클 때만 변환. (최소 크기: 64)
  (배열 크기가 작을 경우, 충돌을 줄이기 위해 우선 resize()를 실행합니다.)

 

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent; // 부모 노드
    TreeNode<K,V> left;   // 왼쪽 자식
    TreeNode<K,V> right;  // 오른쪽 자식
    boolean red;          // 노드 색상
}

이제 Node의 형태도 바뀌게 되죠. TreeNode 클래스가 있습니다!

 

 

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize(); // << 요기서 버킷 크기 증가
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null); // 트리 구조로 변환하는 작업
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

레드-블랙 트리는 O(log n)의 탐색 성능을 보장하므로, 이러면 연결 리스트를 사용할 때 발생할 수 있는 성능 문제를 완화할 수 있겠죠? 하지만 초기 트리 생성에 비용이 소요되고, 데이터가 적을 경우에는 연결 리스트보다 효율이 떨어질 수도 있습니다.

 

백문불여일견. 버킷에 저장된 데이터의 상태를 확인해 보겠습니다. 해시 값을 일부러 고정시켜 충돌을 발생시켰죠.

import java.lang.reflect.Field;
import java.util.HashMap;

public class EfficiencyTest {
    // 동일한 해시 값을 가지는 커스텀 키 객체
    static class CustomKey {
        private final int value;

        public CustomKey(int value) {
            this.value = value;
        }

        @Override
        public int hashCode() {
            return 1; // 동일한 해시 값
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;
            return value == ((CustomKey) obj).value;
        }
    }

    static class CustomKey2 {
        private final int value;

        public CustomKey2(int value) {
            this.value = value;
        }

        @Override
        public int hashCode() {
            return 2; // 동일한 해시 값
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;
            return value == ((CustomKey2) obj).value;
        }
    }

    public static void main(String[] args) throws Exception {
        // 1. LinkedList 상태 확인
        HashMap<Object, String> map = new HashMap<>(64);
        for (int i = 0; i < 5; i++) {
            map.put(new CustomKey(i), "LinkedList_value" + i);
        }

        // 2. TreeNode 상태 확인
        for (int i = 0; i < 9; i++) {
            map.put(new CustomKey2(i), "TreeNode_value" + i);
        }
        printBucketState(map);
    }

    // HashMap 버킷 상태 출력
    private static void printBucketState(HashMap<Object, String> map) throws Exception {
        Field tableField = HashMap.class.getDeclaredField("table");
        tableField.setAccessible(true);
        Object[] table = (Object[]) tableField.get(map);

        for (int i = 0; i < table.length; i++) {
            if (table[i] != null) {
                System.out.println("Bucket " + i + ": " + table[i].getClass().getName());
            } else {
                System.out.println("Bucket " + i + ": null");
            }
        }
    }
}

 

Bucket 0: null
### LinkedList 상태 ###
Bucket 1: java.util.HashMap$Node
### TreeNode 상태 ###
Bucket 2: java.util.HashMap$TreeNode

뭐, 이런 식으로 버킷마다 서로 다른 구조를 병행하면서 사용할 수 있습니다. 융통성 있는 HashMap. 해시 충돌이 없을 때는 O(1)의 성능이기도 하고.. 정말 맘에 드는 자료구조입니다. 현재 이 포스트는 java 1.8을 기준으로 설명했습니다. 이후 Java 21에서도 TREEIFY_THRESHOLD와 같은 기본값은 유지되고 있긴 하지만 전체적인 흐름을 파악하는 정도로만 가져갑시다!