[Java] TreeMap

TreeMap, java.util.TreeMap, Java TreeMap, 트리맵, 정렬 맵

정의

java.util.TreeMap<K,V> 는 Red-Black Tree 기반의 정렬된 Map. NavigableMap (확장 인터페이스) 을 구현해 범위 쿼리, floor/ceiling, sub-map 같은 정렬 기반 연산을 제공한다.

key 는 자연 순서 (Comparable) 또는 생성 시 지정한 Comparator 로 정렬된다.

시각화

핵심 메서드 (NavigableMap)

TreeMap<Integer, String> tm = new TreeMap<>();
tm.put(10, "a"); tm.put(20, "b"); tm.put(30, "c");

tm.firstKey();           // 10
tm.lastKey();            // 30
tm.floorKey(15);         // 10  (≤ 15 중 가장 큰)
tm.ceilingKey(15);       // 20  (≥ 15 중 가장 작은)
tm.higherKey(20);        // 30  (> 20 중 가장 작은)
tm.lowerKey(20);         // 10  (< 20 중 가장 큰)

tm.subMap(10, 30);       // [10, 30) 의 view
tm.headMap(20);          // < 20 의 view
tm.tailMap(20);          // >= 20 의 view

tm.descendingMap();      // 역순 view

이런 정렬 기반 연산이 필요할 때 TreeMap. 그 외에는 HashMap 이 빠르다.

복잡도

Red-Black Tree 의 성질.

작업	시간
get, put, remove	O(log n)
containsKey	O(log n)
firstKey, lastKey	O(log n)
floorKey, ceilingKey	O(log n)
순회	O(n) (정렬 순서)

HashMap 의 평균 O(1) 보다 느리지만 최악도 O(log n) 으로 보장된다는 점이 강점.

Comparator 사용

TreeMap<String, Integer> reverse = new TreeMap<>(Comparator.reverseOrder());
TreeMap<Person, String> byAge = new TreeMap<>(Comparator.comparingInt(Person::age));

Comparator 가 일관되지 않으면 (transitive 위반 등) tree 가 깨진다.

null key 비허용

HashMap 과 달리 key 에 null 을 넣으면 NullPointerException (자연 순서 비교를 할 수 없음). Comparator 가 null 을 처리하도록 만들면 가능하지만 보통 안 한다.

사용 사례

• 시간순 이벤트 조회: TreeMap<Instant, Event> + subMap(start, end)
• 범위 빈도수: 가격대별 상품 수, 점수 구간별 통계
• Floor / Ceiling lookup: 할인율 구간 찾기, IP 범위 매칭
• 자동완성 prefix: subMap(prefix, prefix + "\uffff")

ConcurrentSkipListMap 과의 비교

항목	TreeMap	ConcurrentSkipListMap
백킹	Red-Black Tree	Skip List
Thread-safe	✗	✓
단일 스레드 성능	빠름	약간 느림
동시성	외부 동기화 필요	lock-free 읽기

함정

1. Comparator 와 equals 의 불일치

TreeMap 은 equals 가 아니라 compareTo/Comparator.compare 로 동등성 을 판단한다. 두 key 가 equals 는 false 인데 compare 가 0 을 반환하면 같은 key 로 취급.

TreeMap<BigDecimal, String> tm = new TreeMap<>();
tm.put(new BigDecimal("1.0"), "a");
tm.put(new BigDecimal("1.00"), "b");
// tm.size() == 1, "b" 가 "a" 를 덮어씀
// BigDecimal.compareTo 는 scale 을 무시

참고

• Object
• Iterable
• Collection
• Map
• HashMap
• LinkedHashMap
• ConcurrentHashMap