본문 바로가기
Java

AOS_ HashMap 과 TreeMap 의 차이

by JunsC 2024. 3. 4.
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));
        }
    }
}

🔹 내부 동작 (해싱)

  1. Key의 hashCode()를 계산하여 해시 값 생성
  2. 해시 값을 기반으로 배열 인덱스(버킷) 결정
  3. 동일한 해시 값이 있으면 체이닝(Linked List) 또는 트리(Tree) 구조로 충돌 해결
  4. 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
    }
}

🔹 내부 동작 (레드-블랙 트리)

  1. 새로운 Key가 삽입되면 트리에 추가 후 자동 정렬
  2. 트리 균형을 유지하기 위해 Rebalancing (좌/우 회전) 실행
  3. 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 을 좀 더 최적화 시켜야 할 것 같음.

 

"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."