std::unordered_map

unordered_map의 본질

• std::unordered_map<Key, T>는 해시 테이블 기반 키-값 컨테이너입니다.
• 키는 중복 불가이며, 순서는 정렬되지 않습니다.
• 평균적으로 find/insert/erase가 O(1)이라 조회 중심 작업에 강합니다.
• #include <unordered_map>

std::unordered_map<int, std::string> users;
users.emplace(100, "Alice");
users.emplace(200, "Bob");

---

내부 구조: hash -> bucket

키는 해시 함수로 정수 해시값으로 바뀌고, 버킷 인덱스로 매핑됩니다.

key = "player_100"
hash(key) = 123456
bucket_index = hash(key) % bucket_count

버킷 배열:
[0] [1] [2] ... [42] ... [99]
              ▲
              └─ 같은 버킷에 여러 키가 모일 수 있음(충돌)

• 같은 버킷에 여러 원소가 모이면 충돌이 발생합니다.
• 표준 구현체는 보통 체이닝 기반으로 충돌을 처리합니다.

---

성능 핵심: Load Factor와 Rehash

• load_factor = size / bucket_count
• load_factor가 너무 커지면 충돌이 늘어 성능이 떨어집니다.
• 임계치(max_load_factor)를 넘으면 재배치(rehash)가 일어납니다.

std::unordered_map<std::string, int> freq;
freq.reserve(100000);        // 예상 원소 수를 미리 확보 (rehash 감소)
freq.max_load_factor(0.7f);  // 충돌을 더 줄이고 싶을 때 (선택)

핵심 포인트:

• reserve(n)는 "n개를 넣어도 버틸 버킷 수"를 미리 확보합니다.
• rehash는 한 번에 O(N) 비용이 들 수 있으므로, 대량 삽입 전 reserve가 유리합니다.

---

기본 사용 패턴

std::unordered_map<int, std::string> mp;

mp.insert({1, "one"});
mp.emplace(2, "two");
mp.try_emplace(3, "three");      // C++17
mp.insert_or_assign(2, "TWO");   // C++17

if (auto it = mp.find(2); it != mp.end()) {
    std::cout << it->second << '\n';
}

bool has3 = mp.contains(3); // C++20

• operator[]는 키가 없으면 삽입을 일으킵니다(map과 동일한 함정).

---

시간 복잡도

연산	평균	최악	비고
find, insert, erase	O(1)	O(N)	충돌이 심하면 최악 악화
rehash, reserve로 인한 재배치	-	O(N)	단발성 비용
순회 전체	O(N)	O(N)	순서는 비결정적

---

순서/이터레이터 주의점

• unordered_map은 키 정렬을 보장하지 않습니다.
• 삽입/삭제/rehash 이후 순회 순서는 쉽게 바뀔 수 있습니다.
• 순서가 중요하면 map을 사용해야 합니다.

이터레이터 무효화 감각:

• insert/emplace: rehash가 발생하면 모든 이터레이터 무효화 가능
• erase: 삭제된 원소 이터레이터만 무효화
• rehash/reserve: 모든 이터레이터 무효화

---

커스텀 키 사용 (해시 함수 제공)

사용자 정의 타입을 키로 쓰려면 해시 함수와 동등 비교가 필요합니다.

struct PlayerKey {
    int worldId;
    int playerId;
    bool operator==(const PlayerKey& rhs) const {
        return worldId == rhs.worldId && playerId == rhs.playerId;
    }
};

struct PlayerKeyHash {
    size_t operator()(const PlayerKey& k) const noexcept {
        return (static_cast<size_t>(k.worldId) * 1315423911u)
             ^ static_cast<size_t>(k.playerId);
    }
};

std::unordered_map<PlayerKey, int, PlayerKeyHash> hpByPlayer;

---

map vs unordered_map 선택 기준

상황	권장
키 정렬/범위 검색(lower_bound) 필요	map
평균 조회 성능 최우선, 순서 불필요	unordered_map
최악 성능 예측 가능성 중시	map
대량 키-값 캐시/카운팅	unordered_map + reserve

---

자주 하는 실수 + 체크 질문

자주 하는 실수

실수	문제
정렬 순회를 기대하고 unordered_map 사용	결과 순서가 실행/상태에 따라 달라짐
대량 삽입 전에 reserve 생략	rehash 반복으로 성능 저하
조회 코드에서 operator[] 사용	의도치 않은 삽입 발생
해시 품질이 낮은 커스텀 키 사용	충돌 증가로 O(N)에 가까워짐

체크 질문 (스스로 답해보기)

• load_factor가 커지면 왜 성능이 떨어지는가?
• unordered_map에서 reserve를 언제 호출하는 것이 효과적인가?
• 순서가 필요한 기능에 unordered_map이 부적합한 이유는?

---