C++ map vs unordered_map: 레드-블랙 트리와 해시 테이블의 성능·메모리 비교
이 글의 핵심
정렬이 필요 없는데 습관적으로 map을 쓰던 코드를 unordered_map으로 바꾸면 항상 빨라질까요? 해시 충돌이 몰릴 때의 최악 성능, load_factor가 성능에 주는 영향, 좋은 해시 함수의 조건을 짚고, 게임 엔티티 조회·시계열 데이터·설정 파일 파싱 사례로 선택 기준을 확인합니다.
들어가며: “map이 느린데 unordered_map으로 바꾸면 빨라지나요?”
C++ STL은 map(정렬된 맵)과 unordered_map(해시 테이블) 두 가지 연관 컨테이너를 제공합니다. 시간 복잡도가 다르므로 상황에 맞는 선택이 중요합니다. 해시 테이블의 일반 이론·충돌 처리는 알고리즘 시리즈: 해시 테이블에서 먼저 잡아 두면 unordered_map 선택이 수월합니다.
// map: O(log n) 조회 — 키 순서가 있음
std::map<std::string, int> ordered;
ordered["Alice"] = 100; // O(log n)
int x = ordered["Alice"]; // O(log n)
// unordered_map: O(1) 평균 조회 — 키 순서 없음
std::unordered_map<std::string, int> hashed;
hashed["Alice"] = 100; // O(1) 평균
int y = hashed["Alice"]; // O(1) 평균두 블록은 같은 operator[] 문법을 쓰지만, 내부 자료구조가 트리(정렬 유지)와 해시 테이블(평균 상수 시간)로 달라서 시간 보장과 사용할 수 있는 연산(lower_bound 등)이 달라집니다.
내부 구조 비교
map: 레드-블랙 트리 (Red-Black Tree)
[5]
/ \
[3] [7]
/ \ / \
[1] [4][6] [9]
특징:
- 자가 균형 이진 탐색 트리
- 키가 자동 정렬
- 최악의 경우도 O(log n) 보장std::map<int, std::string> m;
m[5] = "five";
m[3] = "three";
m[7] = "seven";
// 순회하면 정렬된 순서로 출력
for (const auto& [key, value] : m) {
std::cout << key << ": " << value << '\n';
}
// 출력: 3: three, 5: five, 7: sevenunordered_map: 해시 테이블 (Hash Table)
버킷 배열:
[0] → [key=3, val="three"]
[1] → [key=7, val="seven"] → [key=17, val="seventeen"] (충돌)
[2] →
[3] → [key=5, val="five"]
...
특징:
- 해시 함수로 버킷 인덱스 계산
- 키가 정렬되지 않음
- 평균 O(1), 최악 O(n) (충돌 시)std::unordered_map<int, std::string> um;
um[5] = "five";
um[3] = "three";
um[7] = "seven";
// 순회하면 임의 순서로 출력
for (const auto& [key, value] : um) {
std::cout << key << ": " << value << '\n';
}
// 출력: 7: seven, 3: three, 5: five (순서 보장 안 됨)시간 복잡도 비교
연산별 시간 복잡도
| 연산 | map | unordered_map |
|---|---|---|
| 삽입 | O(log n) | O(1) 평균, O(n) 최악 |
| 삭제 | O(log n) | O(1) 평균, O(n) 최악 |
| 조회 | O(log n) | O(1) 평균, O(n) 최악 |
| 순회 | O(n) 정렬됨 | O(n) 정렬 안 됨 |
| 최솟값/최댓값 | O(1) | O(n) |
최악의 경우 차이
// map: 항상 O(log n)
std::map<int, int> m;
for (int i = 0; i < 1000000; ++i) {
m[i] = i; // O(log n) 보장
}
// unordered_map: 해시 충돌 시 O(n)
std::unordered_map<int, int> um;
// 나쁜 해시 함수 사용 시 모든 키가 같은 버킷에 → O(n)연산별 비용을 측정하는 법
아래 코드는 연산별 비용을 직접 재 볼 때 쓸 수 있는 최소 골격입니다. 결과는 CPU, 컴파일러, 표준 라이브러리 구현, 키 분포에 따라 크게 달라지므로, 여기서는 숫자 대신 각 연산에서 무슨 일이 일어나는지를 설명합니다. 측정할 때는 -O2 이상으로 빌드하고, 결과 값(sum 등)을 출력하거나 volatile에 저장해 컴파일러가 루프를 지우지 못하게 해야 합니다.
테스트 1: 삽입 (insert)
// 벤치마크 코드
template <typename Map>
void benchInsert() {
Map m;
for (int i = 0; i < 1000000; ++i) {
m[i] = i;
}
}map은 삽입마다 트리를 O(log n) 단계 내려가며 비교하고 회전으로 균형을 맞추는 반면, unordered_map은 해시로 버킷을 바로 찾습니다. 그래서 정수 키 대량 삽입에서는 보통 unordered_map이 여러 배 빠르게 나오고, reserve로 재해시(rehash)를 없애면 차이가 더 벌어집니다. 다만 키가 0부터 연속된 정수이고 libstdc++의 std::hash<int>는 값을 그대로 쓰기 때문에, 충돌이 거의 없는 유리한 조건이라는 점을 감안해야 합니다.
테스트 2: 조회 (lookup)
template <typename Map>
void benchLookup(const Map& m) {
long long sum = 0;
for (int i = 0; i < 1000000; ++i) {
sum += m.at(i);
}
}map 조회는 트리 노드를 20단계 가까이(log₂ 100만) 따라가며 매번 다른 메모리 위치를 읽어 캐시 미스가 쌓입니다. 문자열 키처럼 해시 계산이 비싸거나 충돌이 많은 키에서는 차이가 줄어들 수 있습니다.
테스트 3: 순회 (iteration)
template <typename Map>
void benchIteration(const Map& m) {
long long sum = 0;
for (const auto& [key, value] : m) {
sum += value;
}
}순회는 두 컨테이너 모두 O(n)이고 실제 비용도 비슷한 편입니다. 둘 다 원소마다 노드를 따로 할당하므로, 노드가 힙에 흩어져 있으면 포인터를 따라갈 때마다 캐시 미스가 납니다. libstdc++의 unordered_map은 모든 노드를 하나의 단일 연결 리스트로 이어 두어 빈 버킷을 건너뛰는 비용이 없습니다.
테스트 4: 정렬된 순회
// map: 자동 정렬
for (const auto& [key, value] : m) {
// 키가 정렬된 순서로 순회
}
// unordered_map: 수동 정렬 필요
std::vector<std::pair<Key, Value>> sorted(um.begin(), um.end());
std::sort(sorted.begin(), sorted.end());
for (const auto& [key, value] : sorted) {
// 정렬된 순서로 순회
}정렬된 순서가 필요하면 map이 유리합니다. unordered_map은 순회 결과를 복사하고 O(n log n) 정렬을 추가로 해야 하기 때문입니다.
메모리 사용량 비교
원소당 오버헤드
// map<int, int> (libstdc++, 64비트 기준)
// [색상 + 부모/왼쪽/오른쪽 포인터 = 32바이트][키 4 + 값 4 = 8바이트] = 노드당 약 40바이트
// + malloc 청크 헤더·정렬로 실제로는 더 큼
// unordered_map<int, int> (libstdc++, 64비트 기준)
// [next 포인터 8바이트][키 4 + 값 4 = 8바이트] = 노드당 약 16바이트
// + 버킷 배열(버킷당 포인터 8바이트, 버킷 수 ≥ 원소 수 / max_load_factor)100만 개 저장 시 메모리
두 컨테이너 모두 원소마다 별도 노드를 힙에 할당하므로, int 두 개(8바이트)를 저장하는 데 그보다 몇 배 큰 메모리를 씁니다. map은 노드마다 포인터 3개와 색상 정보를 갖고, unordered_map은 노드가 더 작은 대신 원소 수 이상의 버킷 배열을 따로 둡니다. 정확한 크기는 표준 라이브러리 구현(libstdc++, libc++, MSVC)과 할당기에 따라 달라지므로, 메모리가 중요하다면 /proc/self/status의 RSS나 커스텀 할당기로 직접 재 보세요.
결론: 보통 unordered_map이 조금 더 작지만, 버킷 배열이 커지는 재해시 직후에는 차이가 줄어듭니다. 메모리가 정말 중요하다면 정렬된 std::vector<std::pair<K,V>>나 C++23 std::flat_map이 노드 할당이 없어 훨씬 작습니다.
상황별 선택 가이드
언제 map을, 언제 unordered_map을 쓰나요?
| 관점 | map을 쓰시면 좋은 경우 | unordered_map을 쓰시면 좋은 경우 |
|---|---|---|
| 성능 | 최악의 경우에도 O(log n)으로 예측 가능해야 할 때 | 평균 조회·삽입이 빈번하며, 해시가 안정적일 때 |
| 사용성 | lower_bound 등 정렬 기반 API를 그대로 쓰고 싶을 때 | 키 순서가 전혀 필요 없고 조회 속도만 중요할 때 |
| 적용 시나리오 | 순위표, 시계열 구간, 키 범위 스캔 | 단어 빈도, ID→객체 캐시, 설정 키 조회 |
결정 트리
Q1. 정렬이 필요한가?
Yes → map
No → Q2
Q2. 최악의 경우 성능이 중요한가? (실시간 시스템)
Yes → map (O(log n) 보장)
No → Q3
Q3. 키가 복잡한가? (해시 함수 작성 어려움)
Yes → map
No → unordered_map상황별 권장
| 상황 | 권장 | 이유 |
|---|---|---|
| 기본 선택 | unordered_map | 평균 O(1), 빠름 |
| 정렬 필요 | map | 자동 정렬 |
| 범위 조회 | map | lower_bound, upper_bound |
| 최악 성능 중요 | map | O(log n) 보장 |
| 메모리 절약 | unordered_map | 오버헤드 낮음 |
| 키가 복잡 | map | 해시 함수 불필요 |
| 빠른 조회 | unordered_map | O(1) 평균 |
실전 예제
예제 1: 단어 빈도 카운트
// 요구사항: 빠른 조회, 정렬 불필요
// 권장: unordered_map
std::unordered_map<std::string, int> wordCount;
for (const auto& word : words) {
++wordCount[word]; // O(1) 평균
}
// 가장 빈번한 단어 찾기
auto maxIt = std::max_element(wordCount.begin(), wordCount.end(),
[](const auto& a, const auto& b) {
return a.second < b.second;
});예제 2: 순위표 (Leaderboard)
// 요구사항: 점수순 정렬, 상위 10명 조회
// 권장: multimap (내림차순) — 점수가 같은 사람이 있을 수 있으므로
// map<int, string>을 쓰면 같은 점수의 이전 이름이 덮어써진다
std::multimap<int, std::string, std::greater<int>> leaderboard; // 내림차순
leaderboard.emplace(100, "Alice");
leaderboard.emplace(95, "Bob");
leaderboard.emplace(98, "Charlie");
leaderboard.emplace(98, "Dave"); // 같은 점수도 유지됨
// 상위 10명 (자동 정렬)
int count = 0;
for (const auto& [score, name] : leaderboard) {
std::cout << name << ": " << score << '\n';
if (++count >= 10) break;
}예제 3: 캐시 (빠른 조회)
// 요구사항: 빠른 조회, 정렬 불필요
// 권장: unordered_map
std::unordered_map<UserId, UserData> cache;
cache.reserve(10000); // 재해싱 방지
// 조회 O(1)
auto it = cache.find(userId);
if (it != cache.end()) {
return it->second;
}예제 4: 구간 쿼리
// 요구사항: 특정 범위의 키 찾기
// 권장: map
std::map<int, std::string> events;
events[100] = "Event A";
events[200] = "Event B";
events[300] = "Event C";
// 150~250 범위의 이벤트 찾기
auto start = events.lower_bound(150); // >= 150
auto end = events.upper_bound(250); // > 250
for (auto it = start; it != end; ++it) {
std::cout << it->first << ": " << it->second << '\n';
}
// 출력: 200: Event B해시 충돌과 성능
해시 충돌 시나리오
// ❌ 나쁜 해시 함수
struct BadHash {
size_t operator()(int key) const {
return 0; // 모든 키가 버킷 0으로 → O(n)
}
};
std::unordered_map<int, int, BadHash> um;
for (int i = 0; i < 1000000; ++i) {
um[i] = i; // O(n) 삽입 → 매우 느림
}좋은 해시 함수
// ✅ 비트를 고르게 섞는 해시 함수 (splitmix64의 마무리 단계)
struct GoodHash {
size_t operator()(int key) const {
uint64_t x = static_cast<uint64_t>(key) + 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return static_cast<size_t>(x ^ (x >> 31));
}
};
std::unordered_map<int, int, GoodHash> um;libstdc++는 버킷 수로 소수를 쓰기 때문에 연속된 정수 키라면 값을 그대로 돌려주는 기본 std::hash<int>로도 충돌이 거의 없습니다. 이런 혼합 함수가 필요한 경우는 키가 특정 배수에 몰려 있거나, 외부 입력이 키라서 공격자가 일부러 같은 버킷에 몰리는 키를 보낼 수 있을 때입니다.
load_factor와 성능
std::unordered_map<int, int> um;
// load_factor = size / bucket_count
std::cout << "Load factor: " << um.load_factor() << '\n';
std::cout << "Max load factor: " << um.max_load_factor() << '\n'; // 기본 1.0
// 삽입 후 load_factor가 max_load_factor를 넘게 되면 재해싱 (rehashing)
um.reserve(1000000); // 미리 버킷 확보 → 재해싱 방지커스텀 키 타입
map: operator< 필요
struct Person {
std::string name;
int age;
// map을 위한 비교 연산자
bool operator<(const Person& other) const {
if (name != other.name) return name < other.name;
return age < other.age;
}
};
std::map<Person, std::string> m;
m[{"Alice", 30}] = "Engineer";unordered_map: std::hash 특수화 + operator==
struct Person {
std::string name;
int age;
// unordered_map을 위한 동등 비교
bool operator==(const Person& other) const {
return name == other.name && age == other.age;
}
};
// std::hash 특수화
namespace std {
template <>
struct hash<Person> {
size_t operator()(const Person& p) const {
size_t h1 = std::hash<std::string>{}(p.name);
size_t h2 = std::hash<int>{}(p.age);
return h1 ^ (h2 << 1); // 간단한 조합(실무에서는 boost::hash_combine 같은 혼합 방식이 더 안전)
}
};
}
std::unordered_map<Person, std::string> um;
um[{"Alice", 30}] = "Engineer";실전 사례 분석
사례 1: 게임 엔티티 조회
요구사항:
- 엔티티 ID로 빠른 조회 (매 프레임)
- 정렬 불필요
선택: unordered_map
class EntityManager {
std::unordered_map<EntityId, Entity> entities_;
public:
EntityManager() {
entities_.reserve(10000); // 재해싱 방지
}
void add(EntityId id, Entity e) {
entities_[id] = std::move(e); // O(1)
}
Entity* get(EntityId id) {
auto it = entities_.find(id); // O(1)
return it != entities_.end() ? &it->second : nullptr;
}
};이유: 매 프레임 조회하므로 O(1)이 중요.
사례 2: 시계열 데이터
요구사항:
- 타임스탬프순 정렬
- 특정 시간 범위 조회
선택: map
class TimeSeriesData {
std::map<Timestamp, double> data_;
public:
void add(Timestamp t, double value) {
data_[t] = value; // 자동 정렬
}
std::vector<double> getRange(Timestamp start, Timestamp end) {
std::vector<double> result;
auto it_start = data_.lower_bound(start); // >= start
auto it_end = data_.upper_bound(end); // > end
for (auto it = it_start; it != it_end; ++it) {
result.push_back(it->second);
}
return result;
}
};이유: 정렬과 범위 조회가 필요.
사례 3: 설정 파일 파싱
요구사항:
- 키-값 쌍 저장
- 조회 빈번, 삽입 드묾
선택: unordered_map
class Config {
std::unordered_map<std::string, std::string> settings_;
public:
void load(const std::string& filename) {
// 파일 읽기
settings_.reserve(100); // 예상 크기
// 파싱
settings_["server.port"] = "8080";
settings_["server.host"] = "localhost";
// ...
}
std::string get(const std::string& key) const {
auto it = settings_.find(key); // O(1)
return it != settings_.end() ? it->second : "";
}
};이유: 조회가 빈번하고 정렬 불필요.