728x90
HashMap 과 TreeMap 의 차이를 알게 되었음.
🛠 HashMap vs TreeMap 상세 비교
HashMap과 TreeMap은 Java의 Map 인터페이스를 구현하는 대표적인 클래스야.
둘 다 키-값(Key-Value) 형태의 데이터 저장이 가능하지만, 내부 동작 방식과 성능 차이가 커.
1️⃣ HashMap과 TreeMap의 차이점 요약
HashMap vs TreeMap
데이터 저장 방식 | 해시 테이블(Hash Table) 사용 | 레드-블랙 트리(Red-Black Tree) 사용 |
정렬 여부 | 순서 보장 X (무작위 순서) | Key 값을 기준으로 자동 정렬 (오름차순, Comparator 가능) |
검색 속도 | 평균 O(1), 최악 O(n) | O(log n) |
삽입/삭제 속도 | 평균 O(1), 최악 O(n) | O(log n) |
Key 기준 정렬 가능 여부 | ❌ 불가능 | ✅ 가능 |
Key에 null 허용 여부 | ✅ 가능 (1개만) | ❌ 불가능 |
Thread-Safe 여부 | ❌ (동기화 X) | ❌ (동기화 X) |
사용 예시 | 빠른 검색/조회가 필요할 때 (캐싱, 데이터 매핑) | Key 정렬이 필요한 경우 (정렬된 데이터 저장) |
2️⃣ HashMap 상세 설명
🔹 특징
- HashMap은 **해시 테이블(Hash Table)**을 기반으로 동작
- 키(Key)의 hashCode()를 기반으로 **버킷(Bucket)**에 데이터를 저장
- 키(Key)의 순서를 보장하지 않음 (랜덤한 순서로 저장)
- 검색 속도는 평균 O(1), 충돌이 많으면 최악의 경우 O(n)
🔹 기본 코드
import java.util.HashMap;
public class HashMapExample {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
// 데이터 추가 (put)
map.put("Apple", 100);
map.put("Banana", 200);
map.put("Cherry", 300);
// 데이터 가져오기 (get)
System.out.println("Apple의 값: " + map.get("Apple")); // 100
// Key 존재 여부 확인 (containsKey)
System.out.println("Banana 존재? " + map.containsKey("Banana")); // true
// 모든 Key-Value 출력
for (String key : map.keySet()) {
System.out.println(key + " -> " + map.get(key));
}
}
}
🔹 내부 동작 (해싱)
- Key의 hashCode()를 계산하여 해시 값 생성
- 해시 값을 기반으로 배열 인덱스(버킷) 결정
- 동일한 해시 값이 있으면 체이닝(Linked List) 또는 트리(Tree) 구조로 충돌 해결
- get() 호출 시, 동일한 해시 값을 가진 Key들 중에서 equals()로 정확한 Key를 찾음
map.put("Apple", 100);
- "Apple".hashCode() → 1253874
- 해시 값을 N개의 버킷으로 매핑 (1253874 % N)
- 해당 버킷에 (Key: Apple, Value: 100) 저장
🔹 장점 & 단점
✔ 장점
- 빠른 검색 속도 (O(1))
- Key 값에 null 사용 가능
❌ 단점
- Key 값 정렬이 불가능
- 충돌 발생 시 성능 저하 가능 (O(n))
- hashCode() 충돌이 많으면 성능 저하
3️⃣ TreeMap 상세 설명
🔹 특징
- 내부적으로 레드-블랙 트리(Red-Black Tree) 사용
- Key 값을 기준으로 자동 정렬됨 (기본: 오름차순 정렬)
- 검색, 삽입, 삭제 연산 속도는 O(log n)
- null을 Key로 사용할 수 없음
- 범위 검색(예: 특정 범위의 Key 조회)에 적합
🔹 기본 코드
import java.util.TreeMap;
public class TreeMapExample {
public static void main(String[] args) {
TreeMap<String, Integer> treeMap = new TreeMap<>();
// 데이터 추가
treeMap.put("Banana", 200);
treeMap.put("Apple", 100);
treeMap.put("Cherry", 300);
// 자동 정렬된 Key 확인
System.out.println(treeMap);
// 출력: {Apple=100, Banana=200, Cherry=300}
// 특정 Key보다 큰 값 가져오기 (higherKey)
System.out.println("Banana보다 큰 Key: " + treeMap.higherKey("Banana")); // Cherry
// 가장 작은 Key 가져오기 (firstKey)
System.out.println("가장 작은 Key: " + treeMap.firstKey()); // Apple
}
}
🔹 내부 동작 (레드-블랙 트리)
- 새로운 Key가 삽입되면 트리에 추가 후 자동 정렬
- 트리 균형을 유지하기 위해 Rebalancing (좌/우 회전) 실행
- get() 호출 시, 트리를 탐색하면서(O(log n)) Key를 찾음
treeMap.put("Banana", 200);
treeMap.put("Apple", 100);
treeMap.put("Cherry", 300);
🔹 장점 & 단점
✔ 장점
- Key가 자동 정렬됨 (오름차순)
- higherKey(), lowerKey() 등을 이용한 범위 검색 가능
- 검색 속도가 안정적 (O(log n))
❌ 단점
- HashMap보다 성능이 낮음 (O(log n) vs O(1))
- Key에 null을 사용할 수 없음
- 메모리 사용량이 높음 (트리 구조 유지 필요)
4️⃣ HashMap vs TreeMap 성능 비교
import java.util.*;
public class MapPerformanceTest {
public static void main(String[] args) {
Map<Integer, Integer> hashMap = new HashMap<>();
Map<Integer, Integer> treeMap = new TreeMap<>();
int dataSize = 1_000_000;
Random random = new Random();
// HashMap 성능 테스트
long start = System.nanoTime();
for (int i = 0; i < dataSize; i++) {
hashMap.put(random.nextInt(), i);
}
long end = System.nanoTime();
System.out.println("HashMap 삽입 시간: " + (end - start) / 1_000_000 + " ms");
// TreeMap 성능 테스트
start = System.nanoTime();
for (int i = 0; i < dataSize; i++) {
treeMap.put(random.nextInt(), i);
}
end = System.nanoTime();
System.out.println("TreeMap 삽입 시간: " + (end - start) / 1_000_000 + " ms");
}
}
➡ 결과: HashMap이 TreeMap보다 3~5배 빠름
5️⃣ 언제 사용해야 할까?
✅ HashMap
- 빠른 검색, 삽입, 삭제(O(1))가 필요할 때
- Key 순서가 중요하지 않은 경우
- 데이터가 많고 성능이 중요한 경우
✅ TreeMap
- Key가 정렬된 상태로 유지되어야 할 때
- **범위 검색(최소/최대 값 조회, 특정 구간 데이터 검색)**이 필요할 때
- Key의 순서를 유지하면서 삽입할 때
📌 결론
- 빠른 속도가 필요하면 HashMap
- Key 정렬이 필요하면 TreeMap
- O(1) vs O(log n)의 차이를 잘 고려해서 선택! 🚀
그래서 위와 같이 정리를 해보았는데 내가 했던 부분들을 예시로 한번 살펴보자 !!
우선 HashMap 을 사용한다면

