unordered_map이란?
unordered_map은 C++ STL에서 제공하는 해시 테이블 기반의 연관 컨테이너입니다. 키-값 쌍을 저장하며, 키를 통해 값에 빠르게 접근할 수 있습니다.
주요 특징
시간 복잡도
- 평균: O(1) - 삽입, 삭제, 검색
- 최악: O(n) - 해시 충돌이 많을 때
map과의 차이점
map: 레드-블랙 트리 기반, 정렬됨, O(log n)unordered_map: 해시 테이블 기반, 정렬 안 됨, O(1)
기본 사용법
#include <unordered_map>
#include <string>
std::unordered_map<std::string, int> scores;
// 삽입
scores["Alice"] = 95;
scores.insert({"Bob", 87});
// 접근
int aliceScore = scores["Alice"];
// 검색
if (scores.find("Charlie") != scores.end()) {
// 존재함
}
// 삭제
scores.erase("Bob");성능 저하가 발생하는 경우
1. 해시 충돌 (Hash Collision)
서로 다른 키가 동일한 해시 값을 가질 때 발생합니다. 충돌이 많아지면 같은 버킷에 여러 원소가 체이닝되어 O(n)의 시간 복잡도로 저하됩니다.
발생 원인:
- 나쁜 해시 함수
- 데이터의 특성이 해시 함수와 맞지 않음
- 로드 팩터가 너무 높음
2. 로드 팩터(Load Factor) 과다
로드 팩터 = (저장된 원소 수) / (버킷 수)
기본 최대 로드 팩터는 1.0입니다. 이를 초과하면 자동으로 rehashing이 발생하여 성능 저하가 일어납니다.
unordered_map<int, int> map;
cout << "Load factor: " << map.load_factor() << endl;
cout << "Max load factor: " << map.max_load_factor() << endl;3. Rehashing 비용
원소가 추가되어 로드 팩터가 임계값을 넘으면 전체 해시 테이블을 재구성해야 합니다. 이 과정에서 모든 원소를 다시 해싱하므로 O(n) 시간이 소요됩니다.
4. 캐시 미스 (Cache Miss)
해시 테이블은 메모리상에 불연속적으로 저장되므로 순회 시 캐시 지역성이 낮아 성능이 저하될 수 있습니다.
5. 커스텀 타입의 비효율적인 해시 함수
struct Point {
int x, y;
};
// 나쁜 예: 항상 같은 값 반환
struct BadHash {
size_t operator()(const Point& p) const {
return 0; // 모든 충돌!
}
};성능 최적화 방법
1. reserve()로 사전 메모리 할당
원소 개수를 미리 알고 있다면 reserve()를 사용하여 rehashing을 방지합니다.
unordered_map<int, int> map;
map.reserve(10000); // 10000개 원소를 위한 공간 확보
for (int i = 0; i < 10000; ++i) {
map[i] = i * 2;
}2. 적절한 해시 함수 설계
좋은 해시 함수는 값들을 균등하게 분산시킵니다.
struct Point {
int x, y;
};
// 좋은 예: 비트 연산으로 균등 분산
struct GoodHash {
size_t operator()(const Point& p) const {
size_t h1 = std::hash<int>{}(p.x);
size_t h2 = std::hash<int>{}(p.y);
return h1 ^ (h2 << 1);
}
};
unordered_map<Point, string, GoodHash> pointMap;3. 로드 팩터 조정
더 많은 메모리를 사용하더라도 충돌을 줄이려면 최대 로드 팩터를 낮춥니다.
unordered_map<int, int> map;
map.max_load_factor(0.5); // 기본값 1.0에서 0.5로 변경4. 적절한 컨테이너 선택
unordered_map 사용이 적합한 경우:
- 빠른 검색이 필요할 때
- 순서가 중요하지 않을 때
- 데이터가 많고 O(1) 성능이 중요할 때
map 사용이 더 나은 경우:
- 정렬된 순서가 필요할 때
- 범위 검색이 필요할 때
- 데이터가 적어서 O(log n)도 충분할 때
- 캐시 지역성이 중요할 때
5. 커스텀 타입의 최적화된 비교 연산자
struct Point {
int x, y;
bool operator==(const Point& other) const {
return x == other.x && y == other.y;
}
};
// operator==를 정의해야 unordered_map이 정상 작동6. 메모리 재사용
unordered_map<int, int> map;
// 작업...
map.clear(); // 메모리는 유지됨
// 다시 사용 - rehashing 최소화실전 성능 비교 예제
#include <iostream>
#include <unordered_map>
#include <chrono>
void testWithoutReserve() {
auto start = std::chrono::high_resolution_clock::now();
std::unordered_map<int, int> map;
for (int i = 0; i < 1000000; ++i) {
map[i] = i;
}
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
std::cout << "Without reserve: " << duration.count() << "ms\n";
}
void testWithReserve() {
auto start = std::chrono::high_resolution_clock::now();
std::unordered_map<int, int> map;
map.reserve(1000000);
for (int i = 0; i < 1000000; ++i) {
map[i] = i;
}
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
std::cout << "With reserve: " << duration.count() << "ms\n";
}정리
unordered_map은 평균 O(1)의 뛰어난 성능을 제공하지만, 해시 충돌과 rehashing으로 인한 성능 저하를 주의해야 합니다. 사전에 reserve()를 호출하고, 적절한 해시 함수를 설계하며, 로드 팩터를 관리하면 최적의 성능을 얻을 수 있습니다.
상황에 따라 map과 unordered_map 중 적절한 것을 선택하는 것이 중요하며, 실제 성능은 벤치마킹을 통해 검증하는 것을 권장합니다.
