unordered_set과 unordered_map은 C++ 표준 라이브러리에서 제공하는 해시 기반 연관 컨테이너로, 삽입·탐색·삭제 연산의 평균 시간 복잡도가 O(1)인 특징을 가집니다. 이들은 정렬된 순서를 보장하지 않으며, 대신 키의 해시 값에 기반한 버킷 분배를 통해 고성능을 실현합니다.

기본 구조와 템플릿 매개변수

두 컨테이너는 다음과 같은 일반화된 템플릿 인터페이스를 따릅니다:

template <
    class Key,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<Key>
> class unordered_set;

template <
    class Key,
    class T,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<std::pair<const Key, T>>
> class unordered_map;

여기서 Hash는 키를 정수로 변환하는 해시 함수 객체이며, KeyEqual는 동일성 판별을 위한 비교 함수 객체입니다. 기본값으로 제공되는 std::hash와 std::equal_to는 대부분의 내장 타입 및 표준 컨테이너에 대해 사전 정의되어 있으나, 사용자 정의 타입의 경우 반드시 이 두 인터페이스를 명시적으로 구현해야 합니다.

정렬 기반 컨테이너와의 주요 차이점

• 정렬 여부: set/map은 적색-흑색 트리 기반으로 키가 오름차순 정렬되며, 반복자는 양방향 반복기입니다. 반면 unordered_set/unordered_map은 해시 테이블 기반이므로 키 순서가 보장되지 않으며, 반복기는 단방향입니다.
• 키 요구 조건: 정렬 컨테이너는 operator< 또는 사용자 정의 비교 함수를 필요로 하지만, 해시 컨테이너는 std::hash 적용 가능성과 == 연산자(또는 등가 비교 함수)를 요구합니다.
• 성능 특성: 평균적으로 해시 컨테이너가 더 빠르지만, 최악의 경우 O(n)까지 성능이 저하될 수 있습니다. 반면 트리 기반 컨테이너는 항상 O(log n)을 보장합니다.

실제 성능 측정 예제

다음 코드는 100만 개의 임의 정수를 대상으로 set과 unordered_set의 삽입 및 탐색 속도를 비교합니다:

#include <iostream>
#include <chrono>
#include <set>
#include <unordered_set>
#include <vector>
#include <random>

int main() {
    constexpr size_t N = 1'000'000;
    std::vector<int> data;
    data.reserve(N);

    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dist(1, N * 2);

    for (size_t i = 0; i < N; ++i) {
        data.push_back(dist(gen));
    }

    // set 성능 측정
    auto start = std::chrono::high_resolution_clock::now();
    std::set<int> sorted_container;
    for (int val : data) sorted_container.insert(val);
    auto end = std::chrono::high_resolution_clock::now();
    auto set_insert_ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();

    // unordered_set 성능 측정 (예비 용량 확보)
    start = std::chrono::high_resolution_clock::now();
    std::unordered_set<int> hash_container;
    hash_container.reserve(N); // 충돌 최소화를 위한 사전 확보
    for (int val : data) hash_container.insert(val);
    end = std::chrono::high_resolution_clock::now();
    auto us_insert_ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();

    std::cout << "set insert: " << set_insert_ms << " ms\n";
    std::cout << "unordered_set insert: " << us_insert_ms << " ms\n";

    // 탐색 성능 비교
    start = std::chrono::high_resolution_clock::now();
    size_t sorted_hits = 0;
    for (int val : data) {
        if (sorted_container.find(val) != sorted_container.end()) ++sorted_hits;
    }
    end = std::chrono::high_resolution_clock::now();
    auto set_find_ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();

    start = std::chrono::high_resolution_clock::now();
    size_t hash_hits = 0;
    for (int val : data) {
        if (hash_container.find(val) != hash_container.end()) ++hash_hits;
    }
    end = std::chrono::high_resolution_clock::now();
    auto us_find_ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();

    std::cout << "set find: " << set_find_ms << " ms (" << sorted_hits << " hits)\n";
    std::cout << "unordered_set find: " << us_find_ms << " ms (" << hash_hits << " hits)\n";

    return 0;
}

중복 허용 버전: unordered_multiset 및 unordered_multimap

unordered_multiset과 unordered_multimap은 동일한 키를 여러 번 저장할 수 있는 버전으로, multiset/multimap과 유사하게 동작하지만 해시 기반 구조를 유지합니다. 이들 역시 키 중복을 허용하며, count(), equal_range() 등의 멤버 함수를 통해 다수의 동일 키 값을 효율적으로 처리할 수 있습니다.

해시 정책 관리 인터페이스

컨테이너는 버킷 수(bucket_count()), 부하 계수(load_factor()), 재해시 트리거(max_load_factor()) 등을 제어하는 인터페이스를 제공합니다. 특히 rehash()와 reserve()를 통해 버킷 수를 미리 조정함으로써 충돌을 줄이고 성능을 안정화할 수 있습니다.