[C++] STL - std::map과 std::unordered_map

std::map

map은 key-value 쌍을 저장하는 자료구조로, 이진 탐색 트리(BST)인 레드-블랙 트리를 기반으로 구현되었습니다. 레드-블랙 트리를 기반으로 구현되어 map의 key 값은 자동 정렬됩니다.

 

시간복잡도

map 자료구조에 원소를 추가/검색/삭제할 때, 해당 위치를 찾기 위해 이진 탐색을 수행합니다. 그 후 명령에 따라 새로운 노드를 삽입하거나, 주어진 키와 각 노드의 키 값을 비교하며 검색하거나, 노드를 제거하는 등의 역할을 수행합니다.

따라서, 이러한 이진 탐색으로 작동하는 map은 모든 기본 연산이 O(log n)의 시간 복잡도를 갖습니다.

 

map은 왜 정렬을 할까?

1. key-value 쌍을 저장할 때, key 값들이 일정한 순서로 정렬되어야 이진 탐색이 가능하고, 이진 탐색을 통한 원소의 검색 속도가 크게 향상되기 때문입니다.

 

2. key 값에 따라 자동으로 정렬되는 구조를 유지해야 하기 때문입니다. 데이터의 삽입/삭제가 빈번하면서도 데이터 간의 순서가 중요한 경우에 map 자료구조를 사용할 수 있습니다.

예시) 사전을 구현할 때, 로그 시스템을 구현하여 발생 시간에 따라 정렬할 때, 작성 시간에 따라 정렬하는 타임라인 기능을 구현할 때

 

std::unordered_map

unordered_map은 map과 동일하게 key-value 쌍으로 데이터를 저장하지만, map과 달리 정렬되지 않는다는 특성이 있습니다. unordered_map의 내부적으론 해시 테이블을 기반으로 만들어졌고, 각 키는 해당 값에 접근하기 위한 고유한 식별자 역할을 수행합니다.

 

해싱

원소를 추가하거나 검색할 때, 키의 해시 값을 통해 접근합니다. 이때 해시 값은 해시 함수에 의해 생성되고, 이 함수는 임의의 길이를 가진 데이터(key)를 고정된 크기의 데이터(해시 값)로 매핑합니다.

 

이렇게 계산된 해시 값을 unordered_map의 버킷 인덱스로 결정하는데, 보통 해시 값을 버킷 수로 나눈 나머지를 사용하여 어느 버킷에 원소를 저장할지 결정합니다.

여기서 '버킷'은 unordered_map 내부에 있는 연속적인 메모리 블록을 의미합니다.

 

리사이징(Resizing)

unordered_map 에서는 로드 팩터(load factor)라는 개념을 사용하여 자동 리사이징 기능을 제공합니다.

로드 팩터란, 현재 맵 안에 원소 수를 버킷의 수로 나눈 값을 말합니다. 이 값이 max_load_factor() 함수로 얻어지는 임계치보다 크면 rehash() 함수가 호출되어 내부적으로 더 많은 버킷이 재해싱됩니다.

일반적으로 해시 테이블의 크기가 2배로 증가합니다.

 

> bucket_count(), rehash(), reserve()

unordered_map에서 버킷의 수를 알기 위해선 bucket_count() 함수를 사용하면 됩니다.
이 함수는 현재 unordered_map이 가지고 있는 버킷의 수를 반환합니다.

만약, 버킷의 수를 미리 늘려놓으려면 rehash()나 reserve() 함수를 사용해 충분한 양의 메모리 공간을 확보해놓을 수 있고, 이렇게되면 새로운 원소가 추가될 때마다 재해싱하는 비용을 줄일 수 있습니다.

rehash(n) 함수는 버킷의 최소 개수를 n개 이상이 되도록 설정하고, reserve(n) 함수는 저장된 원소의 개수가 n개가 될 수 있도록 충분한 공간을 확보하는 것을 요청합니다. reserve 함수는 내부적으로 load_factor() 와 결합하여 적절한 버킷의 수를 계산하고, 필요하다면 rehash()를 호출하여 해시 테이블의 크기를 조정합니다.

 

시간복잡도

unordered_map은 원소의 추가/검색/삭제 시 평균적으로 O(1)의 시간복잡도가 걸립니다.

최악의 경우에 모든 키가 해시 충돌이 일어나 동일한 버킷에 들어가게 된다면, 동일한 버킷 내를 선형탐색하여 O(n)까지 시간복잡도가 증가할 수 있습니다.

 

해싱 충돌 처리

unordered_map에서는 해시 충돌이 일어날 때 체인화 방식으로 처리합니다. 따라서 같은 버킷 인덱스를 가진 원소가 여러 개 존재하는 경우 연결 리스트(linked list)로 관리합니다.

---

map과 unordered_map을 사용하는 경우는? 

위에서 설명했다시피, 추가/검색/삭제의 시간복잡도는 unordered_map이 훨씬 빠릅니다. 반면, map은 항상 정렬된 상태를 유지하여 더 효율적인 경우가 있을 수 있습니다. 따라서 보통 정렬의 필요성이 없는 경우 unordered_map을 사용하는 것이 일반적으로 더 효율적이고, 정렬된 상태를 유지해야 한다면 map을 사용하는 것이 좋습니다.

 

그 밖에도, map과 unordered_map을 효율적으로 사용하는 조건은 key의 값에 따라 달라질 수 있습니다.

unordered_map은 키에 대한 해시 함수를 필요로 하기 때문에, 키가 해시 가능한 경우에만 unordered_map을 사용할 수 있습니다. 예를들어, key 값이 복잡한 사용자 정의 타입인 경우에는 map을 사용해야 합니다.

또한, key 의 크기가 매우 큰 경우엔 해시함수를 이용한 해싱 비용이 증가하므로, map이 더 효율적일 수 있습니다.

map은 정렬을 수행하기 때문에 key 값에 대한 비교함수를 필요로 합니다. 따라서, 키가 '<' 연산자를 지원하는 경우에 map을 사용할 수 있습니다.