[Java] SortedMap

출처

ChatGPT

---

 

SortedMap은 자바의 Map 인터페이스를 확장한 인터페이스로, 정렬된 키-값 쌍을 저장하는 맵이다. SortedMap은 키를 기준으로 정렬된 상태로 데이터를 유지하며, 삽입, 삭제 검색 시 항상 이 정렬 상태가 유지된다.

 

1. SortedMap의 주요 특징

키 기반 정렬

SortedMap은 키를 기준으로 항상 정렬된 상태로 데이터를 저장한다. 기본적으로 키의 자연 순서(Natural Ordering)에 따라 정렬되며, Comparator를 제공하면 사용자 정의 순서로 정렬할 수 있다.

중복된 키 불허

SortedMap은 중복된 키를 허용하지 않으며, 동일한 키가 삽입되면 기존 값을 덮어쓴다.

null 키 허용 여부

SortedMap의 구현체에 따라 다르지만, 일반적으로 null 키는 허용되지 않는다. 예를 들어, TreeMap은 null 키를 허용하지 않는다.

정렬된 맵의 범위 조회

SortedMap은 키의 범위를 지정하여 특정 범위의 데이터를 쉽게 조회할 수 있는 메소드를 제공한다.

 

2. SortedMap의 주요 메소드

SortedMap 인터페이스는 다음과 같은 중요한 메소드를 제공한다.

1. 범위 조회 메소드

1. subMap(K fromKey, K toKey)

주어진 두 키 사이의 범위에 해당하는 서브맵을 반환한다. 시작 키는 포함되고, 끝 키는 포함되지 않느다.

2. headMap(K toKey)

주어진 키보다 작은 모든 키-값 쌍을 포함하느 서브맵을 반환한다.

3. tailMap(K fromKey)

주어진 키보다 큰 모든 키-값 쌍을 포함하는 서브맵을 반환한다.

 

이 메소드들은 특정 범위에 속한 데이터만을 가져와 작업할 때 매우 유용하다.

2. 정렬된 맵의 기본 메소드

1. firstKey()

맵에서 가장 작은 키를 반환한다.

2. lastKey()

맵에서 가장 큰 키를 반환한다.

 

이 메소드들은 맵의 첫 번째 또는 마지막 키를 빠르게 찾을 수 있게 해준다.

3. 정렬 기준 제공 메소드

1. comparator()

맵이 사용하는 Comparator를 반환한다. 만약 맵이 기본 자연 순서를 따르는 경우, null을 반환한다.

 

이 메소드를 통해 SortedMap이 어떤 기준으로 키를 정렬하는지 확인할 수 있다.

 

3. SortedMap을 구현한 클래스

TreeMap

SortedMap의 대표적인 구현첼로, 레드-블랙 트리 기반의 이진 탐색 트리이다. TreeMap은 항상 키를 정렬된 상태로 유지하며, SortedMap과  NavigableMap의 모든 기능을 제공한다.

• 관련 글 -> [자료 구조] 레드-블랙 트리 Red-Black Tree

 

4. SortedMap의 주요 메소드 사용 예시

다음은 TreeMap을 사용해 SortedMap의 주요 메소드를 사용하는 간단한 예시이다.

import java.util.*;

public class SortedMapExample {
    public static void main(String[] args) {
        // TreeMap을 통해 SortedMap 구현
        SortedMap<String, Integer> sortedMap = new TreeMap<>();

        // TreeMap에 키-값 쌍 추가
        sortedMap.put("apple", 10);
        sortedMap.put("banana", 20);
        sortedMap.put("cherry", 30);
        sortedMap.put("date", 40);
        sortedMap.put("elderberry", 50);

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

        // 특정 범위의 서브맵
        SortedMap<String, Integer> subMap = sortedMap.subMap("banana", "date");
        System.out.println("\nSubMap from 'banana' to 'date': " + subMap);

        // headMap (주어진 키보다 작은 키-값 쌍들)
        SortedMap<String, Integer> headMap = sortedMap.headMap("cherry");
        System.out.println("\nHeadMap up to 'cherry': " + headMap);

        // tailMap (주어진 키보다 큰 키-값 쌍들)
        SortedMap<String, Integer> tailMap = sortedMap.tailMap("cherry");
        System.out.println("\nTailMap from 'cherry': " + tailMap);
    }
}

 

출력 결과

First key: apple
Last key: elderberry

