C++ unordered_map: 빠른 해시 맵 조회 완벽 설명

순서가 중요하지 않을 때

방금 std::map을 봤습니다. 균형 트리를 사용해 키를 정렬된 상태로 유지하고 O(log n) 연산을 제공하죠. 하지만 정렬에는 비용이 들고, 많은 경우 키가 어떤 순서로 나오는지는 신경 쓰지 않습니다. 그저 "이 키가 여기 있는가, 그 값은 무엇인가?"를 최대한 빠르게 묻고 싶을 뿐입니다.

바로 그것을 위한 것이 std::unordered_map입니다. 이것은 해시 테이블입니다. 각 키를 해시 함수에 통과시켜 저장 위치를 정하므로, 삽입·조회·삭제가 O(log n)이 아니라 **평균 O(1)**이 됩니다. 그 대가로 순회 순서는 명시되지 않습니다. 키는 버킷이 보관하고 있는 순서대로 나옵니다.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> stock = {
        {"apple", 12},
        {"banana", 7},
        {"cherry", 30}
    };

    cout << "bananas: " << stock["banana"] << "\n";
    stock["apple"] += 5;
    cout << "apples now: " << stock["apple"] << "\n";
}

인터페이스는 의도적으로 map과 거의 동일합니다. 흔히 타입만 바꿔 한쪽을 다른 쪽으로 교체할 수 있습니다. <map>이 아니라 <unordered_map>을 포함하면 키가 정렬되지 않은 상태로 나옵니다.

삽입과 갱신

항목을 넣는 방법은 여러 가지이고, 모두 같은 방식으로 동작하지는 않습니다. 가장 많이 쓰게 될 두 가지는 operator[]와 insert입니다.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> votes;

    votes["alice"] = 3;              // 생성 또는 덮어쓰기
    votes["alice"] = 5;              // 덮어쓰기 -> 5
    votes.insert({"bob", 2});        // "bob"이 없을 때만 삽입
    votes.insert({"bob", 99});       // 무시됨, "bob"은 이미 존재

    cout << "alice: " << votes["alice"] << "\n";   // 5
    cout << "bob:   " << votes["bob"] << "\n";      // 99가 아니라 2
}

핵심 차이는 이렇습니다. operator[]는 기존 값을 덮어쓰지만, insert는 이미 있는 키를 건드리지 않습니다. C++17이라면 insert_or_assign(key, value)는 "무조건 이것으로 설정한다"는 의미를 주고, try_emplace(key, args...)는 키가 새로울 때만 값을 제자리에서 생성합니다. 생성 비용이 큰 값에 유용합니다.

operator[]의 함정: 읽을 때 삽입한다

이것은 가장 흔한 unordered_map 버그라서 별도의 절을 둡니다. m[key]는 순수한 읽기가 아닙니다. 키가 없으면 기본 생성하여 삽입하고(int는 0이 되고, string은 ""이 됩니다) 참조를 반환합니다. 그래서 조회처럼 보이는 코드가 맵을 슬그머니 키웁니다.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> seen;
    seen["x"] = 1;

    // "y"를 확인만 하려 했는데 []가 삽입해 버렸다:
    if (seen["y"] == 0) {
        cout << "y looked missing...\n";
    }

    cout << "size is now " << seen.size() << "\n";   // 1이 아니라 2!
}

seen["y"]는 언급된 것만으로 "y" -> 0 항목을 만들었습니다. 맵을 변경하지 않고 존재를 검사하려면 count(0 또는 1을 반환)나 find를 사용하세요.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> seen{{"x", 1}};

    if (seen.count("y")) {
        cout << "found y\n";
    } else {
        cout << "no y, size still " << seen.size() << "\n";   // 1
    }

    // C++20: contains()는 count()보다 깔끔하게 읽힌다
    if (seen.contains("x")) cout << "x is here\n";
}

