0Pricing
Java Academy · 강의

트리화와 성능

Java 8 이상에서 충돌을 처리하는 방식을 알아봅니다

트리화와 성능은(는) CoddyKit의 무료 Java Academy 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Java Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Java Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

충돌 문제

Java 8 이전에는 충돌이 많은 버킷이 긴 연결 리스트가 되었습니다. 해당 버킷의 조회 성능은 O(n)으로 저하되었습니다.

공격자는 모든 키가 한 버킷으로 해시되도록 조작하여 이를 악용하고 서비스 거부를 일으킬 수 있었습니다.

public class Main {
    public static void main(String[] args) {
        // All these strings can be made to collide in one bucket
        System.out.println("FB".hashCode() == "Ea".hashCode());
    }
}

Java 8의 트리화

Java 8에서 트리화가 추가되었습니다. 하나의 버킷에 항목이 너무 많이 들어가면 연결 리스트가 균형 잡힌 레드-블랙 트리로 변환됩니다.

그러면 해당 버킷의 조회 성능은 O(n)이 아니라 O(log n)이 됩니다.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i < 1000; i++) m.put(i, i);
        System.out.println("Lookups stay fast: " + m.get(742));
    }
}

임계값: 트리화 임계값

상수 TREEIFY_THRESHOLD는 8입니다. 버킷에 항목이 8개 들어가면 트리로 변환됩니다.

하지만 두 번째 조건도 있습니다. 테이블 크기가 최소한 MIN_TREEIFY_CAPACITY(64) 이상이어야 하며, 그렇지 않으면 맵이 대신 크기를 조정합니다.

public class Main {
    public static void main(String[] args) {
        int TREEIFY_THRESHOLD = 8;
        int MIN_TREEIFY_CAPACITY = 64;
        System.out.println("Treeify when bucket size >= " + TREEIFY_THRESHOLD);
        System.out.println("...and table capacity >= " + MIN_TREEIFY_CAPACITY);
    }
}

먼저 크기 조정, 나중에 트리화

버킷이 넘치지만 테이블이 아직 작으면(64 미만) HashMap은 먼저 테이블의 크기를 조정합니다.

크기를 조정하면 일반적으로 항목이 다시 분배되어 집중 지점이 사라지므로, 트리화는 실제로 해시 분포가 나쁜 경우를 위한 최후의 수단일 뿐입니다.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16);
        for (int i = 0; i < 50; i++) m.put(i, i);
        // Many resizes happened before any treeify would
        System.out.println("size = " + m.size());
    }
}

트리 해제

트리는 영구적이지 않습니다. 삭제로 버킷의 크기가 UNTREEIFY_THRESHOLD(6) 미만으로 줄어들면 트리는 연결 리스트로 되돌아갑니다.

트리화 기준인 8과 트리 해제 기준인 6 사이의 간격은 경계에서 반복적으로 전환되는 현상을 방지합니다.

public class Main {
    public static void main(String[] args) {
        System.out.println("TREEIFY_THRESHOLD   = 8");
        System.out.println("UNTREEIFY_THRESHOLD = 6");
        System.out.println("Gap prevents flip-flopping at the edge");
    }
}

트리에는 비교 가능 순서 또는 동일성 순서가 필요합니다

레드-블랙 트리는 항목의 순서를 정해야 합니다. HashMap은 먼저 해시 코드를 비교하고, 값이 같으면 키가 이를 구현하는 경우 Comparable을 사용하며, 그렇지 않으면 클래스 이름과 동일성을 기준으로 안정적인 순서를 정합니다.

Comparable인 키(예: String 또는 정수형)는 가장 깔끔한 트리 순서를 제공합니다.

public class Main {
    public static void main(String[] args) {
        System.out.println("String is Comparable: " + ("a" instanceof Comparable));
        System.out.println("Integer is Comparable: " + (Integer.valueOf(1) instanceof Comparable));
    }
}

실제 영향

해시 코드가 적절한 대부분의 실제 프로그램에서는 트리화를 전혀 보지 못할 것입니다. 버킷이 짧게 유지되기 때문입니다.

트리화는 해시가 좋지 않거나 악의적으로 조작된 경우에도 최악의 조회 성능을 O(log n)으로 제한하는 안전장치입니다.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("alpha", 1);
        m.put("beta", 2);
        m.put("gamma", 3);
        // Tiny buckets, plain linked lists, no trees needed
        System.out.println(m.get("beta"));
    }
}

