Brain109. 해시맵 vs 트리맵 (HashMap vs TreeMap)
핵심 인사이트 (3줄 요약)
- 본질: 해시맵(HashMap)은 해시 함수를 사용하여 키를 값에 매핑하는 해시 테이블 기반의 자료구조이고, 트리맵(TreeMap)은 이진 탐색 트리(BST) 기반으로 키를 값에 매핑하는 정렬된 키-값 쌍을 저장하는 자료구조이다.
- 가치: 해시맵은 O(1) 평균 검색 성능을 제공하고, 트리맵은 키가 정렬된 순서로 저장되어 범위 쿼리와 순서 기반 작업에 적합하다.
- 융용: 해시맵은 캐싱, 중복 제거, 사전 구조 등에 사용되고, 트리맵은 정렬된 데이터 관리, 범위 검색, 순회 등에 사용된다.
Ⅰ. 개요 및 필요성 (Context & Necessity)
해시맵(HashMap)과 트리맵(TreeMap)은 모두 키-값 쌍(Key-Value Pair)을 저장하는 자료구조이지만, 내부 구현과 특성에서 중요한 차이가 있다. 적절한 상황에서 올바른 자료구조를 선택하는 것은性能과 기능적으로 큰 차이를 만든다.
**해시맵(HashMap)**은 해시 테이블(Hash Table)을 기반으로 한 자료구조로, 키의 해시 값을 계산하여 값에 직접 접근한다. 키의 해시 함수 값에 따라 버킷(Bucket)이 결정되고, 충돌(Collision)이 발생하면 체이닝(Chaining)이나 개방 주소법(Open Addressing)으로 해결한다. 평균적으로 삽입, 검색, 삭제 모두 O(1) 시간에 수행된다.
**트리맵(TreeMap)**은 이진 탐색 트리(Binary Search Tree), 구체적으로는 레드-블랙 트리(Red-Black Tree)로 구현된다. 키가 이진 트리에 저장되며, 트리의 중위 순회(Inorder Traversal)를 하면 키가 정렬된 순서로 방문된다. 모든 작업이 O(log n) 시간에 수행되며, 키가 정렬되어 있다는 추가적인 특성을 가진다.
선택 기준으로 순서가 중요한 경우는 트리맵을 사용해야 한다. 키의 정렬된 순서로 순회하거나, 범위 쿼리(Range Query)를 수행해야 할 때 적합하다. 성능이 중요한 경우는 해시맵을 사용한다. O(1) 평균 검색 성능이 O(log n)보다 빠르다. 키의 자연스러운 순서가 있는 경우(예: 문자열, 숫자)는 트리맵이 더 자연스럽다.
[HashMap vs TreeMap 구조 비교]
┌──────────────────────────────────────────────────────────────┐
│ │
│ [HashMap 내부 구조] │
│ ──────────────────────────────────────────── │
│ │
│ 해시 함수: hash(key) → 버킷 인덱스 │
│ │
│ 버킷 0: [키:"Alice", 값:100] → [키:"Bob", 값:200] → ... │
│ 버킷 1: [키:"Charlie", 값:150] → null │
│ 버킷 2: null │
│ 버킷 3: [키:"David", 값:300] → ... │
│ ... │
│ │
│ • 키의 해시값으로 버킷 결정 │
│ • 충돌 시 체이닝(Linked List 또는 Tree) │
│ • 순서 보장 안됨 │
│ │
│ [TreeMap 내부 구조] │
│ ──────────────────────────────────────────── │
│ │
│ [David:300] │
│ / \ │
│ [Bob:200] [Frank:400] │
│ / \ │
│ [Alice:100] [Charlie:150] │
│ │
│ • 레드-블랙 트리로 구현 │
│ • 키가 이진 트리 순서로 저장 │
│ • 중위 순회: Alice → Bob → Charlie → David → Frank │
│ • 모든 작업이 O(log n) │
│ │
│ [HashMap vs TreeMap 특성 비교] │
│ ──────────────────────────────────────────── │
│ │
│ HashMap TreeMap │
│ ───────────────────────── ───────────────────────── │
│ 내부 구조: 해시 테이블 이진 탐색 트리 │
│ 시간 복잡도: O(1) 평균 O(log n) │
│ 순서: 순서 없음 키 순서로 정렬 │
│ 동기화: 비동기 (기본) 비동기 (SortedMap) │
│ null 키: 하나의 null 허용 null 불가 (Comp非対応) │
│ null 값: 여러 null 허용 여러 null 허용 │
│ 구현: 해시 함수 + 체이닝 레드-블랙 트리 │
│ │
└──────────────────────────────────────────────────────────────┘
- 관찰: HashMap은 O(1), TreeMap은 O(log n) 검색 시간을 가진다.
- 원인: HashMap은 직접 주소 지정처럼 해시값으로 직접 접근하고, TreeMap은 트리를 탐색하기 때문이다.
- 결과: 대규모 데이터에서 HashMap이 더 빠르지만, TreeMap은 순서가 보장된다.
- 판단: 성능이냐 순서냐에 따라 선택이 달라진다.
📢 섹션 요약 비유: HashMap은 도서관의 사서 시스템과 같습니다. 책 제목(키)을 해시하여 특정 책꽂이(버킷)에 바로 이동하여 책을 찾습니다. TreeMap은 도서관의 알파벳별 분류 시스템과 같습니다. A로 시작하는 책들, B로 시작하는 책들 등으로 분리되어 있어 순서대로 진행하면서 찾을 수 있습니다. HashMap이 더 빠르지만, TreeMap은 순서대로 나열되어 있습니다.
Ⅱ. HashMap 심층 분석 (Deep Dive into HashMap)
HashMap의 핵심은 해시 함수와 충돌 해결 기법이다. Java 8 이후부터는 충돌이 많이 발생하면 Linked List 대신 Red-Black Tree를 사용하여 성능을 개선한다.
해시 함수에서 좋은 해시 함수는 키를 균등하게 분포시켜 충돌을 최소화한다. Java에서 Object의 hashCode()는 객체의 메모리 주소를 기반으로 기본 해시값을 생성한다. String의 경우 문자열 내용을 기반으로 효율적인 해시 함수가 구현되어 있다.
충돌 해결에서 JDK 7까지는 Separate Chaining(연결 리스트로 충돌 처리)을 사용했다. JDK 8 이후부터는 버킷 내 항목 수가 8개 이상이면 Linked List를 Red-Black Tree로 변환한다. 이는 검색 시간을 O(n)에서 O(log n)으로 개선한다.
**扩容(Resize/Rehashing)**에서 HashMap은 부하율(Load Factor)이 0.75를 초과하면 테이블 크기를 2배로 확장한다.扩容 시 모든 항목을 다시 해시하여 새로운 버킷에 배치해야 한다. 이는 O(n) 시간이 걸리지만 드물게 발생하므로 분할 상환 분석 시 O(1)이다.
[HashMap 동작 상세]
┌──────────────────────────────────────────────────────────────┐
│ │
│ [삽입 과정: put("Alice", 100)] │
│ ──────────────────────────────────────────── │
│ Step 1: key.hashCode() 호출 → 해시값 h 계산 │
│ Step 2: h & (n-1)으로 버킷 인덱스 결정 │
│ Step 3: 해당 버킷이 비어있으면 노드 생성 │
│ 비어있지 않으면: │
│ - 같은 키가 있으면 값 업데이트 │
│ - 다른 키면链表 또는 트리에 추가 │
│ Step 4: 항목 수 증가, 부하율 검사 │
│ Step 5: 부하율 > 0.75이면 resize() 호출 │
│ │
│ [검색 과정: get("Alice")] │
│ ──────────────────────────────────────────── │
│ Step 1: 키의 해시값 계산 │
│ Step 2: 버킷 인덱스 결정 │
│ Step 3: 버킷이 비어있으면 null 반환 │
│ 그렇지 않으면链表 또는 트리에서 키 비교 │
│ Step 4: 찾으면 값 반환, 없으면 null 반환 │
│ │
│ [JDK 8 이후 Tree 변환] │
│ ──────────────────────────────────────────── │
│ 버킷 내 항목 수: │
│ 1개: 직접 노드 │
│ 2-7개: Linked List │
│ 8개 이상: Red-Black Tree │
│ │
│ 예: 같은 버킷에 8개 이상 충돌 시 │
│ Linked List → Red-Black Tree │
│ → 검색 시간: O(n) → O(log n) │
│ │
│ [扩容 과정] │
│ ──────────────────────────────────────────── │
│ threshold = capacity * loadFactor │
│ 기본값: capacity = 16, loadFactor = 0.75 │
│ → threshold = 12 │
│ │
│ 항목이 12개 초과 시: │
│ - capacity 2배로 확장 (16 → 32) │
│ - 모든 항목 rehash하여 새 버킷에 배치 │
│ - threshold = 24로 업데이트 │
│ │
└──────────────────────────────────────────────────────────────┘
- 관찰: HashMap의 성능은 해시 함수의 품질과 부하율에 크게 의존한다.
- 원인: 좋은 해시 함수는 키를 균등하게 분포시켜 충돌을 줄이기 때문이다.
- 결과: 해시 함수의 선택과 부하율 관리에 따라 성능이 크게 달라진다.
- 판단: 대부분의 HashMap 구현은 잘 최적화되어 있으므로 기본 설정을 사용하면 된다.
Ⅲ. TreeMap 심층 분석 (Deep Dive into TreeMap)
TreeMap은 이진 탐색 트리 중 레드-블랙 트리로 구현되어 있다. 이는 O(log n) 시간 복잡도를 보장하며, 키가 정렬된 순서로 저장된다는 추가적인 특성을 제공한다.
레드-블랙 트리는 자가 균형 이진 탐색 트리로, 어떤 경로도 다른 경로의 2배 이상 길어지지 않도록 보장한다. 이는 최악의 경우에도 O(log n) 시간을 보장한다. 모든 노드는 빨간색 또는 검은색으로 칠해져 있다. 루트는 검은색이고, 리프(NIL)는 검은색이며, 빨간 노드의 자식은 반드시 검은색이다.
주요 연산에서 삽입은 일반 BST 삽입 후 레드-블랙 트리 특성을 유지하기 위해 회전과 색상 변환을 수행한다. 검색은 일반 BST와 동일하게 키를 비교하며 좌우로 이동한다. 삭제는 가장 복잡한 연산으로, 여러 경우를 처리해야 한다. 순회는 중위 순회(Inorder Traversal)로 하면 키가 오름차순으로 방문된다.
Navigation 메서드로 TreeMap은 키를 기반으로 다양한 메서드를 제공한다. lowerKey(k), floorKey(k), ceilingKey(k), higherKey(k)는 각각 주어진 키보다 작은/작거나 같은/크거나 같은/큰 키를 반환한다. firstKey(), lastKey()는 가장 작은/가장 큰 키를 반환한다.
[TreeMap 동작 상세]
┌──────────────────────────────────────────────────────────────┐
│ │
│ [레드-블랙 트리 특성] │
│ ──────────────────────────────────────────── │
│ 1. 모든 노드는 빨간색 또는 검은색 │
│ 2. 루트는 검은색 │
│ 3. 모든 리프(NIL)는 검은색 │
│ 4. 빨간색 노드의 자식은 반드시 검은색 (赤-赤 충돌禁止) │
│ 5. 모든 경로에서 검은색 높이가 동일 │
│ │
│ → 결과: 어떤 경로도 다른 경로의 2배 이상 길어지지 않음 │
│ → 최악의 경우에도 O(log n) 보장 │
│ │
│ [TreeMap 삽입: put("E", 5)] │
│ ──────────────────────────────────────────── │
│ Step 1: BST처럼 삽입 위치 찾기 │
│ root → "E"를 어디에? → "D"의 오른쪽 │
│ Step 2: 새 노드를 빨간색으로 삽입 │
│ Step 3: 레드-블랙 특성 복구 (회전, 색상 변환) │
│ - Uncle이 빨간색 → 색상 변환 │
│ - Uncle이 검은색 → 회전 후 색상 변환 │
│ │
│ [TreeMap 순회] │
│ ──────────────────────────────────────────── │
│ 중위 순회 (Inorder): 왼쪽 → 현재 → 오른쪽 │
│ │
│ 예: TreeMap {"C":3, "A":1, "B":2, "E":5, "D":4} │
│ 순회 결과: A → B → C → D → E (오름차순) │
│ │
│ [Navigation 메서드] │
│ ──────────────────────────────────────────── │
│ 메서드 설명 예시 │
│ ──────────────────────────────────────────── │
│ lowerKey(k) < k 인 가장 큰 키 lowerKey(5) → 4 │
│ floorKey(k) ≤ k 인 가장 큰 키 floorKey(5) → 5 │
│ ceilingKey(k) ≥ k 인 가장 작은 키 ceilingKey(5) → 5 │
│ higherKey(k) > k 인 가장 작은 키 higherKey(5) → 6 │
│ │
│ [TreeMap vs HashMap 성능 비교] │
│ ──────────────────────────────────────────── │
│ │
│ 연산 HashMap TreeMap │
│ ──────────────────────────────────────────── │
│ 삽입 O(1) 평균 O(log n) │
│ 검색 O(1) 평균 O(log n) │
│ 삭제 O(1) 평균 O(log n) │
│ 최소/최대 O(n) O(log n) │
│ 범위 쿼리 O(n) O(log n + k) │
│ 정렬된 순회 불가능 가능 │
│ │
└──────────────────────────────────────────────────────────────┘
- 관찰: TreeMap은 O(log n) 시간을 보장하지만, 순서 관련 기능이 뛰어나다.
- 원인: 레드-블랙 트리의 균형 잡힌 구조 덕분이다.
- 결과: 대규모 데이터에서도 예측 가능한 성능을 보인다.
- 판단: 순서 관련 작업이 필요하다면 TreeMap이 HashMap보다 효율적이다.
Ⅳ. 선택 기준 및 활용 시나리오 (Selection Criteria & Use Cases)
HashMap과 TreeMap은 각각 다른 상황에서 선호된다. 성능, 순서, 기능적 요구사항을 고려하여 적절한 자료구조를 선택해야 한다.
HashMap이 선호되는 경우로 순서가 필요 없는 경우에 적합하다. 키의 순서와 관계없이 빠른 검색이 필요할 때 사용한다. 대규모 데이터 처리에서 O(1) 평균 검색 성능이 O(log n)보다 빠르다. 빈번한 삽입/삭제에서 해시 테이블 기반이므로 이러한 작업에 효율적이다. 단순 키-값 저장에서 추가적인 순서 기능이 필요 없는 경우에 적합하다.
TreeMap이 선호되는 경우로 키의 순서가 중요한 경우에 적합하다. 정렬된 순서로 데이터를 순회해야 할 때 사용한다. 범위 쿼리에서 특정 범위의 키에 해당하는 값들을 효율적으로 가져와야 할 때 사용한다. 최소/최대 값 찾기에서 O(1) 또는 O(log n) 시간에 가능하다. 키 기반 네비게이션에서 lowerKey, floorKey 등의 메서드가 필요할 때 사용한다.
ConcurrentHashMap vs TreeMap에서thread-safe가 필요한 경우 ConcurrentHashMap(HashMap 기반)이나 synchronizedMap(TreeMap 기반)을 사용한다. Java 8 이후 ConcurrentHashMap은 더 좋은 성능을 제공한다.
[선택 기준 및 활용 시나리오]
┌──────────────────────────────────────────────────────────────┐
│ │
│ [HashMap 활용] │
│ ──────────────────────────────────────────── │
│ │
│ // 사용자 세션 저장 │
│ Map<String, UserSession> sessions = new HashMap<>(); │
│ sessions.put(sessionId, userSession); │
│ │
│ // 단어 빈도수 세기 │
│ Map<String, Integer> wordCount = new HashMap<>(); │
│ wordCount.put(word, wordCount.getOrDefault(word, 0) + 1); │
│ │
│ // 캐시 구현 │
│ Map<String, Data> cache = new HashMap<>(); │
│ │
│ [TreeMap 활용] │
│ ──────────────────────────────────────────── │
│ │
│ // 정렬된 사용자 목록 │
│ Map<String, Integer> sortedWordCount = new TreeMap<>(); │
│ // words 자동 정렬됨 │
│ │
│ // 범위 쿼리: 10에서 100 사이 점수 │
│ Map<Integer, String> scoreBoard = new TreeMap<>(); │
│ scoreBoard.subMap(10, 101).forEach((k, v) -> ...); │
│ │
│ // Leaders 보드 구현 │
│ Map<Integer, Player> rankings = new TreeMap<>( │
│ Collections.reverseOrder()); │
│ rankings.firstEntry() // 1위 │
│ rankings.lastEntry() // 꼬등 │
│ │
│ [LinkedHashMap: 순서 있는 HashMap] │
│ ──────────────────────────────────────────── │
│ • 삽입 순서 유지 │
│ • HashMap + Linked List로 구현 │
│ • Map<String, Integer> ordered = new LinkedHashMap<>(); │
│ ordered.put("first", 1); │
│ ordered.put("second", 2); │
│ // 순회: first → second │
│ │
│ [성능 최적화 팁] │
│ ──────────────────────────────────────────── │
│ HashMap: │
│ • 적절한 초기 용량 설정 (확산 방지) │
│ • 불변(immutable) 키 사용 권장 │
│ • 커스텀 해시 함수 필요한 경우 신중하게 설계 │
│ │
│ TreeMap: │
│ • 자연 순서 외의 정렬이 필요하면 Comparator 제공 │
│ • NavigableMap 인터페이스의 rich API 활용 │
│ │
└──────────────────────────────────────────────────────────────┘
- 관찰: HashMap이 TreeMap보다 더 널리 사용된다.
- 원인: 대부분의 경우 순서가 필요 없고, HashMap이 더 빠르기 때문이다.
- 결과: 순서 기능이 필요 없는 한 HashMap을 기본으로 사용한다.
- 판단: 순서 기능이 필요할 때만 TreeMap으로 전환한다.
Ⅴ. 요약 및 점검 (Summary & Checklist)
HashMap과 TreeMap은 모두 키-값 쌍을 저장하는 자료구조이지만, HashMap은 해시 테이블 기반(O(1) 평균), TreeMap은 레드-블랙 트리 기반(O(log n))으로 구현된다. HashMap은 빠른 검색을, TreeMap은 정렬된 순서와 범위 쿼리를 제공한다.
핵심 점검 사항으로 먼저, HashMap은 해시 테이블 기반, O(1) 평균 검색, 순서 없음, null 허용等特点가 있다. 둘째, TreeMap은 레드-블랙 트리 기반, O(log n) 검색, 키 순서로 정렬, Navigation API 제공等特点가 있다. 셋째, 선택 기준으로 순서가 필요하면 TreeMap, 성능이 중요하면 HashMap을 선택한다. 넷째, JDK 8 이후 변경으로 HashMap은 버킷 내 항목이 8개 이상이면 Tree로 변환한다. 다섯째, LinkedHashMap은 HashMap이면서 삽입 순서를 유지한다.
핵심 용어 정리
- HashMap: 해시 테이블 기반 키-값 쌍 저장소, O(1) 평균 검색
- TreeMap: 레드-블랙 트리 기반 정렬된 키-값 쌍 저장소, O(log n) 검색
- 레드-블랙 트리: 스스로 균형을 잡는 이진 탐색 트리
- 부하율 (Load Factor): HashMap에서 항목 수 / 용량, 기본 0.75
- NavigableMap: TreeMap이 구현하는 인터페이스로, 네비게이션 메서드 제공
检查清单 (Checkpoint)
- HashMap과 TreeMap의 내부 구조 차이를 설명할 수 있는가?
- HashMap의 평균 시간 복잡도가 O(1)인 이유를 설명할 수 있는가?
- TreeMap에서 키가 정렬되는 이유를 설명할 수 있는가?
- HashMap과 TreeMap 중 어떤 것을 선택할지 결정할 수 있는가?
- JDK 8 이후 HashMap의 변경 사항(버킷 내 Tree 변환)을 알고 있는가?
- LinkedHashMap이 무엇이고 언제 사용하는지 알고 있는가?