C++ map vs unordered_map 심층 비교 | "어느 게 빠를까?" 성능 비교와 선택 가이드
이 글의 핵심
C++ map vs unordered_map 심층 비교에 대한 실전 가이드입니다.
들어가며: “map이 느린데 unordered_map으로 바꾸면 빨라지나요?"
"정렬이 필요 없는데 map을 쓰고 있었어요”
C++ STL은 map(정렬된 맵)과 unordered_map(해시 테이블) 두 가지 연관 컨테이너를 제공합니다. 시간 복잡도가 다르므로 상황에 맞는 선택이 중요합니다. 해시 테이블의 일반 이론·충돌 처리는 알고리즘 시리즈: 해시 테이블에서 먼저 잡아 두면 unordered_map 선택이 수월합니다.
비유로 말씀드리면, map은 항상 목차가 정해진 사전처럼 키가 정렬되어 있어 범위 검색·바로 다음 키를 찾기 좋고, unordered_map은 서가에 꽂은 책을 제목만 보고 바로 꺼내는 것에 가깝습니다. 평균적으로는 빠르지만, 해시 충돌이 나면 그 서가에 책이 몰려 한꺼번에 뒤져야 할 수 있습니다.
// map: O(log n) 조회 — 키 순서가 있음
std::map<std::string, int> scores;
scores["Alice"] = 100; // O(log n)
int x = scores["Alice"]; // O(log n)
// unordered_map: O(1) 평균 조회 — 키 순서 없음
std::unordered_map<std::string, int> scores;
scores["Alice"] = 100; // O(1) 평균
int x = scores["Alice"]; // O(1) 평균위 두 블록의 차이는 같은 scores["Alice"] 문법이어도, 내부 자료구조가 트리(정렬 유지)와 해시 테이블(평균 상수 시간)로 달라서 시간 보장과 사용할 수 있는 연산(lower_bound 등)이 달라집니다.
이 글에서 다루는 것:
- map과 unordered_map의 내부 구조
- 시간 복잡도 비교 (삽입, 삭제, 조회)
- 실제 성능 벤치마크
- 메모리 사용량 비교
- 상황별 선택 가이드
- 해시 함수 커스터마이징
목차
1. 내부 구조 비교
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 (순서 보장 안 됨)2. 시간 복잡도 비교
연산별 시간 복잡도
| 연산 | 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)3. 실제 성능 벤치마크
벤치마크 환경
CPU: Intel i7-12700K
RAM: 32GB DDR4-3200
컴파일러: GCC 11.2, -O3
원소 개수: 100만 개테스트 1: 삽입 (insert)
// 벤치마크 코드
template <typename Map>
void benchInsert() {
Map m;
for (int i = 0; i < 1000000; ++i) {
m[i] = i;
}
}결과:
| 컨테이너 | 시간 | 상대 속도 |
|---|---|---|
| map | 850ms | 5.3x |
| unordered_map | 160ms | 1.0x (기준) |
| unordered_map (reserve) | 120ms | 0.75x (더 빠름) |
분석: unordered_map이 5배 빠름.
테스트 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 | 120ms | 3.0x |
| unordered_map | 40ms | 1.0x (기준) |
분석: unordered_map이 3배 빠름.
테스트 3: 순회 (iteration)
template <typename Map>
void benchIteration(const Map& m) {
long long sum = 0;
for (const auto& [key, value] : m) {
sum += value;
}
}결과:
| 컨테이너 | 시간 | 상대 속도 |
|---|---|---|
| map | 25ms | 1.0x (기준) |
| unordered_map | 30ms | 1.2x (약간 느림) |
분석: 순회는 비슷함 (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 순회 | 25ms |
| unordered_map 순회 + 정렬 | 180ms |
분석: 정렬이 필요하면 map이 유리.
4. 메모리 사용량 비교
원소당 오버헤드
// map<int, int>
// [4바이트 키][4바이트 값][24바이트 트리 노드] = 32바이트
// 오버헤드: 24바이트 (300%)
// unordered_map<int, int>
// [4바이트 키][4바이트 값][8바이트 next 포인터][버킷 배열] = 16바이트 + α
// 오버헤드: 8바이트 + 버킷 배열 (100~200%)100만 개 저장 시 메모리
| 컨테이너 | 메모리 사용량 | 오버헤드 |
|---|---|---|
| map | 32MB | 300% |
| unordered_map | 16~24MB | 100~200% |
결론: unordered_map이 메모리 효율 약간 높음.
5. 상황별 선택 가이드
언제 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(),
{
return a.second < b.second;
});예제 2: 순위표 (Leaderboard)
// 요구사항: 점수순 정렬, 상위 10명 조회
// 권장: map (내림차순)
std::map<int, std::string, std::greater<int>> leaderboard; // 내림차순
leaderboard[100] = "Alice";
leaderboard[95] = "Bob";
leaderboard[98] = "Charlie";
// 상위 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) 삽입 → 매우 느림
}좋은 해시 함수
// ✅ 좋은 해시 함수 (균등 분포)
struct GoodHash {
size_t operator()(int key) const {
// FNV-1a 해시
size_t hash = 2166136261u;
hash ^= key;
hash *= 16777619u;
return hash;
}
};
std::unordered_map<int, int, GoodHash> um;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 > 1.0이면 재해싱 (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); // 간단한 조합
}
};
}
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 : "";
}
};이유: 조회가 빈번하고 정렬 불필요.
정리
선택 기준 요약
대부분의 경우: unordered_map을 사용하세요 (빠름)
예외 상황:
- 정렬이 필요 → map
- 범위 조회 → map
- 최악 성능 중요 → map
- 키가 복잡 → map (해시 함수 작성 어려움)
성능 순위
삽입: unordered_map (5배) > map 조회: unordered_map (3배) > map 순회: map ≈ unordered_map 정렬된 순회: map >>> unordered_map 메모리: unordered_map > map
핵심 규칙
- 기본은 unordered_map (빠름)
- 정렬이 필요하면 map
- reserve로 재해싱 방지 (unordered_map)
- 벤치마크로 검증 (추측하지 말고 측정)
- 커스텀 키는 해시 함수 작성 (unordered_map)
같이 보면 좋은 글 (내부 링크)
이 주제와 연결되는 다른 글입니다.
- C++ map 완벽 가이드 | 정렬된 맵 사용법
- C++ unordered_map 완벽 가이드 | 해시 테이블 사용법
- C++ 해시 함수 | 커스텀 해시 작성법
- C++ STL 컨테이너 선택 가이드
이 글에서 다루는 키워드 (관련 검색어)
map vs unordered_map, 해시 테이블, 성능 비교, 정렬된 맵, O(1) vs O(log n) 등으로 검색하시면 이 글이 도움이 됩니다.
실전 팁
실무에서 바로 적용할 수 있는 팁입니다.
디버깅 팁
- 성능 문제가 있으면 프로파일러로 확인하세요
- load_factor를 모니터링하세요 (> 1.0이면 충돌 많음)
- 해시 충돌을 bucket_count로 확인하세요
성능 팁
- unordered_map은 reserve로 재해싱을 방지하세요
- 정렬이 필요 없으면 unordered_map이 빠릅니다
- 원소가 적으면 (< 100) 차이가 거의 없습니다
코드 리뷰 팁
- map을 사용하는 코드는 정렬이 필요한지 물어보세요
- unordered_map은 reserve를 확인하세요
- 커스텀 키는 해시 함수를 확인하세요
마치며
map과 unordered_map의 선택은 정렬 필요 여부와 성능 요구사항에 달려 있습니다.
핵심 원칙:
- 기본은 unordered_map (빠름)
- 정렬이 필요하면 map
- reserve로 성능 향상 (unordered_map)
- 벤치마크로 검증
대부분의 경우 unordered_map이 3~5배 빠르지만, 정렬이나 범위 조회가 필요하면 map이 유일한 선택입니다. 프로젝트 요구사항을 먼저 파악하고, 벤치마크로 최종 결정하세요.
다음 단계: 컨테이너를 선택했다면, C++ 성능 최적화 가이드에서 더 깊이 최적화할 수 있습니다.
관련 글
- C++ 시리즈 전체 보기
- C++ Adapter Pattern 완벽 가이드 | 인터페이스 변환과 호환성
- C++ ADL |
- C++ Aggregate Initialization |