[Data Structure] Unordered Map

Unordered Map

📢 순서에 상관없이 Key-Value Pair들을 정렬해놓은 Map

---

Unordered Map 특징

• Map과 동일하게 Key-Value Pair들을 저장해요.
• Hash Table로 구현해요.
• 각각의 Key는 중복 없이 유일해야 해요.
• Collision이 일어날 수 있어요. (Hash Table 참고)

---

⏰ 시간 복잡도

탐색(Search), 삽입(Insert), 제거(Delete)

• Hash Map을 기반으로 구현되어 있어서 O(1)의 시간 복잡도를 가져요.

---

🎨 내부 메서드 (C++)

C++ STL 내부에 Unordered Map이 존재해요!
#include <unordered_map>을 헤더에 추가하시고 사용하면 됩니다.
변수 선언 방법은 아래와 같아요.

unordered_map<자료형, 자료형> 변수명;

대부분의 메소드는 Map과 동일한 메소드를 가지고 있어요!! 아래의 몇가지만 추가 되었답니다.

메소드 이름	역할
begin, end	Map의 처음과 끝의 Iterator 반환
empty	Map 내부가 비어있는지 여부를 반환
size	Map의 크기를 반환
[], at	Map의 특정 Key를 가진 데이터에 접근
insert	Map에 데이터 추가
erase	Map에서 데이터 제거
clear	Map 내부 요소 전부 제거
swap	Map끼리 내부 데이터 교환
find	특정 Key값을 가진 데이터를 반환
bucket_count	Bucket 개수를 반환
load_factor	Load Factor을 반환
rehash	Hash Table을 Rehash
hash_function	Hash Fucntion을 반환

---

아래는 위의 메소드를 적용한 예제예요.

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
    unordered_map<string, int> newMap;
    /*---------------Insert Method----------------------*/
    newMap.insert(pair<string, int>("Apple", 1000));
    newMap.insert(pair<string, int>("Grape", 4000));
    newMap["Peach"] = 5000;
    newMap["Banana"] = 2000;
    // insert는 Key가 중복이 되면 에러를 발생
    // []는 Key가 중복이 되면 값을 Update
    /*--------------------------------------------------*/

    /*---------------Find Method------------------------*/
    cout << newMap.find("Banana")->second << endl;
    cout << newMap.find("Peach")->first << endl;
    /*--------------------------------------------------*/

    /*---------------Bucket_count-----------------------*/
    cout << "We have " << newMap.bucket_count() << " buckets." << endl;
    /*--------------------------------------------------*/

    /*---------------Load_Factor------------------------*/
    cout << "The Load Factor is " << newMap.load_factor() << " now. " << endl;
    /*--------------------------------------------------*/

    /*---------------ReHash-----------------------------*/
    newMap.rehash(20);
    // Hash Table 크기를 새로 지정해준다
    /*--------------------------------------------------*/

    /*---------------Hash_Function----------------------*/
    unordered_map<string, int>::hasher fn = newMap.hash_function();

    cout << "Lotte : " << fn("Lotte") << endl;
    cout << "LG : " << fn("LG") << endl;
    // Hash_Function으로 Hash 값을 알 수 있다.
    /*--------------------------------------------------*/

    /*---------------[], at Method----------------------*/
    cout << newMap["Peach"] << endl;
    cout << newMap.at("Banana") << endl;
    /*--------------------------------------------------*/

    /*---------------Size Method------------------------*/
    cout << newMap.size() << endl;
    /*--------------------------------------------------*/

    /*---------------Begin, End Method------------------*/
    for(auto iter = newMap.begin(); iter != newMap.end(); iter++) {
        cout << iter->first << " ";
        cout << iter->second << endl;
    }
    /*--------------------------------------------------*/

    /*---------------Erase Method-----------------------*/
    newMap.erase("Grape");
    /*--------------------------------------------------*/

    /*---------------Clear Method-----------------------*/
    newMap.clear();
    /*--------------------------------------------------*/

    /*---------------Empty Method-----------------------*/
    if(newMap.empty())
        cout << "Unordered_Map is empty!!" << endl;
    else
        cout << "Unordered_Map is not empty!!!" << endl;
    /*--------------------------------------------------*/
}