std::unordered_map을 처음 배울 때 가장 많이 듣는 설명은 “key로 value를 평균 O(1)에 찾는 container”입니다.
이 설명은 맞지만, 실무 코드에서는 이 한 문장만 기억하면 성능 문제를 놓치기 쉽습니다.
std::unordered_map의 성능은 hash function, bucket 개수, load factor, rehash 시점에 영향을 받기 때문입니다.
std::unordered_map은 빠른 container가 아니라, 좋은 hash 분포와 적절한 bucket 관리가 있을 때 평균적으로 빠르게 동작하는 container입니다.
이번 글에서는 std::unordered_map이 내부적으로 어떤 흐름으로 값을 찾는지, collision과 rehash가 왜 중요한지, 그리고 C++17 코드에서 어떤 점을 조심해야 하는지 정리해보겠습니다.
std::unordered_map의 핵심은 key를 hash로 변환한 뒤 bucket에서 후보를 좁혀 value를 찾는 흐름입니다.
1. std::unordered_map은 무엇을 약속하나?
std::unordered_map은 key와 value를 저장하는 associative container입니다.
std::map이 key를 정렬된 tree 구조로 관리한다면, std::unordered_map은 key의 hash 값을 이용해 bucket을 고르고 그 안에서 값을 찾습니다.
그래서 key 순회 순서는 정렬되어 있지 않고, 삽입 순서도 보장되지 않습니다.
| 구분 |
std::map |
std::unordered_map |
| 기반 구조 |
balanced tree |
hash table |
| 탐색 복잡도 |
O(log n) |
평균 O(1), 최악 O(n) |
| 순회 순서 |
key 기준 정렬 |
정렬 보장 없음 |
| 주요 관심사 |
비교 함수, 정렬 순서 |
hash 분포, collision, rehash |
std::unordered_map을 고를 때는 “정렬이 필요 없는가?”와 “key의 hash 분포가 괜찮은가?”를 같이 봐야 합니다.
정렬된 순회가 필요하거나 범위 탐색이 중요하면 std::map이 더 자연스러울 수 있고, 단일 key lookup이 압도적으로 많으면 std::unordered_map이 좋은 선택이 될 수 있습니다.
2. 왜 항상 O(1)이 아닌가?
std::unordered_map의 평균 O(1)은 hash가 key를 bucket에 고르게 분산시킨다는 전제가 있을 때 의미가 있습니다.
서로 다른 key가 같은 bucket으로 몰리면 collision이 생깁니다.
collision이 조금 있는 것은 자연스러운 일이지만, 특정 bucket에 값이 과도하게 몰리면 그 bucket 안에서 후보를 다시 비교해야 합니다.
- key로 hash 값을 계산한다.
- hash 값을 bucket index로 변환한다.
- 해당 bucket 안의 element를 확인한다.
- 같은 bucket에 여러 element가 있으면 key equality로 다시 비교한다.
즉, 평균적으로는 bucket 하나만 보면 되지만, hash 분포가 나쁘면 한 bucket 안에서 많은 element를 훑게 됩니다.
이 경우 std::unordered_map은 이름과 달리 사실상 긴 list를 뒤지는 것처럼 느려질 수 있습니다.
3. bucket과 load factor로 이해하기
std::unordered_map을 볼 때 중요한 값은 bucket_count, size, load_factor입니다.
load_factor는 현재 element 수를 bucket 수로 나눈 값입니다.
| 항목 |
의미 |
활용 |
| size() |
저장된 element 개수 |
데이터가 얼마나 들어갔는지 확인 |
| bucket_count() |
현재 bucket 개수 |
hash table이 어느 정도 공간을 확보했는지 확인 |
| load_factor() |
size / bucket_count |
bucket당 평균 element 밀도를 확인 |
| max_load_factor() |
rehash를 유도하는 기준값 |
밀도가 너무 높아지기 전 bucket을 늘리는 기준 |
| reserve(n) |
n개 element를 담을 수 있게 준비 |
대량 삽입 전에 불필요한 rehash를 줄임 |
element가 늘어나 load_factor가 높아지면 container는 bucket을 늘리기 위해 rehash를 수행할 수 있습니다.
rehash는 기존 element를 새 bucket 배열 기준으로 다시 배치하는 작업입니다.
이 작업은 순간적으로 비용이 크고, 기존 iterator를 무효화할 수 있습니다.
collision은 여러 key가 같은 bucket에 모이는 상황이고, rehash는 bucket 배열을 키워 element를 다시 배치하는 작업입니다.
4. C++17 코드로 rehash 확인해보기
다음 코드는 작은 용량으로 시작한 std::unordered_map에 많은 element를 넣어서 rehash가 발생했는지 확인합니다.
bucket_count의 정확한 값은 구현체마다 다를 수 있으므로, 예제에서는 값 자체보다 bucket 개수가 바뀌었는지를 봅니다.
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<int, std::string> users;
users.max_load_factor(0.7f);
users.reserve(4);
const auto first_bucket_count = users.bucket_count();
for (int id = 1; id <= 50; ++id) {
users.emplace(id, "user-" + std::to_string(id));
}
const bool rehashed = users.bucket_count() != first_bucket_count;
const auto user = users.find(20);
std::cout << std::boolalpha;
std::cout << "rehash happened: " << rehashed << '\n';
std::cout << "contains 20: " << (user != users.end()) << '\n';
if (user != users.end()) {
std::cout << "user 20: " << user->second << '\n';
}
}
실행 결과
rehash happened: true
contains 20: true
user 20: user-20
여기서 중요한 점은 reserve(4)를 했더라도 50개를 넣는 동안 bucket 배열이 계속 그대로 유지된다는 뜻은 아니라는 것입니다.
container는 max_load_factor를 넘지 않도록 필요할 때 bucket을 늘립니다.
그래서 대량 삽입이 예상된다면 실제 예상 개수에 가깝게 reserve를 호출해 rehash 횟수를 줄이는 편이 좋습니다.
5. 코드에서 봐야 할 핵심
std::unordered_map을 사용할 때는 container API만 보는 것이 아니라 성능과 invalidation 조건도 같이 봐야 합니다.
| 상황 |
주의할 점 |
| 대량 insert |
예상 element 수를 알고 있으면 reserve를 먼저 호출해 rehash 횟수를 줄인다. |
| iterator 보관 |
insert 중 rehash가 발생하면 iterator가 무효화될 수 있으므로 오래 들고 있지 않는다. |
| reference 보관 |
rehash가 element 자체를 새로 생성하는 것은 아니므로 reference와 pointer는 보통 유지되지만, erase 대상은 당연히 무효화된다. |
| custom key 사용 |
hash와 equality가 서로 일관되게 동작해야 한다. |
| 순서 의존 코드 |
순회 순서가 정렬이나 삽입 순서를 의미한다고 가정하면 안 된다. |
특히 iterator invalidation은 버그로 이어지기 쉽습니다.
반복문 안에서 insert를 수행하면서 기존 iterator를 계속 사용하는 코드는 rehash 조건을 만나면 위험해질 수 있습니다.
필요하다면 먼저 reserve를 호출하거나, insert 단계와 순회 단계를 분리하는 식으로 흐름을 단순하게 만드는 편이 안전합니다.
6. 자주 하는 오해
- 오해 1. unordered_map은 무조건 map보다 빠르다.
단일 lookup이 많고 hash 분포가 좋으면 빠를 가능성이 큽니다. 하지만 정렬 순회, 범위 탐색, 작은 데이터, 나쁜 hash 분포에서는 std::map이 더 낫거나 차이가 작을 수 있습니다.
- 오해 2. 평균 O(1)이면 성능을 신경 쓰지 않아도 된다.
평균 O(1)은 collision과 rehash 비용이 관리된다는 전제 위에 있습니다. 대량 삽입 경로에서는 reserve 여부가 체감 성능에 영향을 줄 수 있습니다.
- 오해 3. bucket_count가 크면 항상 좋다.
bucket이 너무 많으면 메모리 사용량과 cache 효율이 나빠질 수 있습니다. 적절한 load factor와 데이터 크기를 같이 봐야 합니다.
- 오해 4. std::hash는 보안용 hash다.
std::hash는 hash table용 hash입니다. 외부 입력이 공격적으로 들어오는 환경에서는 hash flooding 같은 가능성을 별도로 고려해야 합니다.
std::unordered_map은 편리한 기본 선택지가 될 수 있지만, 모든 key-value 문제의 정답은 아닙니다.
정렬 필요 여부, 데이터 크기, key 특성, 삽입 패턴을 같이 보고 선택해야 합니다.
7. 실무에서는 어떻게 볼까?
실무에서 std::unordered_map이 가장 잘 맞는 경우는 id, name, token처럼 정확한 key로 값을 바로 찾는 lookup이 많을 때입니다.
예를 들어 user id로 profile을 찾거나, symbol로 metadata를 찾거나, 문자열 command를 handler에 연결하는 구조가 여기에 해당합니다.
반대로 key 순서대로 출력해야 하거나, 특정 범위의 key를 자주 찾아야 하거나, 데이터가 매우 작아 container overhead가 더 크게 보이는 상황이라면 다른 container도 비교해야 합니다.
성능 이슈가 의심될 때는 단순히 std::map을 std::unordered_map으로 바꾸기보다 bucket_count, load_factor, reserve 호출 여부, custom hash 품질을 먼저 확인하는 편이 좋습니다.
특히 대량 데이터 적재 경로에서는 “삽입 전에 reserve를 했는가?”라는 질문 하나만으로 불필요한 rehash 비용을 크게 줄일 수 있습니다.
8. 정리
std::unordered_map은 hash table 기반의 key-value container입니다.
평균 lookup은 O(1)이지만, hash collision이 심하면 최악 O(n)까지 느려질 수 있습니다.
load_factor가 높아지면 rehash가 발생할 수 있고, 이때 iterator가 무효화될 수 있습니다.
대량 삽입 전에는 예상 element 수에 맞춰 reserve를 호출하는 것이 좋습니다.
정렬 순회나 범위 탐색이 필요하면 std::map 같은 다른 container가 더 적합할 수 있습니다.
std::unordered_map을 잘 쓰는 기준은 “정렬이 필요 없는 key lookup인가, 그리고 hash 분포와 rehash 비용을 관리할 수 있는가?”입니다.