C++ ] std::unordered_map과 std::map의 차이, unordered_map의 사용법

 

 

 

 

std::unordered_map

 

unordered_map은 STL에서 제공하는 해시 테이블 기반의 키-값 쌍을 저장하는 컨테이너로, 사용법은 map과 유사하지만 몇 가지 차이점이 있다.

 

 

내부 구현:

• map은 균형 이진 검색 트리(레드-블랙 트리)를 사용하여 요소를 저장한다.
• unordered_map은 해시 테이블을 사용하여 요소를 저장한다.

 

접근 시간:

• map에서 키-값 쌍에 접근하는 데 걸리는 시간은 O(log n)이다.
• unordered_map은 평균적으로 상수 시간 O(1)에 키-값 쌍에 접근할 수 있다. 단, 해시 충돌이 발생할 경우 최악의 경우 시간 복잡도는 O(n)에 수렴한다.

 

정렬:

• map은 키에 대해 < 연산자를 사용하여 오름차순으로 정렬된 순서를 유지한다.
• unordered_map은 입력된 순서나 키에 대한 정렬을 유지하지 않고, 해시 함수의 결과에 따라 내부적으로 정렬되므로 불규칙적으로 보일 수 있다.

 

사용 사례:

• 정렬된 순서로 키-값 쌍을 유지해야 하거나, 키의 순서에 따라 순회해야 할 경우 map을 사용한다.
• 반면에 순서가 중요하지 않고 키에 대한 빠른 접근이 필요한 경우 unordered_map이 유용하다.

 

 

 

unordered_map의 사용법

map과 차이가 없다.

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;

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

    // 삽입
    ageMap["Alice"] = 30;
    ageMap.insert({"Bob", 25});
    ageMap.emplace("Charlie", 35);

    // 접근
    cout << "Alice's age: " << ageMap["Alice"] << endl;

    // 탐색
    auto search = ageMap.find("Bob");
    if (search != ageMap.end()) {
        cout << "Found Bob, age: " << search->second << endl;
    } else {
        cout << "Bob not found" << endl;
    }

    // 삭제
    ageMap.erase("Charlie");

    // 순회
    for (const auto& pair : ageMap) {
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

 

 

 

 

 

해시 충돌이란?

 

두 개의 서로 다른 키가 우연히 같은 해시 값을 가지게 되는 경우를 해시 충돌이라고 한다. unordered_map의 경우 해시충돌이 발생하면 체이닝(Chaining) 방식을 사용해 해시 충돌을 처리하는데, 체이닝은 같은 해시 값을 가진 요소들을 링크드 리스트로 연결해서, 여러 키-값 쌍이 같은 해시 버킷 내에서 관리될 수 있도록 하는 방식이다.

 

해시 충돌이 발생했을 때의 처리 과정을 살펴보면 먼저 unorderd_map에 새로운 키-값 쌍을 삽입하려고 할 때, 키 데이터 타입의 해시 함수를 통해 해시 값을 계산하고 계산된 해시 값에 해당하는 버킷을 찾아 키-값쌍을 저장하려고 시도한다. 만약 이 때 해당 버킷에 이미 다른 키-값 쌍이 존재한다면(즉, 해시 충돌이 발생한 경우) 새로운 키-값 쌍은 해당 버킷에 연결된 리스트에 추가되어 관리된다. 때문에 충돌이 빈번하게 발생할 경우 버킷의 리스트를 다 뒤져야 하므로 성능이 저하될 수 있는 것이다.

 

 

 

 

 

사용자 정의 타입으로 unordered_map 사용시 해시 함수 구현하기

 

int, float, string 같은 기본 데이터 타입은 해시 함수를 내장하고 있어 개발자가 신경쓸 게 없지만, pair<string, int> 같은 복합 타임이나 사용자 정의 타입(클래스나 구조체)를 키로 사용하려면 해당 타입에 대한 해시 함수를 직접 정의하고 unordered_map에 제공해야 한다. 또한 사용자 정의 타입을 키로 쓸 때는 키가 동일한지 비교하기 위해 == 연산자도 재정의 해주어야 한다.

 

 

pair<템플릿1, 템플릿2> 타입을 키로 사용하는 경우 예시.

 

다음 예시는 사용자 정의 해시 함수 객체를 정의하고 operator()를 오버로딩하여 객체를 함수처럼 호출할 수 있게한다. 함수의 내용은 키로 사용되는 객체에 대한 해시 값을 계산해 retrun하도록 구현한다.

 

그리고 unordered_map의 세 번째 템플릿 인자로 정의한 함수 객체를 넘긴다. 이렇게 지정해주면 unordered_map 내부적으로 해당 해시 함수 객체를 인스턴스화하여 사용한다.

 

#include <iostream>
#include <unordered_map>
#include <string>

using namesapce std;
// 사용자 정의 해시 함수 객체
struct PairHash {
    template <class T1, class T2>
    size_t operator () (const pair<T1,T2> &pair) const {
        auto hash1 = hash<T1>{}(pair.first);
        auto hash2 = hash<T2>{}(pair.second);
        // T1, T2가 해시함수를 내장한 데이터 타입일 때
        // pair<T1, T2> 타입에 대한 유일한 해시값을 계산하여 size_t 타입으로 반환한다.
        return hash1 ^ hash2;
    }
};

int main() {
    unordered_map<pair<string, int>, string, PairHash> myMap;

    // 원소 추가
    myMap[{ "Alice", 30 }] = "Developer";
    myMap[{ "Bob", 25 }] = "Designer";

    // 원소 접근
    cout << "{ \"Alice\", 30 } is a " << myMap[{ "Alice", 30 }] << endl;

    return 0;
}

 

 

 

사용자 정의 구조체를 unordered_map의 키로 사용하는 경우의 예시.

 

위의 예시에서 pair는 기본적으로 operator==를 정의하고 있기 때문에 따로 재정의할 필요가 없었지만 사용자 정의 타입의 경우 키를 비교하기 위해 ==연산자도 재정의하여 제공해야한다.

 

#include <iostream>
#include <unordered_map>
#include <string>

using namespace std;
// 사용자 정의 구조체
struct Person {
    string name;
    int age;

    Person(string n, int a) : name(n), age(a) {}

    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

// Person 타입에 대한 해시 함수 객체
struct PersonHash {
    size_t operator()(const Person& p) const {
        return hash<string>()(p.name) ^ (hash<int>()(p.age) << 1);
    }
};

int main() {
    unordered_map<Person, string, PersonHash> myMap;

    // 원소 추가
    myMap[Person("Alice", 30)] = "Developer";
    myMap[Person("Bob", 25)] = "Designer";

    // 원소 접근
    for (const auto& entry : myMap) {
        cout << entry.first.name << ", " << entry.first.age << " is a " << entry.second << endl;
    }

    return 0;
}