위의 사진처럼 entrySet 을 돌릴때 만약 키값이 "1", "2", "3", "4" .. 이런식의 숫자 스트링이라고 한다면 순서보장이 되질 않아 어쩔땐 4번이 첫번째가 될 수 있고 2번이 첫번째가 될 수 있음.
그래서 만약 순서보장을 해야한다면 밑의 사진처럼 TreeMap 으로 구성해야 순서를 보장받을 수 있음.

단, HashMap 과의 차이중 하나더 설명하자면, 속도가 HashMap 이 더 빠르고 TreeMap 이 좀 더 느리는 단점이 있으니 만약 데이터 구조가 클 경우 HashMap 을 사용해서 순서보장하거나 TreeMap 을 좀 더 최적화 시켜야 할 것 같음.

'Java' 카테고리의 다른 글
Java_ 지역변수 , 인스턴스 변수 차이 (0) | 2024.09.12 |
---|---|
Java & Swift _ runOnUiThread , view.post , handler, DispatchQueue.... 의 차이 (0) | 2024.09.12 |
Java_ Rxjava blockingGet , subscribe ... (0) | 2024.08.25 |
Java_ Lazy Singleton (0) | 2024.08.25 |
AOS - Rxjava3 , Single , Disposable (0) | 2024.06.23 |