Java/Java이론

TreeMap: 정렬된 키-값 저장을 위한 Java Map

P_eli 2024. 11. 19. 16:47
728x90
반응형

TreeMap은 Java에서 제공하는 Map 인터페이스를 구현한 클래스 중 하나로, 키가 정렬된 순서로 저장되는 특징을 가지고 있습니다. 이는 데이터의 정렬 상태를 유지해야 하거나, 정렬된 상태로 데이터를 탐색해야 하는 경우 매우 유용합니다. TreeMap은 내부적으로 레드-블랙 트리라는 이진 탐색 트리 자료구조를 사용하여 데이터를 저장하므로, 항상 오름차순 정렬 상태를 유지합니다.

 

TreeMap의 주요 특징

1. 정렬된 데이터 저장

TreeMap은 키를 자연 정렬(Natural Ordering)하거나 사용자가 제공한 Comparator에 따라 정렬된 상태로 저장합니다. 따라서 데이터가 정렬된 상태로 필요할 때 별도의 추가 정렬 과정 없이 빠르게 데이터를 처리할 수 있습니다.

2. 레드-블랙 트리 기반

TreeMap은 레드-블랙 트리로 구현되어 있으며, 이는 자기 균형 이진 탐색 트리의 일종입니다. 이 구조 덕분에 삽입, 삭제, 검색 작업에서 O(log n)의 시간 복잡도를 가집니다.

3. 중복 키 허용 안 함

다른 Map과 마찬가지로, TreeMap은 각 키가 유일해야 합니다. 동일한 키로 데이터를 삽입하면 이전 값이 덮어씌워집니다.

4. null 키 제한

TreeMap은 키로 null 값을 허용하지 않습니다. 이는 키의 정렬을 위해 비교 연산이 필요한데, null 값은 이러한 연산에서 예외를 발생시키기 때문입니다.

5. 유용한 메서드 제공

TreeMap은 특정 범위의 데이터를 가져오는 데 유용한 메서드를 제공합니다.

  • subMap(fromKey, toKey): 지정된 범위의 서브 맵 반환
  • headMap(toKey): 특정 키보다 작은 모든 엔트리 반환
  • tailMap(fromKey): 특정 키 이상인 모든 엔트리 반환
  • firstKey(), lastKey(): 가장 작은/큰 키 반환

 

TreeMap의 사용 사례

1. 정렬된 데이터 필요

TreeMap은 데이터가 정렬된 상태로 필요할 때 적합합니다. 예를 들어, 성적 순위, 날짜별 거래 기록 등과 같은 데이터를 처리할 때 유용합니다.

2. 범위 기반 탐색

특정 범위의 데이터를 효율적으로 탐색해야 하는 경우 TreeMap을 사용할 수 있습니다. 예를 들어, 날짜 범위에 해당하는 거래 내역을 조회하거나, 특정 점수 이상을 받은 학생 목록을 가져오는 경우입니다.

3. 데이터베이스 인덱스 시뮬레이션

TreeMap은 데이터베이스 테이블의 인덱스를 메모리 상에서 구현하는 데 적합합니다. 키를 테이블의 기본 키로, 값을   데이터 행으로 매핑하면 정렬된 데이터를 쉽게 탐색할 수 있습니다.

 

TreeMap 사용법

다음은 TreeMap을 활용한 간단한 예제입니다.

import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        // TreeMap 생성
        TreeMap<Integer, String> map = new TreeMap<>();
        
        // 데이터 삽입
        map.put(2, "two");
        map.put(1, "one");
        map.put(3, "three");

        // 정렬된 상태로 출력
        System.out.println("TreeMap: " + map);

        // 첫 번째와 마지막 키
        System.out.println("First Key: " + map.firstKey());
        System.out.println("Last Key: " + map.lastKey());

        // 특정 키 이상의 데이터 가져오기
        System.out.println("Tail Map (from 2): " + map.tailMap(2));

        // 특정 범위의 데이터 가져오기
        System.out.println("Sub Map (1 to 3): " + map.subMap(1, 3));
    }
}

 

출력 결과

 

TreeMap을 사용할 때 주의할 점

  1. null 키 불가
    • TreeMap은 키로 null 값을 허용하지 않으므로, 키가 null일 가능성이 있다면 다른 Map(예: HashMap)을 고려해야   합니다.
  2. 삽입 순서 보존되지 않음
    • 데이터는 항상 키 기준으로 정렬되므로, 삽입 순서를 유지하려면 LinkedHashMap을 사용해야 합니다.
  3. 성능
    • 레드-블랙 트리를 사용하므로 O(log n)의 시간 복잡도를 가지지만, 이는 HashMap의 평균 시간 복잡도 O(1)보다는   느릴 수 있습니다. 정렬이 필요 없는 경우 HashMap이 더 효율적입니다.

 

TreeMap과 다른 Map 비교

특징 TreeMap HashMap LinkedHashMap
정렬 여부 키 기준으로 정렬됨 정렬되지 않음 삽입 순서 유지
null 키 허용 안 함 1개의 null 키 허용 1개의 null 키 허용
시간 복잡도 O(log n) O(1) (평균) O(1) (평균)
구조 레드-블랙 트리 기반 해시 테이블 기반 해시 테이블 + 링크드 리스트

 

TreeMap은 정렬된 데이터가 필요하거나 특정 범위의 데이터 조회가 자주 필요한 경우에 매우 강력한 도구입니다. 하지만 정렬이 불필요한 경우에는 HashMap 또는 LinkedHashMap이 더 효율적일 수 있으니, 사용 사례에 맞게 선택하세요!

728x90
반응형