경험칙: []는 생성하거나 갱신할 의도가 있을 때만 사용하세요. 순수 읽기에는 count, contains(C++20), 또는 find를 사용합니다.

find와 at: 안전한 조회

find는 항목에 대한 반복자를 반환하고, 키가 없으면 end()를 반환합니다. 절대 삽입하지 않으며, 한 번의 조회로 it->first와 it->second를 통해 키와 값 모두에 접근하게 해 줍니다.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> prices = {{"pen", 2}, {"mug", 9}};

    auto it = prices.find("mug");
    if (it != prices.end()) {
        cout << it->first << " costs " << it->second << "\n";
    } else {
        cout << "not found\n";
    }
}

키가 존재해야 한다고 확신하고 없을 때 확실히 실패하길 원한다면 at을 사용하세요. []와 달리 at은 삽입하지 않습니다. 없는 키에 대해 std::out_of_range를 던집니다.

int p = prices.at("pen");   // 정상
int q = prices.at("hat");   // std::out_of_range를 던짐 - 키가 없음

그래서 조회 방식이 세 가지 있습니다. [](삽입함), at(던짐), 그리고 find/count(맵을 건드리지 않고 존재를 알림)입니다. 실패 방식이 의도에 맞는 것을 선택하세요.

순회와 삭제

구조적 바인딩을 사용한 범위 기반 for 루프는 모든 항목을 깔끔하게 도는 방법입니다. 순서는 임의라는 점을 기억하고, 절대 의존하지 마세요.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 7}, {"green", 2}};

    for (const auto& [team, score] : wins) {
        cout << team << ": " << score << "\n";   // 순서는 명시되지 않음
    }
}

항목을 제거하려면 erase가 키를 직접 받아 제거된 개수(0 또는 1)를 반환합니다. 중요한 함정: unordered_map에서 순회 중 삭제는 삭제된 원소의 반복자만 무효화하므로, 안전하게 진행하려면 erase(it)의 반환값을 사용하세요.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 1}, {"green", 2}};

    // 점수가 3 미만인 팀을 모두 제거
    for (auto it = wins.begin(); it != wins.end(); ) {
        if (it->second < 3)
            it = wins.erase(it);   // erase는 다음 유효 반복자를 반환
        else
            ++it;
    }

    cout << "remaining entries: " << wins.size() << "\n";
}

wins.erase(it++) 식으로 쓰거나 평범한 erase(it) 뒤에 ++it를 하는 것은 전형적인 댕글링 반복자 함정입니다. 삭제된 반복자는 죽었으니, 항상 erase가 반환한 반복자를 받으세요.

map인가 unordered_map인가?

둘 다 비슷한 API로 키-값 쌍을 저장하므로, 선택은 무엇이 필요한지에 달려 있습니다.

// std::map            -> 정렬된 키, O(log n), 범위 질의 (lower_bound)
// std::unordered_map  -> 순서 없음, 평균 O(1), 가장 빠른 단순 조회

키로 빠르게 조회만 하면 되고 순서가 무관할 때(단어 빈도 세기, 캐싱, 중복 제거)는 unordered_map을 선택하세요. 키가 정렬된 순서로 필요하거나, 순서대로 순회하거나, 범위 질의를 하려면 map을 선택하세요. unordered_map의 두 가지 주의점: 그 O(1)은 평균이며(나쁜 해시가 악화시킬 수 있음), 사용자 정의 키 타입에는 해시 특수화나 해시 함수 객체가 필요한 반면 map은 operator<만 있으면 됩니다.

다음: Set

이제 키-값 컨테이너의 두 가지 형태를 모두 봤습니다. 하지만 때로는 값이 전혀 필요 없을 때가 있습니다. 고유한 태그 모음이나 방문한 ID처럼, 무언가가 존재하는지만 중요한 경우입니다. 다음으로 std::set(그리고 해시 기반 사촌인 unordered_set)을 살펴보겠습니다. 이들은 키만 저장하고 자동으로 고유하게 유지합니다.