컨텐츠 바로가기

java.util.TreeMap 분석

http://iilii.egloos.com/4537561

지난 시간에 썼던 java.util.HashMap 분석과 이어지는 내용입니다. 안 읽으셨다면 먼저 읽으시기 바랍니다.

TreeMap은 keySet()으로 키 데이터 키의 Set을 가져올 때, 정렬된 상태로 가져옵니다. red-black tree로 구현이 되어있습니다. red-black tree는 정렬 알고리즘 중에서 일반적으로 가장 빠른 성능을 보이는 알고리즘입니다.

모든 정렬 알고리즘은 2개의 elemenet를 비교하는 것으로 정렬을 합니다. 그럼 "두 element를 어떻게 비교할 것인가?"에 대해서 java api는 두 가지 방법을 제공합니다. java.lang.Comparable과 java.util.Comparator 입니다. TreeMap의 주요 생성자는 TreeMap()과 TreeMap(Comparator)가 있습니다. 전자는 Key타입에 대해 Comparable을 이용하고, 후자는 받은 Comparator를 이용해서 element를 정렬합니다. Comparable과 Comparator는 잠시 후에 자세히 다루겠습니다.

Map으로써의 성능은 HashMap보다 일반적으로 떨어집니다. 하지만, rehashing 작업이 없어서, 어느 순간 갑자기 부하가 급증하는 일은 발생하지 않습니다.

HashMap과 마찬가지로 동기화 처리는 되어있지 않습니다.(method가 synchronized로 처리되지 않았다는 뜻입니다.) 따라서 여러 개의 쓰레드에서 동시에 접근할 일이 있을 경우에는 Collections.synchronizedMap 을 이용해야 합니다.

자~~ 이제 Comparable과 Comparator에 대해서 얘기 해봅시다. 
Comparable은 int를 리턴하는 compareTo(T o) 라는 메쏘드만 하나 있습니다. T는 generics에 의해 정의된 타입입니다. a와 b를 비교한다면, a.compareTo(b)와 같이 합니다.Comparator는 두 개를 모두 인자로 받는 compare(T o1, T o2)가 있습니다. SomeComparator.compare(a, b)와 같이 호출하게 됩니다. 둘 모두 뭔가를 비교하는 의미를 가지고 있으며,  순서상 a가 b보다 앞이면, -값을 같으면 0을 뒤면 +를 리턴합니다. -몇인지 +몇인지는 중요하지 않습니다. (그래서 -1,0,+1 3가지 중 하나만 리턴하는 경우도 많습니다.) Comparable.compareTo나 Comparator.compare가 0을 리턴한다는 것은 반드시 equals에 대해서도 true를 리턴한다는 것은 아닙니다. ( 여기에 참고자료가 있습니다.)

일반적으로는 Comparable을 더 많이 쓰게 됩니다. 우리가 아는 정렬이나 비교 등이 필요할 것 같은 대부분의 클래스들은 Comparable을 implement합니다. (String 같은 게 대표적이죠.)

Comparator를 쓰는 이유는 일반적으로 두 가지입니다. 첫 번째는 비교하고자 하는 클래스가 Comparable을 구현하지 않은 경우 입니다. 기존에 이미 구현된 클래스를 수정하지 않고 비교 기능을 추가 할 수 있습니다. 두 번째는 비교 방식을 다르게 하고자 할 때입니다. 예를 들어, 순서를 거꾸로 하여 정렬하고 싶다거나, 영어와 한글이 섞여 있는 Collection에서 한글을 영어보다 앞에 나오도록 하는 경우 등이 있겠습니다.

Comparator를 가지고 할 수 있는 좀 더 재밌는 예가 있습니다. 다음은 이름-점수 로 되어있는 데이터를 점수 기준으로 정렬하는 예입니다.

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class Test {
    public static void main(String[] args) {
       Map<String, Integer> data = new HashMap<String, Integer>();
       data.put("철희", 70);
       data.put("영희", 80);
       data.put("영수", 85);
       data.put("철수", 70);
      
       ValueComparator<String, Integer> comparator = new ValueComparator<String, Integer>(data);
      
       TreeMap<String, Integer> sorted = new TreeMap<String, Integer>(comparator );
       sorted.putAll(data);
       System.out.println(sorted);

       TreeMap<String, Integer> reverse = new TreeMap<String, Integer>(new ReverseComparator<String>(comparator));
       reverse.putAll(data);
       System.out.println(reverse);
      
    }

    private static class ValueComparator<K extends Comparable<K>, V extends Comparable<V>> 
        implements Comparator<K>{
        private Map<K, V> map;
        ValueComparator(Map<K, V> map) {
            this.map = map;
        }
        public int compare(K o1, K o2) {
            int p = map.get(o1).compareTo(map.get(o2));
            if (p != 0) {
                return p;
            }
            return o1.compareTo(o2);
        }
    }
   
    private static class ReverseComparator<T> implements Comparator<T>{
        private Comparator<T> comparator;
        ReverseComparator(Comparator<T> comparator) {
            this.comparator = comparator;
        }
        public int compare(T o1, T o2) {
            return -1 * comparator.compare(o1, o2);
        }
    }
}

=========== 실행 결과 =================
{철수=70, 철희=70, 영희=80, 영수=85}
{영수=85, 영희=80, 철희=70, 철수=70}


일반적인 정렬은 key를 기준으로 하지만 위의 예제에서 사용된 ValueComparator는 value를 기준으로 정렬할 수 있는 방법을 제공합니다. (이 코드의 메모리상 효율성은 떨어집니다만 일단 무시하죠.) ValueComparator가 map의 모든 데이터를 가지고 있기 때문에 value를 기준으로 정렬할 수 있는 방법을 제공합니다.
ReverseComparator는 정렬 방식을 무조건 반대로 바꿉니다.


덧글|덧글 쓰기|신고