Java HashMap 충돌 처리 : 체이닝, LinkedList ↔ Tree 전환, 설계 원리와 내부 동작 분석

Java 컬렉션 중 하나인 HashMap은 매우 자주 쓰고 일반적으로 O(1)의 조회 성능을 기대할 수 있다.

그 이유는 내부적으로 HashTable 구조를 기반으로 key의 해시값에 따라 배열의 인덱스를 계산하여 데이터를 저장하고 조회하기 때문이다.

그런데 여기서 생기는 “해시 충돌” 문제는 어떻게 해결되고 있을까?

이 글에서는 그 과정을 개념 → 코드 → 의문점 → 추론 흐름으로 정리했다.

1. 해시 충돌(Hash Collision)이란?

서로 다른 두 객체가 같은 hashCode() 값을 갖는 경우이다.

결국 동일한 배열 인덱스에 저장되어 있음
충돌이 발생함

이렇게 동일한 버킷에 여러 객체가 들어가는 상황이 발생한다.

충돌 해결 방법

1. 체이닝(Chaining)

같은 인덱스에 여러 엔트리를 연결 리스트나 트리로 연결

2. 개방 주소법(Open Addressing)

충돌 시 다른 빈 버킷을 찾아가며 저장

Java의 HashMap은 1번 체이닝 방식을 사용한다.

2. 실제 코드를 보자 – put() 메서드

1. put() 메서드

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

hash(key) : key의 hashCode()를 변형하여 해시값 계산
putVal( ... ) : 실제 저장 로직

2. 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;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

putVal() 메서드를 보면 위처럼 되어 있다.

코드를 보면, 해시 충돌이 발생하면 LinkedList로 체이닝하여 데이터를 연결하고

이 리스트의 길이가 8 이상이 되면 해시 테이블의 크기가 64 이상일 경우에만 Red-Black Tree로 전환된다.

그리고 6 이하로 줄어들면 다시 LinkedList로 되돌리는 로직이 존재한다.

3. 의문점과 추론

왜 Java는 체이닝(Chaining) 방식을 선택했을까?

1. 구현이 간단하고 유지보수가 용이하다

체이닝은 충돌 시 해당 인덱스에 노드를 연결하면 끝이다.
개방 주소법은 선형 탐사, 이차 탐사, 이중 해싱 등 복잡한 로직을 구현해야 한다.

2. 삭제가 쉽다

체이닝은 연결된 노드만 끊으면 삭제 완료
개방 주소법은 삭제 후 빈 자리를 다시 정리하거나 삭제 마커를 둬야 한다. -> 복잡함

3. 해시 품질이 완벽하지 않아도 비교적 안정적이다

체이닝은 해시 함수의 성능이 떨어져도 치명적인 성능 저하 없이 동작한다.
개반 주소법은 해시 분포가 불균형할 경우 성능이 나빠질 수 있다.

이런 점 때문에 체이닝 방식이 Java의 HashMap에 더 적합했고

그래서 충돌 처리 방식으로 채택된 것으로 볼 수 있다.

왜 8 이상 일 때 Tree로 바꿀까?

LinkedList의 탐색 성능 : O(N)
Red-Black Tree의 탐색 성능 : O(log N)
그래서 엔트리 개수가 많아지면 탐색 성능 저하 → Tree로 전환

여기에 하나 더

단순히 8 이상이라는 조건만으로는 Tree로 전환되지 않는다.

해시 테이블의 길이(capacity)가 64 이상일 때만 Tree로 전환이 가능하다.

즉, 두가지 조건을 모두 만족해야 Tree 로 바뀐다.

버킷 안의 엔트리 개수 ≥ 8
해시 테이블 크기 ≥ 64

이러한 조건들은 충돌이 많더라도 해시 테이블 자체가 작을 경우엔 굳이 Tree로 바꿀 필요가 없다는 설계적 고려로 보인다.

작은 테이블에서는 Tree로 바꾸더라도 오히려 전환 비용만 증가하고 실익이 적기 때문이다.

