자바에서 HashMap과 TreeMap은 모두 Map 인터페이스를 구현하는 대표적인 컬렉션 클래스입니다. 두 클래스는 이름은 비슷하지만 내부 구조, 동작 방식, 성능 특성에서 큰 차이를 보입니다. 이 글에서는 두 클래스의 차이점을 항목별로 살펴보고, 어떤 상황에서 어떤 클래스를 선택하는 것이 좋은지 알아보겠습니다.
HashMap이란?
- 자바의 해시 테이블(Hash Table) 기반 자료구조입니다.
- Map 인터페이스의 구현체로, Map, Cloneable, Serializable 인터페이스를 함께 구현합니다.
- null 키는 최대 하나까지 허용하며, null 값은 여러 개 저장할 수 있습니다.
- get, put 같은 기본 연산에서 O(1)의 상수 시간 성능을 제공하기 때문에 TreeMap보다 빠릅니다.
- 키를 정렬하지 않으므로 서로 다른 타입의(이기종) 요소도 키로 사용할 수 있습니다.
- 요소의 삽입 순서나 정렬 순서를 유지하지 않습니다.
- 따라서 정렬된 키-값 쌍이 필요하지 않은 경우에 적합합니다.
- 키 비교에는 Object 클래스의 equals() 메소드를 사용하며, Map 클래스가 이를 오버라이드합니다.
- keySet(), get(), put() 등 기본적인 메소드만 제공합니다.
TreeMap이란?
- 자바의 트리(Tree) 구조 기반 자료구조입니다.
- 마찬가지로 Map 인터페이스를 기반으로 하며, NavigableMap, Cloneable, Serializable 인터페이스를 구현합니다.
- null 키는 허용하지 않지만, null 값은 여러 개 저장할 수 있습니다.
- 정렬 상태를 유지해야 하므로 키는 동일한 타입(동질적)이어야 하며, 서로 비교 가능한 값이어야 합니다.
- add(), remove(), contains() 등 대부분의 연산이 O(log n)의 시간 복잡도를 가지므로 HashMap보다 느립니다.
- 내부적으로 레드-블랙 트리(Red-Black Tree)를 사용합니다.
- 레드-블랙 트리는 스스로 균형을 유지하는(self-balancing) 이진 탐색 트리입니다.
- 키 비교에는 compareTo() 메소드를 사용합니다.
- tailMap(), firstKey(), lastKey(), pollFirstEntry(), pollLastEntry() 등 다양한 탐색 및 조작 메소드를 제공합니다.
- 요소들은 오름차순, 즉 자연 순서(natural order)로 정렬됩니다.
- 정렬된 키-값 쌍이 필요한 경우에 적합합니다.
HashMap vs TreeMap 주요 차이점 한눈에 보기
| 구분 | HashMap | TreeMap |
|---|---|---|
| 내부 구조 | 해시 테이블 | 레드-블랙 트리 |
| 시간 복잡도 | O(1) | O(log n) |
| null 키 | 1개 허용 | 허용하지 않음 |
| 정렬 여부 | 정렬하지 않음 | 오름차순(자연 순서) 정렬 |
| 순서 유지 | 유지하지 않음 | 정렬 순서 유지 |
| 키 비교 방식 | equals() | compareTo() |
| 구현 인터페이스 | Map, Cloneable, Serializable | NavigableMap, Cloneable, Serializable |
| 적합한 경우 | 빠른 조회·저장이 필요할 때 | 정렬된 데이터나 범위 검색이 필요할 때 |
정리: 어떤 것을 선택해야 할까?
성능이 최우선이고 데이터의 순서가 중요하지 않다면 HashMap이 좋은 선택입니다. 반면, 데이터를 항상 정렬된 상태로 유지하거나 firstKey(), tailMap() 같은 범위 조회 기능이 필요하다면 TreeMap이 더 적합합니다. 두 클래스의 특성을 정확히 이해하고 프로젝트의 요구 사항에 맞게 활용하시기 바랍니다.