[Java 가지고놀기] Java Map 정리(3) - TreeMap

callme.waffle·2024년 9월 19일

Java 가지고놀기

목록 보기
11/18

1. 개요

Java 문법을 복습하며 Collection 구현체들을 정리하던 중 Set의 구현체 다수에서 Map을 사용하는 것을 확인하였습니다.
Map에 대한 지식없이 Set 구현체를 이해하는 것에 어려움이 있어 관련내용을 공부하며 정리하였습니다.

#Reference

2. Map이란?

Key-Value 쌍으로 이루어진 자료형

Map은 Key와 Value를 각각 한쌍으로 묶어 데이터를 저장하는 Java 자료형을 의미합니다.
자세한 내용은 이 글을 참고해주세요

3. TreeMap 구현체

전체적인 상속관계는 다음과 같습니다

  • AbstractMap (implements Map) [Class(Abstract)]
    • TreeMap (implements NavigableMap<K,V>, Cloneable, java.io.Serializable) [Class]

TL;DR

정렬상태를 중간중간 자주 확인해야하는경우 사용

TreeMap은 연결리스트 방식을 사용하여 구현된 이진탐색트리 구조를 사용하여 Key를 저장/관리하는 Map 구현체입니다.
HashMap과 다른점이라면 저장할 때 효율적인 정렬기준이나 알고리즘을 직접 설정하여 작업속도를 향상시킬 수 있다는 점 입니다.
또한 null을 데이터가 없다는 표시로 사용하여, value로 null을 사용할 수 없습니다.

기본 동작구조

TreeMap은 동작구조가 복잡하진 않지만, 통일성을 위해 HashMap처럼 동작방식을 정리하였습니다

0) TreeMap 동작원리

TreeMap은 내부에서 Map.Entry를 extend하는 TreeMap 내 자체 Entry 객체를 통해 연결리스트 방식으로 이진탐색트리구조를 구성하여 관리합니다. 다음과 같은 정보를 담을 수 있습니다:

1) TreeMap 생성: 정렬기준 (comparator) 설정

TreeMap을 constructor로 생성할 때, TreeMap은 별도의 작업 없이 내부필드 중 Comparator만 설정합니다.
선택옵션이므로 별도로 입력하지 않아도 되며, Map을 입력하는 경우 기존 정렬기준과 내부값을 읽어와 생성하는 객체 내에 buildFromSorted()메서드를 사용하여 깊은복사를 수행합니다.

2) 데이터 추가

TreeMap.put()을 통해 데이터를 추가하게 되면, TreeMap은 기존에 저장되어있던 값을을 비교하며 기존에 설정된 Comparator를 사용하여 새로운 값의 저장위치를 판단하여 저장합니다.
따라서 기존 입력순서는 유지되지 않고, 입력 즉시 정렬됩니다.

3) 데이터 접근

HashMap.get()를 통해 데이터 접근 시, 초기 TreeMap 생성 시 Comparator를 선언했는지 여부에 따라 getEntryUsingComparator()나 getEntry()를 사용하여 탐색하게 됩니다.

caseA) Comparator를 선언한 경우
getEntryUsingComparator()를 호출하여 기존에 선언한 Comparator의 응답을 기준으로 root부터 트리를 탐색합니다.

caseB) Comparator를 선언하지 않은 경우
getEntry()를 호출하여 key의 compareTo() 메서드 구현에 의존하여 root부터 트리를 탐색합니다. 이를 위해 초기 key 설정 시, key의 type은 반드시 Comparable Interface를 implement해야 합니다.

동작 별 소요 시간복잡도

최종적으로 동작 별 소요되는 시간복잡도는 다음과 같습니다:

동작유형시간복잡도설명
추가O(log n)저장위치 탐색을 위해 이진탐색트리에서의 탐색시간이 소요
조회 - getO(log n)대응키 탐색을 위해 이진탐색트리에서의 탐색시간이 소요
조회 - containsKeyO(log n)Comparator 유무에 따라 get과 같은방식으로 tree에서 key를 탐색
조회 - containsValueO(log n) / O(n)Comparator를 사용하지 않고 오른쪽으로 dfs방식으로 탐색하며 확인. 포함되어있지 않은 경우 모두 찾아보기 때문에 O(n)
삭제O(log n)삭제대상 탐색을 위해 이진탐색트리에서의 탐색시간이 소요

4. 결론

데이터를 많이 저장해야하고, 입력순서가 중요하지 않다면
TreeMap을 사용하자.. (심지어 HashMap도 데이터가 많으면 TreeMap을 사용한다)

profile
Developer waffle = new Waffle();

0개의 댓글