기본기를 다지자/자료구조

[java] TreeMap

아. 이렇게 하면 될거 같은데.. 2025. 3. 27. 01:31
728x90

📌 TreeMap?

음.. Map을 공부하다 보니 TreeMap이란 것을 알게되었다. Tree랑 Map이 합쳐지다니 벌써부터 어떤 자료 구조인지 궁금하다. 알아보러 가자

 

역시 먼저 자바 DOC에서 TreeMap에 대한 설명을 확인해 보자

Treemap은 레드-블랙 트리를 기반으로 한 NavigableMap 구현체이다. 이 맵은 키의 자연 순서대로, 또는 맵 생성시 제공된 Comparator에 따라 정렬된다.
이 구현체는 containsKey, get, put, remove 연산에 대해 log(n) 시간 복잡도를 보장한다.
compareTo와 equals의 일관성을 유지해야한다. ( 두개의 키가 compareTo에 의해 같다고 판정되면, TreeMap 입장에서 이 두 키는 같다고 간주된다.

 

여기서 레드-블랙 트리라는 새로운 개념이 나오는데 레드-블랙 트리란 균형 잡힌 이진 탐색 트리로, 일정한 규칙을 통해 트리의 균형을 유지하고 효율적인 연산을 보장한다. O(log n)의 성능을 제공한다.

레드-블랙 트리는 내용이 많아. 추후에 따로 포스팅을 해야겠다.

 

✏️ 생성자

TreeMap()

기본 생성자로, 비어 있는 새로운 TreeMap을 생성한다.

 

TreeMap( Comparator<? super K> comparator )

주어진 Comparator를 사용하여 키를 정렬하는 새로운 빈 TreeMap을 생성한다.

 

TreeMap( Map<? extends K, ? extends V> m )

주어진 Map의 모든 항목을 포함하는 새로운 TreeMap을 생성한다.

 

TreeMap( SortedMap<K, ? extends V> m)

주어진 SortedMap을 복사하고, 그 정렬 순서를 그대로 사용하는 새로운 TreeMap을 생성한다.

 

 

📌 TreeMap 메서드

메서드 설명 반환 값
V put(K key, V value) 주어진 키와 값을 추가하거나, 해당 키가 이미 존재하면 값을 덮어 쓴다. 이전 값 또는 null 
V get(Object key) 지정된 키와 연관된 값을 반환한다. 값 또는 null
V remove(Object key) 주어진 키를 삭제하고, 대응되는 값을 반환한다 삭제된 값 또는 null
void clear() 모든 항목을 삭제한다 void
boolean containsKey(Object key) 주어진 키가 존재하는지 확인한다 true OR false
boolean containsValue(Object value) 주어진 값이 존재하는지 확인한다 true OR false
int size() 트리맵에 포함된 항목의 수를 반환한다 항목의 개수
boolean isEmpty() 트리맵이 비어있는지 확인한다 true OR false
Set<K> keySet() 모든 키를 정렬된 순서로 포함하는 Set을 반환한다 키들의 집합( Set )
Collection<V> values() 모든 값을 포함하는 Collection을 반환한다. 값들의 컬렉션 ( Collection )
Set<Map.Entry<K, V>> entrySet() 모든 키-값 쌍을 포함하는 Set을 반환한다. 키들의 집합
K firstKey() 첫 번째 (가장 작은) 키를 반환한다. 첫 번쨰 키
K lastKey() 마지막 (가장 큰) 키를 반환한다. 마지막 키
K higherKey(K key) 주어진 키보다 큰 가장 작은 키를 반환한다. 키 또는 null
K lowerKey(K key) 주어진 키보다 작은 가장 큰 키를 반환한다. 키 또는 null
K ceilingKey(K key) 주어진 키보다 큰 가장 작은 키를 반환한다. 키 또는 null
K floorKey(K key) 주어진 키보다 작은 가장 큰 키를 반환한다. 키 또는 null
Map.Entry<K, V> firstEntry() 주어진 키와 같거나 큰 가장 작은 키를 반환한다. 첫 번째 엔트리 또는 null
Map.Entry<K, V> lastEntry() 주어진 키와 같거나 작은 가장 큰 키를 반환한다. 마지막 엔트리 또는 null
Map.Entry<K, V> pollFirstEntry() 첫 번째 엔트릴를 반환한다 삭제된 첫 번쨰 엔트리
Map.Entry<K, V> pollLastEntry() 마지막 엔트리를 반환한다 삭제된 마지막 엔트리
NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) 주어진 범위 내의 엔트리를 포함하는 NavigableMap을 반환합니다. 부분맵
NavigableMap<K, V> headMap(K toKey, boolean inclusive) 주어진 키까지의 엔트리를 포함하는 NavigableMap을 반환한다. 부분 맵
NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) 주어진 키부터의 엔트리를 포함하는 NavigableMap을 반환한다. 부분 맵

 

