[C++] map과 unordered_map

기본적으로 map과 unordered_map은 key, value의 한 쌍으로, pair<Tkey, Tvalue> 형태를 띄는 자료구조입니다.

 

---

map

 

1. map은 아래와 같은 형태의 RB Tree로 이루어져 있습니다. (이해하는 데 도움을 받은 링크를 첨부합니다.)
2. 요약하면 RB Tree는 레드 노드를 연속으로 배치할 수 없도록 하여 느슨한 AVL Tree를 만든 것입니다.
3. 유사 AVL Tree이므로 자료구조의 탐색, 삽입, 삭제가 얼추 O(log N)으로 보장됩니다.
4. Key를 기준으로 정렬되어 있으며, Iterator를 통해 그 순서대로 순회가 가능합니다.

레드, 블랙 노드로 이루어져 있는 RB Tree

https://jwdeveloper.tistory.com/280

(알고리즘) 레드블랙트리

 

https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC

레드-블랙 트리 - 위키백과, 우리 모두의 백과사전

---

unordered_map

 

1. unordered_map은 말 그대로 정렬되어있지 않은 map입니다. (Tree의 형태로 되어있지 않음)
2. 내부는 Hash Table로 되어 있습니다.
3. Hash Table은 Key를 Hash Function으로 변환하여 인덱스를 추출하여 Value를 사용하는 방식입니다.
4. 즉 접근, 삽입, 삭제가 O(1)로 매우 우수하다는 특징이 있습니다.

해시 테이블 구조도

---

? Key를 기준으로 정렬된 자료 구조를 순회할 수 있다는 것을 제외하면 단순히 봤을 때 unordered_map이 우수해보인다.

---

결론부터 말하자면 일반적으론 unordered_map의 성능이 더 좋다.

 

• 하지만 다음과 같은 경우엔 주의가 필요합니다.

1. Key로 사용되는 타입이 길이에 제약을 가졌는가?
2. unordered_map의 사용처가 너무 거대하진 않은가?

 

---

Key로 사용되는 타입이 길이에 제약을 가졌는가?

우선 Key의 길이에 제한이 없으면 엄청나게 긴 길이의 Key가 들어올 가능성이 있습니다.

string을 예로 들어봅시다.

map의 Key 비교 함수는 앞에서부터 차례대로 비교하여 크고 작음을 가려내기 때문에,
Key 문자열 길이의 변화는 그 영향이 적을 확률이 높습니다.
(하지만 타임 스탬프 기록 등 앞 부분 유사도가 높은 경우엔 주의해야 합니다.)

하지만 unordered_map은 문자열을 모두 Hashing하기 때문에, 그 길이에 영향을 비교적 많이 받습니다. 문자열의 길이가 각각 4, 8, 12, 16인 경우의 비교 그래프입니다.

---

unordered_map의 사용처가 너무 거대하진 않은가?

unordered_map은 Hash Table입니다.

서로 다른 Hash를 Index로 변환하는 과정에서 중복이 발생할 수 있는 여지가 항상 있습니다. (해시 충돌)

이를 보통 체이닝, 오픈 어드레싱을 사용하여 해결하게 되는데,
결과적으로 이는 접근, 삽입, 삭제에 대한 시간 복잡도를 O(1)을 유지해야 하는 해시 테이블을 무너뜨립니다.

unordered_map의 사용처가 너무 거대하다면 해시 충돌의 발생 빈도가 상승하므로,
주의해서 사용할 필요가 있습니다.

---

https://gracefulprograming.tistory.com/3

[C++] map vs hash_map(unordered_map)