왜 하필 8이 기준일까?

해시 분포는 보통 푸아송 분포를 따른다?

일반적으로 해시 함수가 균등하게 분포한다고 가정할 때,

해시 충돌로 인해 한 버킷에 저장되는 엔트리 개수는 푸아송 분포(Poisson Distribution) 를 따른다.

포아송 분포란?
어떤 사건이 일정한 평균 발생률을 가지고 특정 시간/공간에서 독립적으로 발생할 때 그 횟수의 확률 분포를 나타낸다.

HashMap의 체이닝 구조에서, 한 버킷에 k개의 엔트리가 저장될 확률은 다음과 같이 계산된다.

P(k) = (e^−λ * λ^k) / k!

Java 공식 문서에 따르면 평균 λ는 0.5로 가정하고 있고,

이 때 k가 8 이상일 확률은 매우 낮아지며, 그만큼 성능 저하 가능성도 현실적으로 의미 있어지는 시점이라는 분석이 가능하다.

📌 체이닝을 쓸 때 연결 리스트의 크기 k에 따른 확률 = e^(-0.5) * (0.5)^k / k!
출처: velog 글 보기

8이라는 수치는 성능과 메모리 사용 간의 트레이드오프를 고려해

실제로 성능 이득이 나타나는 시점을 기준으로 정해졌다고 볼 수 있다.

그럼 처음부터 Tree로 하면 안 될까?

내 생각엔 메모리 오버헤드 때문인 것 같다.

LinkedList는 각 노드가 다음 노드만 참조 -> 간단한 구조
Red-Black Tree는 부모/자식 참조 + 노드 색상 정보 등 추가 필드를 갖고 있어 구조가 더 복잡하고 메모리 사용량도 더 많다.

즉, 평소에는 LinkedList로 가볍게 유지하다가

해시 충돌이 많아지는 경우에만 성능을 위해 Tree로 전환하는 방식이다.

왜 6 이하일 때 다시 LinkedList로 바꿀까?

처음엔 이게 이상하게 느껴졌다.

이미 Tree로 변환되어 있고 성능도 좋은데 굳이 다시 List로 바꿀 필요가 있을까?
다시 LinkedList ↔ Tree 이렇게 전환되는 비용이 더 클 수도 있지 않을까?

하지만 아래와 같은 가설을 세웠다.

1. 메모리 오버헤드 절감

Tree는 유지 자체가 메모리 비용이 크다.
데이터가 줄어들면 List로 바꿔서 가볍게 유지하는 편이 효율적

2. 전환비용 최소화

만약 기준을 7로 잡으면 Tree ↔ List 전환이 너무 자주 발생할 수 있다.
그래서 8 → Tree 전환, 6 → List 전환으로 임계점을 벌려 불필요한 재전환을 방지한다.

다시 말해 전환 비용은 일시적이지만 메모리 오버헤드는 지속적이라는 점을 고려한 설계로 보인다.

마무리

결국, HashMap은 충돌 상황에서도 일정 수준의 성능을 보장하기 위해 체이닝, Tree 전환 등 다양한 구조적 장치를 마련해 두었다.

하지만 진짜 핵심은 따로 있다.

"가장 좋은 방법은 충돌이 잘 안나게 hashCode() 를 설계해야 한다."

hashCode()가 충분히 고르게 분포하도록 잘 설계되어 있다면

실제로는 충돌 자체가 거의 일어나지 않거나 위에서 설명한 극단적인 트리 전환까지 갈 일이 드물다고 생각한다.

다시 말해서 LinkedList ↔ Tree 전환은 어디까지나 최후의 수단,

예외적인 경우를 대비한 방어적 설계일 뿐이라고 생각한다.

이번 글을 통해 단순히 "HashMap은 빠르다"는 수준을 넘어서
"왜 그렇게 설계되었는가?" 에 대한 나만의 이해와 관점을 쌓을수 있었다.

Developer fiat_lux