1. 탐색 동작: hash → bucket → ==
컨테이너의 내부 구조를 모르면 전형적인 함정에 쉽게 빠집니다:
- “갑자기 느려졌는데 왜?” (대부분 충돌 및 밀도 관련),
- “반복자가 동작을 멈췄다” (대개 어딘가에서 rehash가 발생),
- “순서가 '튀는' 이유” (구현상의 보장이 없기 때문).
내부 용어(bucket, load_factor, rehash)를 이해하는 것은 단순한 이론이 아니라 데이터 증가 시 깨지지 않는 코드를 쓰기 위한 방법입니다.
std::map에서는 키가 정렬(트리)되어 비교로 탐색합니다. 반면 unordered_*은 다른 철학을 가집니다: 키를 숫자(해시)로 바꿔, 그 숫자로 빠르게 “상자”를 선택합니다.
탐색의 두 단계
여기서 초보자의 기대를 깨는 중요한 점: 해시는 키가 일치함을 증명하지 않습니다. 해시는 단지 “저 상자를 보라”라고 알려줄 뿐입니다. 그 후 컨테이너는 두 번째 단계로 넘어갑니다: 동등성 프레디케이트(보통 ==)로 키들을 비교합니다.
unordered_*에 대한 요구사항은 보통 Hash와 Pred의 존재로 설명됩니다. 즉 '해셔'와 '동등성 검사기'입니다.
간단히 말하면, unordered_map은 대략 다음을 수행합니다:
key -> hash(key) -> bucket 번호 -> bucket 내부에서 ==로 선형 검색따라서 해시와 동등성 검사가 동시에 필요합니다.
3. 버킷과 충돌
bucket이라는 단어에 대해 이야기해봅시다. 한국어로는 보통 “버킷” 또는 “바구니”라고 합니다. 솔직히 말하면 “바구니”가 의미상 더 가깝습니다: 키들을 번호에 따라 바구니에 “던져 넣습니다”.
버킷이란 무엇인가
컨테이너는 일정 수의 바구니를 유지합니다: bucket_count(). 각 바구니는 0개 또는 여러 개의 요소를 보관합니다.
바구니가 충분히 많고 해시 함수가 적절하면 요소들은 비교적 균등하게 분포합니다: 각 바구니에 요소가 적어 탐색이 빠릅니다.
충돌은 정상적 상황이다
충돌은 서로 다른 키가 동일한 해시를 내거나 동일한 바구니에 들어갈 때 발생합니다. 이는 오류가 아니며 해시 테이블의 정상 운용 모드입니다. 따라서 unordered_map은 “해시가 같으니 키도 같다”라고 단정할 수 없고, 반드시 동등성 검사를 수행해야 합니다.
이해를 돕는 도식:
flowchart TD
A["Key: 'alice'"] --> B["hash('alice') = 123456"]
C["Key: 'bob'"] --> D["hash('bob') = 123999"]
E["Key: 'ALICE'"] --> F["hash('ALICE') = 123456 (collision)"]
B --> G["bucket = hash % bucket_count"]
D --> G
F --> G
G --> H["Inside bucket: compare keys via == (KeyEqual)"]
4. Load factor와 rehash
오늘의 가장 유용한 용어: load factor. 세탁기 용어처럼 느껴질 수 있지만—비슷합니다: “드럼이 얼마나 가득 찼나”라는 의미입니다.
load_factor(): 해시 테이블의 '밀도'
unordered_*에는 load_factor() 메서드가 있습니다. 개념은 매우 간단합니다:
load_factor ≈ size() / bucket_count()즉 “평균적으로 한 바구니에 얼마나 많은 요소가 있는가”입니다.
load_factor가 작으면 평균적으로 바구니별 요소 수가 적어 바구니 내부 검색(==로)이 짧습니다.
load_factor가 크면 바구니들이 붐비고 각 바구니 내부에서 많은 요소를 비교해야 합니다. 그러면 unordered_map은 기대하던 거의 O(1)이 아닌, O(N)에 가까운 동작을 보일 수 있습니다.
학습용 과제에서는 대개 치명적이지 않습니다. 그러나 수천·수만 건의 데이터를 다루기 시작하면, 프로파일러 없이도 “프로그램이 눈에 띄게 느려졌다”는 것을 체감하게 됩니다.
max_load_factor(): 컨테이너가 확장되는 임계값
컨테이너에는 설정 가능한 값도 있습니다: max_load_factor(). 이것은 컨테이너가 “이제 확장해야겠다”(즉 바구니 수를 늘린다)고 판단하는 '밀도 임계값'입니다.
실전에서는 다음과 같이 동작합니다: 요소를 삽입하면 size()가 증가하고 load_factor()가 증가합니다. 이 값이 max_load_factor를 넘으면 컨테이너는 rehash(재구성)를 수행할 수 있습니다.
rehash가 하는 일과 그 '영향'
컨테이너가 rehash를 할 때는 다음을 수행합니다:
- 바구니 수를 변경(보통 증가)합니다,
- 각 요소에 대해 이제 어느 바구니로 가야 하는지 다시 계산합니다,
- 요소들을 새 바구니로 옮깁니다.
왜 속도가 빨라질까요? bucket_count가 증가하고 보통 load_factor가 내려가기 때문입니다. 요소들은 더 많은 바구니로 분산되어 각 바구니 내부 비교가 줄어듭니다.
실용적인 부분: 재구성 중에 반복자가 무효화될 수 있습니다. 같은 요소처럼 보여도 위치가 바뀔 수 있습니다.
반복자 무효화 보장과 컨테이너 동작에 대한 표준 규정은 해가 지날수록 개선·명확해집니다. 핵심 엔지니어링 생각은 단순합니다: 컨테이너가 재구성될 수 있다면 반복자를 장기간 보관하는 것은 위험합니다, 특히 삽입이 활발할 때는 더더욱 그렇습니다.
5. 성장 제어: reserve, rehash 및 간단 진단
vector에서 reserve로 불필요한 재할당을 막듯이, unordered_*에도 유사한 아이디어가 있습니다. 단 의미가 약간 다릅니다: 미리 예상되는 요소 수에 맞춰 바구니를 준비해서 rehash가 덜 발생하게 합니다.
reserve와 rehash는 동일하지 않다
인터페이스 관점에서 비슷한 두 메서드를 보게 됩니다:
- rehash(n) — 최소 n개의 바구니를 요청합니다 (bucket count),
- reserve(n) — 현재 max_load_factor를 고려하여 n개의 요소에 대비하도록 요청합니다 (즉 size 기준).
실무에서는 보통 reserve가 더 편리합니다. '몇 개의 요소를 넣을 것인가'라는 사고를 하기 때문입니다.
bucket_count와 load_factor를 직접 확인해보기
지금 간단한 '진단' 코드를 보여드리겠습니다. 비즈니스 로직용이 아니라 컨테이너 동작을 이해하기 위한 코드입니다.
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, int> m;
std::cout << m.bucket_count() << '\n'; // 예: 1 (구현에 따라 다름)
m[10] = 1;
m[20] = 2;
std::cout << m.load_factor() << '\n'; // 예: 0.5
}숫자는 컴파일러/라이브러리마다 다를 수 있으며 이는 정상입니다. 중요한 것은 '마법 같은 특정 숫자(예: 13버킷)를 외우는 것'이 아니라 컨테이너가 자체적으로 상태를 가지며, 그 상태가 bucket_count와 load_factor로 표현된다는 점입니다.
간단 예: rehash는 자동으로 발생할 수 있다
짧은 예제로 'rehash는 이벤트다'라는 생각을 보여줍니다. 반복자 문제를 일부러 유발하지는 않겠고, 단지 bucket_count가 '튀는' 것을 관찰하겠습니다.
#include <iostream>
#include <unordered_set>
int main() {
std::unordered_set<int> s;
std::cout << s.bucket_count() << '\n'; // 이전 값
for (int i = 0; i < 100; ++i) s.insert(i);
std::cout << s.bucket_count() << '\n'; // 이후 값 (종종 증가)
}요점은 다음과 같습니다: 삽입으로 size()가 늘고 load_factor가 증가하면, 컨테이너는 '모든 걸 위한 한 개의 바구니'가 되지 않기 위해 확장할 수 있습니다.
6. 실습: id 기반 인덱스와 순회 순서
예제가 공중에 뜨지 않게, 강의에서 개발 중인 샘플 애플리케이션을 이어가겠습니다: TaskBoard — 콘솔 기반 작업 저장 프로그램입니다.
id로 빠른 인덱스 만들기
모델이 다음과 같다고 하겠습니다:
#include <string>
struct Task {
int id{};
std::string title;
};작업들은 std::vector<Task> tasks;에 보관합니다(순회, 출력, 정렬에 편리). 그러나 id로 빠르게 찾을 필요가 있습니다. 이를 위해 인덱스를 만듭니다:
#include <cstddef>
#include <unordered_map>
#include <vector>
std::vector<Task> tasks;
std::unordered_map<int, std::size_t> pos_by_id; // id -> vector 내 위치핵심은 다음입니다: 많은 작업을 로드할 때(예: 입력에서) 대강의 개수를 알고 있다면, 미리 unordered_map을 준비할 수 있습니다:
#include <unordered_map>
void prepare_index(std::unordered_map<int, std::size_t>& pos_by_id, std::size_t n) {
pos_by_id.reserve(n); // 성장 시 rehash 감소
pos_by_id.max_load_factor(0.7f); // 약간 더 '희박하게' 설정
}이것은 엔지니어링처럼 보이지만 실제로는 습관입니다: 데이터 크기를 미리 알면 내부 재구성 수를 줄일 수 있습니다.
unordered_*에서 순서에 기대면 안 되는 이유
std::map에서는 비교기를 통해 순회 순서가 정해지지만, unordered_*에서는 순회 순서가 보장되지 않습니다.
이것은 '바구니'의 본질에서 기인합니다: 요소들은 키의 증가 순이 아니라 해시 기준으로 배치됩니다. 더구나 rehash 후에는 바구니가 바뀌고 분포가 달라지므로 순서가 크게 변할 수 있습니다.
실용적인 규칙은 간단합니다: '키 순으로 예쁘게 출력하고 싶다면' map을 사용하거나 출력 전에 별도 정렬을 수행하세요.
7. unordered_* 사용 시 흔한 실수
실수 1: hash(a) == hash(b) 이면 a == b 라고 생각하는 것.
이것은 가장 흔한 논리적 함정 중 하나입니다. 해시는 바구니 선택 수단일 뿐 동등성의 증명이 아닙니다. 충돌은 정상이며, 따라서 unordered_*는 항상 바구니 내부에서 동등성 검사를 수행합니다. '나쁜 해시'는 많은 충돌을 만들어 비교 비용을 증가시키기에 컨테이너 성능을 저하시킵니다.
실수 2: load_factor를 무시하고 성능 저하에 놀라는 것.
초보자는 종종 '언제나 빠르다'고 생각합니다. 그러나 테이블이 지나치게 밀집하면(요소는 많고 바구니는 적음) 각 바구니 내부 탐색이 길어집니다. 이는 고장이 아니라 컨테이너가 정직하게 일하는 결과입니다. load_factor()와 max_load_factor()를 이해하면 이런 현상의 원리를 알 수 있습니다.
실수 3: 반복자/참조를 보관한 채로 활발히 삽입하는 것.
직접 rehash()를 호출하지 않더라도 삽입 중 자동으로 재구성이 발생할 수 있습니다. 그 결과 반복자나 참조가 무효화되어 '무작위 크래시'나 '가끔 사라지는 요소' 같은 버그가 생깁니다. 습관적으로 반복자를 보관하지 않거나, 삽입 규모를 정확히 안다면 미리 reserve를 호출하세요.
실수 4: unordered_map의 순회가 정렬되어 있다고 기대하는 것.
작은 데이터에서는 순서가 안정적으로 보일 수 있지만, 요소를 몇십 개 추가하면 출력이 달라질 수 있습니다. unordered_*의 순서는 구현의 부산물이지 계약이 아닙니다. 안정적 순서가 필요하면 요구사항에 맞는 자료구조를 선택하세요.
실수 5: reserve를 '값을 위한 메모리 예약'과 혼동하는 것.
unordered_*의 reserve(n)은 vector식 '값 저장소 메모리 예약'과는 다릅니다. 이는 삽입 시 n개의 요소에 대해 재구성이 자주 발생하지 않도록 바구니를 준비하는 것입니다. 간단히 기억하세요: vector::reserve는 배열 재할당을 줄이고, unordered_map::reserve는 rehash와 밀도 증가를 줄입니다.
GO TO FULL VERSION