📌 TreeMap 사용

 

TreeMap과 HashMap의 차이점 부터 확인해 보자

        TreeMap<Integer, String> map2 = new TreeMap<>();
        map2.put(1, "Apple");
        map2.put(38, "Banana");
        map2.put(29, "Orange");
        map2.put(52, "Grapes");
        map2.put(14, "Strawberry");
        System.out.println("TreeMap: " + map2);

        Map<Integer, String> map3 = new HashMap<>();
        map3.put(1, "Apple");
        map3.put(38, "Banana");
        map3.put(29, "Orange");
        map3.put(52, "Grapes");
        map3.put(14, "Strawberry");
        System.out.println("HashMap: " + map3);

 

[결과]

TreeMap: {1=Apple, 14=Strawberry, 29=Orange, 38=Banana, 52=Grapes}
HashMap: {1=Apple, 52=Grapes, 38=Banana, 29=Orange, 14=Strawberry}

 

결과를 보면 TreeMap은 정렬이 되어서 나오고 HashMap은 정렬이 안되어서 나온다. 시간적으로는 괜찮은가? 확인해 보자

 

        TimeCheck timer = new TimeCheck();

        timer.start();

        // 596221000
//        Map<Integer, String> map = new HashMap<>();

        // 1270982291
        TreeMap<Integer, String> map = new TreeMap<>();

        for(int i = 0; i < 10_000_000; i++) {
            map.put(i, "String" + i);
        }

        timer.stop();

        System.out.println(timer.getElapsedTimeInNano());

 

천만번의 put연산 결과 HashMap은 596,221,000 나노초가 걸렸고, TreeMap은 1,270,982,291 나노초가 걸렸다. 약 2배 정도 차이가 나는 것 같다. TreeMap은 내부 정렬을 계속 해서 시간이 더 걸리는것 같다.

 

Get연산도 시험해 봤는데 HashMap은 97,242,958 나노초, TreeMap은 629,957,458나노초가 걸렸다 Get연산 역시 TreeMap이 시간이 더 많이 걸리는것 같았다.

 

이유를 찾아보았다.

HashMap은 데이터를 해시 테이브레 저장하여 대부분의 경우 헤시 태이블에서 O(1) 시간 복잡도롤 데이터를 검색, 삽입, 삭제한다. 하지만 TreeMap의 경우 레드-블랙 트리로 데이터를 저장하여 삽입, 삭제, 검색 모두 O(log n)의 시간 복잡도를 가진다.

 

결론적으로 HashMap은 순서유지가 필요없을때 적합하고, TreeMap은 순서유지가 필요할때 적합하다.

📌 느낀점

요번에 처음으로 TreeMap에 대해 공부를 해봤는데 레드-블랙 트리라는 거대한 산을 또 마주쳐서 빨리 알아 보고 싶다. 레드-블랙 트리 까지 학습해야 TreeMap을 완벽히 이해할 수 있을 것 같다.

 

728x90
반응형