상수 hashCode가 트리화를 강제합니다

의도적으로 상수 hashCode를 반환하면 모든 키가 하나의 버킷에 들어갑니다. 용량이 64 이상이면 해당 버킷이 트리화됩니다.

이는 안전장치를 보여 주지만 설계상의 문제 신호입니다. 대신 hashCode를 수정하세요.

import java.util.HashMap;
import java.util.Map;

public class Main {
    static class Bad implements Comparable<Bad> {
        final int v;
        Bad(int v) { this.v = v; }
        @Override public int hashCode() { return 1; } // forces collisions
        @Override public boolean equals(Object o) { return o instanceof Bad b && b.v == v; }
        @Override public int compareTo(Bad o) { return Integer.compare(v, o.v); }
    }
    public static void main(String[] args) {
        Map<Bad, Integer> m = new HashMap<>();
        for (int i = 0; i < 100; i++) m.put(new Bad(i), i);
        System.out.println("All in one bucket, still works: " + m.get(new Bad(50)));
    }
}

트리의 메모리 비용

트리 노드는 부모, 왼쪽, 오른쪽, 색상 참조를 저장하므로 일반 연결 리스트 노드보다 큽니다.

이것이 트리화가 기본 방식이 아니라 대체 수단인 또 다른 이유입니다. 트리는 최악의 경우 속도를 얻는 대신 메모리를 더 사용합니다.

public class Main {
    public static void main(String[] args) {
        System.out.println("Node: hash, key, value, next");
        System.out.println("TreeNode: + parent, left, right, prev, red flag");
        System.out.println("=> trees cost more memory per entry");
    }
}

트리화를 피하는 방법

트리화에 의존하고 싶은 경우는 거의 없습니다. 다음과 같은 방법으로 피하세요:

  • 분포가 좋은 hashCode()를 작성합니다.
  • 내장 타입이나 레코드를 키로 사용합니다.
  • 충돌을 줄이도록 맵의 크기를 미리 지정합니다.
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class Main {
    record Key(int a, int b) {}
    public static void main(String[] args) {
        Map<Key, Integer> m = new HashMap<>(256);
        for (int i = 0; i < 200; i++) m.put(new Key(i, i * 31), i);
        System.out.println("Even distribution, fast lookups: " + m.get(new Key(10, 310)));
    }
}

성능 요약

HashMap 연산 비용:

  • 좋은 hash: 평균 O(1)입니다.
  • 연결된 버킷: 최악의 경우 버킷당 O(n)입니다.
  • 트리화된 버킷: 버킷당 O(log n)입니다.

트리화는 최악의 경우를 제한하지만, 좋은 hashCode를 사용하면 O(1)을 유지할 수 있습니다.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(1 << 14);
        for (int i = 0; i < 10000; i++) m.put(i, i);
        System.out.println("10k entries, O(1) get: " + m.get(9999));
    }
}

빠른 확인

트리화에 대한 지식을 확인해 보세요.

복습

최신 HashMap이 충돌을 처리하는 방식을 학습했습니다:

  • 용량이 64 이상이면 버킷은 항목 8개에서 트리화됩니다.
  • 트리는 최악의 경우 조회 성능을 O(log n)으로 제공합니다.
  • 항목이 6개 미만이면 버킷의 트리가 해제됩니다.
  • 좋은 hashCode를 사용하면 이 안전장치가 작동하는 경우가 드뭅니다.

HashMap 내부 구조 과정을 완료했습니다.

public class Main {
    public static void main(String[] args) {
        System.out.println("Treeification course complete");
    }
}

자주 묻는 질문

“트리화와 성능” 강의는 무료인가요?

네 — “트리화와 성능” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Java Academy 강의 전체를 잠금 해제할 수 있습니다. Java Academy 강의에는 총 4개의 강의가 포함되어 있습니다.

“트리화와 성능”에서 뭘 배우나요?

Java 8 이상에서 충돌을 처리하는 방식을 알아봅니다 브라우저에서 직접 실행하는 실습 코드로 Java Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

Java Academy을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 Java Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.

“트리화와 성능” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 Java Academy 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 Java Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

  1. HashMap의 작동 원리
  2. equals/hashCode 계약
  3. hashCode 구현
  4. 트리화와 성능
← Java Academy(으)로 돌아가기