핵심 인사이트 (3줄 요약)
- 본질: HashMap은 해시 함수(Hash Function)로 키를 배열 인덱스에 직접 매핑하여 평균 O(1) 접근을 달성하는 반면, TreeMap은 레드-블랙 트리(Red-Black Tree)를 기반으로 키를 정렬된 순서로 유지하면서 O(log n) 연산을 보장한다.
- 가치: HashMap은 빠른 단건 조회·삽입·삭제가 필요할 때, TreeMap은 범위 조회(Range Query), 정렬된 순회, 최솟값·최댓값 조회가 필요할 때 선택하며, 두 자료구조의 선택이 알고리즘 전체 성능을 결정짓는다.
- 판단 포인트: 해시 충돌(Hash Collision)과 리해싱(Rehashing) 비용, 정렬 여부 필요성, 메모리 사용량을 3가지 축으로 판단하며, 실시간 순위표·캐시·집계 처리에는 HashMap, 이벤트 스케줄러·범위 검색에는 TreeMap이 적합하다.
Ⅰ. 개요 및 필요성
HashMap은 키-값(Key-Value) 쌍을 해시 테이블에 저장하는 자료구조로, 평균 O(1)의 접근 성능을 제공한다. TreeMap은 동일한 키-값 쌍을 이진 탐색 트리(BST, Binary Search Tree)의 균형 변형인 레드-블랙 트리에 저장하여 키의 정렬 순서를 항상 유지한다.
두 자료구조의 차이를 이해하지 못하면, 정렬이 필요한 작업에 HashMap을 쓰다가 O(n log n) 정렬을 매번 수행하거나, 단순 조회에 TreeMap을 써서 불필요하게 O(log n) 비용을 지불하게 된다.
┌──────────────────────────────────────────────────────────┐
│ HashMap vs TreeMap 내부 구조 대비 │
├──────────────────────────────────────────────────────────┤
│ │
│ [HashMap] [TreeMap] │
│ Key → hash(Key) → 배열 인덱스 Key → 레드-블랙 트리 삽입 │
│ │
│ 배열: [null][K2:V2][K1:V1]... 트리: K3 │
│ 해시 충돌 체인 가능 ╱ ╲ │
│ K1 K5 │
│ 장점: 단건 O(1) ╱ ╲ │
│ 단점: 순서 없음 K0 K2 │
│ │
│ 장점: 정렬 유지, 범위 조회 O(log n)│
│ 단점: 단건 O(log n) │
└──────────────────────────────────────────────────────────┘
- 📢 섹션 요약 비유: HashMap은 물건을 라벨(해시)로 창고 선반에 바로 꽂는 방식이라 찾기 빠르지만 선반이 뒤죽박죽이다. TreeMap은 물건을 크기 순서로 정렬해서 꽂아두는 방식이라 찾는 데 한 단계 더 걸리지만, "이 크기보다 큰 물건 전부 가져와"가 즉시 가능하다.
Ⅱ. 아키텍처 및 핵심 원리
HashMap 핵심 메커니즘
| 구성 요소 | 역할 | 상세 |
|---|---|---|
| 해시 함수 | Key → 배열 인덱스 변환 | hashCode() % 배열크기 |
| 로드 팩터 (Load Factor) | 리해싱 임계값 | 기본 0.75 (75% 찰 때 크기 2배 확장) |
| 충돌 해결 | 같은 인덱스 키 처리 | 체이닝(LinkedList) 또는 오픈 어드레싱 |
| Java 8+ 최적화 | 긴 체인 트리 변환 | 8개 초과 시 TreeMap으로 변환 (O(n)→O(log n)) |
TreeMap 핵심 메커니즘 (레드-블랙 트리)
┌──────────────────────────────────────────────────────────┐
│ 레드-블랙 트리 속성 (Self-Balancing BST) │
├──────────────────────────────────────────────────────────┤
│ │
│ 1. 모든 노드는 빨간색(R) 또는 검은색(B) │
│ 2. 루트 노드는 항상 검은색 │
│ 3. 빨간 노드의 자식은 항상 검은색 │
│ 4. 모든 리프까지의 검은색 노드 수 동일 │
│ │
│ [B:50] │
│ ╱ ╲ │
│ [R:30] [R:70] ← 삽입/삭제 후 회전으로 균형 유지 │
│ ╱ ╲ │
│ [B:20] [B:40] │
└──────────────────────────────────────────────────────────┘
- 📢 섹션 요약 비유: 레드-블랙 트리는 도서관 사서가 매번 책을 꽂은 뒤 왼쪽-오른쪽 균형을 맞추는 것과 같다. 불균형해질 때마다 빨간-검정 색 규칙으로 즉시 재배치하여 항상 O(log n)을 보장한다.
Ⅲ. 비교 및 연결
| 항목 | HashMap | TreeMap | LinkedHashMap |
|---|---|---|---|
| 내부 구조 | 해시 테이블 | 레드-블랙 트리 | 해시 테이블 + 연결 리스트 |
| 정렬 | 없음 | 키 기준 오름차순 | 삽입 순서 유지 |
| get/put | 평균 O(1) | O(log n) | 평균 O(1) |
| 범위 조회 | 불가 | subMap, headMap, tailMap | 불가 |
| null 키 | 허용 (1개) | 불허 | 허용 (1개) |
| 메모리 | 낮음 | 높음 (트리 포인터 오버헤드) | 중간 |
- 📢 섹션 요약 비유: HashMap은 편의점(빠르지만 순서 없음), TreeMap은 도서관(느리지만 정렬됨), LinkedHashMap은 번호표 뽑는 창구(빠르면서 접수 순서 기억)다.
Ⅳ. 실무 적용 및 기술사 판단
실무 시나리오: 실시간 순위표 vs 이벤트 스케줄러
HashMap 적합: 수백만 사용자의 포인트를 userId → point로 실시간 업데이트하는 게임 순위표 집계. 단건 갱신 빈도가 압도적으로 높으므로 O(1) HashMap이 최적.
TreeMap 적합: 이벤트 발생 시각(long)을 키로 하는 스케줄러. pollFirstEntry()로 가장 이른 이벤트를 O(log n)으로 꺼내고, 특정 시간 범위의 이벤트를 subMap(from, to)으로 O(log n + k)에 추출.
체크리스트
- 충돌 집중(Hash Skew) 발생 시 hashCode() 재정의로 균등 분배 확보.
- TreeMap의 Comparator 지정 시 null 안전성과 일관성(equals와 일치) 보장.
- 멀티스레드 환경: HashMap → ConcurrentHashMap, TreeMap → ConcurrentSkipListMap.
안티패턴
-
정렬된 결과가 필요한 경우에 HashMap을 쓰고 나중에 매번 정렬하는 코드. O(n log n) 정렬이 반복 발생하여 TreeMap의 O(log n) 삽입 비용보다 훨씬 비싸진다.
-
📢 섹션 요약 비유: 정렬이 필요한데 HashMap을 쓰는 건, 창고에 물건을 아무렇게나 쌓고 주문마다 전부 꺼내 다시 정리하는 것과 같다. 처음부터 TreeMap(정렬 창고)을 쓰면 주문마다 정리 비용이 없어진다.
Ⅴ. 기대효과 및 결론
| 기대효과 | HashMap | TreeMap |
|---|---|---|
| 조회 성능 | 평균 O(1), 최악 O(n) | 보장 O(log n) |
| 적합 사례 | 캐시, 집계, 카운팅 | 범위 조회, 정렬 순회 |
| 확장성 | 리해싱으로 O(n) 일시 발생 | 균형 보장으로 안정적 |
올바른 Map 선택은 알고리즘 설계의 기초다. 실무에서 HashMap과 TreeMap은 서로 보완하여 사용되며, 레디스(Redis) 등 분산 캐시는 내부적으로 해시 테이블(Hash)과 정렬 집합(Sorted Set)을 둘 다 지원하여 이 두 자료구조의 특성을 모두 활용한다.
- 📢 섹션 요약 비유: HashMap은 스피드 레이서(빠르지만 정해진 코스만), TreeMap은 내비게이션 장착 차(약간 느리지만 어디든 최적 경로로 가능)다. 레이스(단건 조회)엔 전자, 여행(범위 탐색)엔 후자가 맞다.
📌 관련 개념 맵
| 개념 | 연결 포인트 |
|---|---|
| 해시 함수 (Hash Function) | HashMap의 O(1) 성능의 근거; 키를 균등하게 분산 |
| 레드-블랙 트리 | TreeMap의 내부 자료구조; 항상 O(log n) 보장 |
| 해시 충돌 (Hash Collision) | 성능 저하 요인; 체이닝 또는 오픈 어드레싱으로 해결 |
| ConcurrentHashMap | HashMap의 스레드 안전 버전; 세그먼트 락 방식 |
| Skip List | TreeMap의 분산 시스템 대안; ConcurrentSkipListMap의 기반 |
📈 관련 키워드 및 발전 흐름도
[배열 — O(1) 인덱스 접근, 키 제약]
│
▼
[해시 테이블 (HashMap) — O(1) 키-값 접근]
│
▼
[균형 이진 탐색 트리 (TreeMap) — O(log n) 정렬 유지]
│
▼
[Java 8 LinkedHashMap + 복합 활용 — 삽입 순서 + O(1)]
│
▼
[ConcurrentHashMap / Skip List — 분산/병렬 환경 확장]
배열의 O(1) 접근에서 해시 테이블, 균형 트리로 진화하며, 멀티스레드와 분산 환경에서 ConcurrentHashMap/SkipList로 확장된다.
👶 어린이를 위한 3줄 비유 설명
- HashMap은 물건마다 고유 번호(해시)를 붙여서 창고 선반에 직접 바로 꽂는 방식이에요 — 찾기가 엄청 빠르지만 선반 순서는 뒤죽박죽이에요.
- TreeMap은 물건을 크기 순서대로 줄 세워 꽂는 방식이라 "이것보다 큰 물건 다 가져와!"처럼 범위 검색이 아주 쉬워요.
- 빨리빨리 하나씩 찾을 땐 HashMap, 순서나 범위가 필요할 땐 TreeMap을 고르면 된답니다!