Map에 대하여..

TreeMap

 

Map collection class에 속하는 대표적인 클래스 중 TreeMap이 있다.

TreeMap class는 Map Interface를 계승한 클래스이기 때문에 HashMap과 마찬가지로 키와 값을 한 쌍으로 하는 Map.entry를 상속받지만 차이점은 Entry를 이진검색트리 형태로 저장한다는 점이다.

이진검색트리는 데이터를 추가하거나 제거하는 등의 기본동작 시간이 빠르다. 그리고 많은 자료에서 원하는 값을 찾을 때 효율적이다.( 검색 )

 

TreeMap과 TreeSet의 차이점은 TreeMap에서는 키와 값이 저장된 map.entry를 저장한다는 것이다.

TreeMap클래스는 Map 인터페이스를 구현하므로, 중복된 키 값을 저장할 수 없지만, 같은 값을 다른 키로 저장하는 것은 가능하다. (Tree에서는 중복된 값을 받을 수 없다. Tree와 TreeMap의 차이점)

TreeMap에서 하나의 노드는 노드 값인 value와 왼쪽과 오른쪽 자식 노드를 참조하기 위한 두 개의 변수(포인터)로 구성되어 있다.

두 개의 변수는 자식 노드의 메모리의 저장 위치를 알려준다. 즉, 두 개의 변수는 참조변수이다.

TreeMap에 객체를 저장하면 자동으로 정렬이 되는데, 부모의 키 값과 비교해서 키 값이 낮은 것은 왼쪽 자식 노드에 저장, 키 값이 높은 것은 오른쪽 자식 노드에 map.entry 형태로 저장된다.

  

Map 중 key값이 정렬된 것을 SortedMap 인터페이스라고 하는데 이를 구현한 것이 TreeMap이며, JDK 1.2부터 제공된 TreeMap 클래스는 NavigableMap 인터페이스를 기존의 이진검색트리의 성능을 향상시킨 레드블랙트리로 구현한다.

  

SortedMap을 간단히 정의하자면, 정렬을 위한 map계열의 클래스이다.

SortedMap은 key값을 기준으로 정렬해 저장한다.

SortedMap은 자연적인 정렬방식을 이용하거나, comparator가 제공한 해당 정렬 방식으로 SortedMap을 생성한다. 여기서 자연적인 정렬방식이란 키에 해당하는 객체가 증가되는 순서를 말한다.

여기서 더 깊이 나아가면, SortedMap은 또 comparator를 가지고 있는 맵을 인자로 받고 있다.

그러므로 SortedMap Interface를 받는 TreeMap에서도 comparator에서 직접 정렬 방식을 따로 지정하지 않을 경우, 키 값이 자연 정렬 방식으로 저장된다.

만약 자연 정렬 방식이 아닌 직접 지정한 정렬 방식으로 정렬을 수행하고 싶다면, SortedMap에서 comparator를 구현해 자신이 직접 정렬방식을 지정하여 구현하면 된다.

 

NavigableMap은 지정된 타겟으로 가장 가까운 요소를 돌려주는 네비게이션 메소드로 확장된 SortedMap 이다. NavigableMap은 자바 1.6 version에서 추가되었는데, 맵 자료구조에서 데이터는 찾아가는 성능이 구현된 것이다.

 

TreeMap을 이진 검색 트리형태에서 더 나아가 레드블랙트리형태로 구현 할 수 있다.

이진검색트리에서 몇 가지 조건을 만족할 시 레드블랙트리가 된다.

1.노드는 레드 혹은 블랙 중의 하나이다.

2.루트 노드는 블랙이다.

3.모든 리프 노드는 블랙이다.

4.레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다.(즉,레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다)

5.어떤 노드로부터 시작되어 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.

 

트리에 n개의 원소가 있을 때, O(log n)의 시간 복잡도로 삽입, 삭제, 검색을 한다.

여기서 레드-블랙 트리의 가장 중요한 특성은 루트 노드부터 가장 먼 경로까지의 거리가, 가장 가까운 경로까지의 거리의 두 배 보다 항상 작다. 다시 말해서 레드-블랙 트리는 균형이 잡혀 있다.

따라서 삽입, 삭제, 검색 시 최악의 경우에서의 시간복잡도가 트리의 높이에 따라 결정되기 때문에 보통의 이진 탐색 트리에 비해 효율적이라고 할 수 있다.

 

왜 이런 특성을 가지는가에 대한 이유는 레드블랙트리의 조건인 어떤 경로에도 레드 노드가 연이어 나타날 수 없다는 것만 알고 있어도 충분하다. 최단 경로는 모두 블랙 노드로만 구성되어 있다고 했을 때, 최장 경로는 블랙 노드와 레드 노드가 번갈아 나오는 것이 될 것이다. 다섯 번째 속성에 따라서, 모든 경로에서 블랙 노드의 수가 같다고 했기 때문에 존재하는 모든 경로에 대해 최장 경로의 거리는 최단 경로의 거리의 두 배 이상이 될 수 없다.

cf)만약 모든 노드가 다 블랙이라면 최단시단

 

레드블랙트리의 장점은...

자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행시간을 보장한다.

이진 검색 트리로 구현할 경우, 편향트리 형태로 데이터가 저장될 가능성이 있다. 그 경우, 최악의 시간이 걸리게 된다.

그 점을 방지 할 수 있다는 점이 TreeMap을 레드블랙트리로 구현하면 좋은 점이다.

따라서 실시간 처리 같은 실행시간이 중요할 경우 레드블랙트리를 사용하면 좋겠다.

 

 

---

 

STL container

 

STL 컨테이너는 크게 시퀀스 컨테이너와 연관 컨테이너로 나뉜다.

시퀀스 컨테이너(Vector, List, Deque) -> 순서 있게 자료 보관

연관 컨테이너(Map, Set, HashMap, HashSet) -> 어떠한 키와 짝을 이루어 자료 보관, 자료를 넣고 빼고 찾을　때에 key가 필요

=>시퀀스 컨테이너에는 많지 않은 자료를 보관하고, 연관 컨테이너는 대량의 자료를 보관하고 검색을 빠르게 하고 싶을 때 사용

 

HashMap

 

HashMap의 자료구조는 HashTable이다. HashTable에 자료를 저장할 때는 key 값을 해쉬 함수에 대입하여 버킷번호가 나오면 그 버킷이 빈 슬롯에 자료를 저장한다.

키 값을 해쉬 함수에 입력하여 나오는 버킷번호에 자료를 넣으므로 많은 자료를 저장해도 삽입, 삭제, 검색 속도가 거의 일정하다.

Map과의 차이점 : HashTable이란 자료구조를 사용하기 때문에 원소을 정렬하지 않는다. 더 빠른 검색 속도를 가진다.

cf) HashTable -> key값에 해쉬 함수를 적용시켜 얻은 값을 얻어 해쉬 테이블에 분산하여 저장, 이론상 O(1)의 검색속도를 얻어 낼 수 있는 자료구조

- HashMap을 사용할 때와 사용하지 않을 때

 

해쉬 테이블은 많은 자료를 저장하고 있어도 검색이 빠르다. 그러나 저장한 자료가 적을 때는 메모리 낭비와 검색 시 오버헤드가 생긴다.

​적은 요소를 저장하고 검색 할 때는 vector나 list가 훨씬 빠를 수 있지만, 수천의 자료를 저장하여 검색을 하는 경우에는 HashMap을 사용하는 것이 좋다.

 

따라서!!! HashMap 단일검색, Tree는 범위검색에 적합하다.