SubMap from 'banana' to 'date': {banana=20, cherry=30}

HeadMap up to 'cherry': {apple=10, banana=20}

TailMap from 'cherry': {cherry=30, date=40, elderberry=50}

 

• firstKey()와 lastKey()  : 가장 작은 키와 가장 큰 키를 반환한다.
• subMap() : 특정 키의 범위에 해당하는 서브맵을 반환한다. 이 예시에서는 "banana"에서 "date"까지의 범위를 지정해 서브맵을 반환했다. "data"는 포함되지 않았다.
• haedMap() : 주어진 키보다 작은 키-값 쌍으로 이루어진 맵을 반환한다.
• tailMap() : 주어진 키보다 큰 키-값 쌍으로 이루어진 맵을 반환한다.

 

5. SortedMap의 활용

SortedMap은 정렬된 데이터를 다루거나 범위 기반 조회가 필요한 경우에 매우 유용하다. 키가 항상 정렬된 상태로 저장되므로, 데이터의 순서를 보장해야 하는 작업에 적합하다.

1. 범위 조회

예를 들어, 날짜를 키로 사용하여 특정 날짜 범위의 데이터를 조회하는 경우, SortedMap의 subMap(), headMap(), tailMap() 메소드를 사용해면 쉽게 범위 기반 데이터를 조회할 수 있다.

2. 최소/최대 값 처리

SortedMap은 항상 정렬된 상태를 유지하므로, 가장 작은 값 도는 가장 큰 값을 빠르게 찾아낼 수 있다. firstKey()와 lastKey() 메소드는 최소값과 최대값을 처리할 때 유용하다.

3. 이진 탐색 기반 작업

SortedMap은 키를 기준으로 정렬된 상태를 유지하므로, 이진 탐색과 같은 성능 최적화 작업에도 유리하다. 특히 대규모 데이터를 다룰 때 효율적으로 사용할 수 있다.

 

6. SortedMap과 Map의 차이점

특징	Map	SortedMap
정렬	키의 순서가 유지되지 않음	키가 항상 정렬된 상태로 유지됨
범위 기반 조회	제공되지 않음	subMap(), headMap(), tailMap() 메소드 제공
최소/최대 값 처리	firstKey()와 lastKey() 없음	firstKey(), lastKey() 제공
기본 구현채	HashMap, Hashtable등	TreeMap

 

7. 정렬 기준

SortedMap은 키의 자연 순서에 따라 정렬되거나, 사용자 정의 정렬 기준(Comparator)을 제공하여 정렬할 수 있다.

1. 자연 순서

키가 Comparable을 구현한 경우, SortedMap은 기본적으로 자연 순서에 따라 정렬이 된다. 예를 들어, Integer, String, Double과 같은 타입은 Comparable 인터페이스를 구현하고 있으므로, 기본적으로 오름차순으로 정렬된다.

2. 사용자 정의 정렬

사용자가 Comparator를 제공하면, 해당 정렬 기준에 따라 키를 정렬할 수 있다. 다음은 Comparator를 사용한 TreeMap의 예시이다.

import java.util.*;

public class CustomSortedMapExample {
    public static void main(String[] args) {
        // 키를 내림차순으로 정렬하는 Comparator를 가진 TreeMap 생성
        Comparator<String> comparator = (s1, s2) -> s2.compareTo(s1);
        SortedMap<String, Integer> sortedMap = new TreeMap<>(comparator);

        // TreeMap에 키-값 쌍 추가
        sortedMap.put("apple", 10);
        sortedMap.put("banana", 20);
        sortedMap.put("cherry", 30);
        sortedMap.put("date", 40);
        sortedMap.put("elderberry", 50);

        // TreeMap 출력 (내림차순으로 정렬됨)
        System.out.println("TreeMap with custom comparator: " + sortedMap);
    }
}

 

출력 결과

TreeMap with custom comparator: {elderberry=50, date=40, cherry=30, banana=20, apple=10}

 

8. 결론

SortedMap은 키를 기준으로 항상 정렬된 상태로 데이터를 유지하는 맵 인터페이스이다. TreeMap이 그 대표적인 구현체이며, 자연 순서 또는 사용자 정의 정렬 기준에 따라 데이터를 정렬할 수 있다. 또한 SortedMap은 범위 조회와 같은 고급 기능을 제공하여, 대규모 데이터를 효율적으로 관리할 수 있도록 돕는다.