[Java] 알아두면 쓸모있는 정렬된 Map - SortedMap(feat. TreeMap)

자바에서 제공하는 Map<K, V>은 인터페이스입니다.

그렇기 때문에 자바에서는 Map 인터페이스를 구현한 클래스도 다양하게 제공하고 있는데요.

대표적으로 가장 많이 사용되는 HashMap이나 순서를 유지하는 LinkedHashMap, 멀티 쓰레드 환경에서 동시성을 보장하는 ConcurrentHashMap 등이 있습니다.

 

이번 포스팅에서는 이렇듯 다양한 Map 중에서도 특별히 Key 값에 따라 정렬이 되는 Map인 SortedMap에 대해 다뤄보도록 하겠습니다.

 

interface SortedMap<K, V> extends Map<K, V>

SortedMap은 Map 인터페이스를 상속합니다.

그렇기 때문에 SortedMap을 구현하는 클래스는 Map 인터페이스에서 제공하는 모든 메소드도 모두 구현해야 합니다.

잠시 뒤에 살펴볼 TreeMap이 그 예라고 할 수 있습니다.

 

SortedMap은 key의 값이 Integer, Double 등과 같이 비교 가능한(Comparable) 타입이거나, SortedMap을 생성하는 시기에 별도의 Comparator를 등록해서 정렬할 수 있습니다.

다시 정리하자면, Map의 Key가 정렬되기 위해서는

1.  Key가 Comparable 인터페이스를 구현한다.
2.  Map 인스턴스 생성 단계에 Comparator 구현객체를 등록한다.

그리고 이때 유지되는 Key 순서는 Map이 지니는 entrySet(), entrySet(), values() 메소드를 통해 생성되는 Collection에도 반영됩니다.

 

생성자(Constructor)

일반적으로 SortedMap 구현 객체(ex: TreeMap)는 다음과 같은 생성자를 갖습니다.

1. No Arguments 생성자
   - Key가 Comparable 인터페이스를 구현하고 있어, 그에따라 자연스럽게 정렬되는 Map을 생성합니다.
2. Comparator 구현 객체를 파라미터로 갖는 생성자
   - 정렬의 기준이 되는 Comparator를 등록하여 이에따라 정렬되는 Map을 생성합니다.
3. Map 객체를 파라미터로 갖는 생성자
   - 주어진 Map의 요소들(Comparable 인터페이스가 구현된 Key)을 가지고 SortedMap을 생성합니다.
4. SortedMap 객체를 파라미터로 갖는 생성자
   - 주어진 SortedMap의 요소들과 동일한 값과 순서를 갖는 새로운 SortedMap을 생성합니다.
   - Copy의 기능을 한다고 보시면 됩니다.

물론, 어디까지나 권고사항일 뿐입니다. SortedMap은 인터페이스이기 때문에 구현객체에게 생성자를 강제할 수는 없습니다.

 

대표적인 SortedMap 구현 클래스 -> TreeMap

TreeMap은 가장 잘 알려진 SortedMap 구현 클래스입니다.(정확하게는 SortedMap 인터페이스를 상속한 NavigableMap을 구현합니다.)

그럼 TreeMap을 통해서 위에서 언급한 생성자들을 사용해 인스턴스를 생성해보겠습니다.

 

1. No Arguments 생성자

public static void main(String[] args) {
    SortedMap<String, Integer> map = new TreeMap<>();
    map.put("banana", 50);
    map.put("cocoa", 90);
    map.put("avocado", 10);
    
    map.keySet().forEach(key -> {
        System.out.println(key + " -> " + map.get(key));
    });
}

avocado -> 10
banana -> 50
cocoa -> 90

이 경우, Key 타입인 String이 Comparable 인터페이스를 구현하고 있기 때문에 위와 같이 정렬된 결과를 가져왔습니다.

 

2. Comparator 구현 객체를 파라미터로 갖는 생성자

이번에는 Comparator를 생성자의 인자로 넘겨서 생성해보겠습니다.

Comparator 인터페이스의 구현 객체를 람다식으로 넘기도록 하겠습니다.

public static void main(String[] args) {
    SortedMap<String, Integer> map = new TreeMap<>((s1, s2) -> s1.length() - s2.length());
    map.put("banana", 50);
    map.put("cocoa", 90);
    map.put("avocado", 10);
    
    map.keySet().forEach(key -> {
        System.out.println(key + " -> " + map.get(key));
    });
}

cocoa -> 90
banana -> 50
avocado -> 10

위 코드는 String의 길이에 따라 오름차순으로 정렬할 수 있도록 Comparator를 구현한 예제입니다.

결과는 문자열의 길이가 가장 짧은 cocoa 에서 가장 긴 avocado 순으로 정렬되었음을 확인할 수 있습니다.

 

SortedMap methods

Map 인터페이스와 비교해서 SortedMap에서 추가적으로 제공하는 메소드들을 살펴보겠습니다.

1. Comparator comparator()
   - SortedMap에 등록된 Comparator가 있으면 해당 인스턴스를 리턴하고, 별도로 등록된게 없으면 null을 리턴합니다.
2. K firstKey()
   - 첫번째 Key를 리턴합니다. 오름차순의 경우 가장 작은 값(lowest)을 리턴합니다.
3. K lastKey()
   - 마지막 Key를 리턴합니다. 오름차순의 경우 가장 큰 값(highest)을 리턴합니다.
4. SortedMap headMap(K toKey)
   - 인자로 받은 toKey 보다 작은 Key들을 가지고서 부분적인 Map을 리턴합니다.
5. sortedMap tailMap(K fromKey)
   - 인자로 받은 fromKey 보다 큰 Key들을 가지고서 부분적인 Map을 리턴합니다.

 

---

Java에서 Map은 굉장히 유용한 자료구조 중 하나입니다.

가장 많이 쓰이는 구현 클래스는 HashMap입니다만, 이외에도 다양한 Map 클래스들이 있기 때문에 많은 Map의 종류를 최대한 숙지하여 적재적소에 사용한다면 보다 효율적인 프로그래밍을 할 수 있을 것입니다.