[Set, Map / Hash] std::unordered_map

 

 

unordered_map 

1. unordered_map이란?

• 이전 시간에는 unordered_set(해시 셋)에 대해 알아보았다.
• 이번에는 동일하게 해시(Hash) 기반 구조를 사용하면서 키(Key)와 값(Value)의 관계를 저장하는 unordered_map 에 대해 알아본다.

기존에 배운 map은:

• Key + Value 구조
• 내부적으로 트리(Red-Black Tree) 사용
• 정렬된 상태 유지
• 삽입, 삭제, 탐색 → O(log N)

반면 unordered_map은:

• Key + Value 구조
• 내부적으로 해시 테이블(Hash Table) 사용
• 정렬되지 않음
• 삽입, 삭제, 탐색 → 평균 O(1)

 

 

 

2. unordered_map 기본 사용법

예:

unordered_map<int, string> idName;

• Key : int
• Value : string

데이터 입력:

idName[1] = "Rocoton";
idName[2] = "Kitty";
idName[3] = "Nabi";

출력하면:

1 Rocoton
3 Nabi
2 Kitty

처럼 출력 순서는 보장되지 않는다.

이유는 unordered_map이 해시 기반 구조이기 때문이다.

 

 

 

3. 중복 Key 처리

unordered_map은 map과 동일하게 Key 중복을 허용하지 않는다.

예:

idName.insert({1, "Bingo"});

기존에:

1 → Rocoton

이 존재한다면 새로운 값은 추가되지 않는다.

즉:

1 → Rocoton

상태가 유지된다.

 

 

 

4. operator[]를 이용한 값 변경

unordered_map에서도 대괄호 연산자를 사용할 수 있다.

예:

idName[1] = "Bingo";

결과:

1 → Bingo

기존 Value가 새로운 값으로 변경된다.

즉:

• insert() → 기존 Key가 있으면 추가하지 않음
• operator[] → 기존 Key가 있으면 Value를 변경

 

 

5. 존재하지 않는 Key 접근 주의

다음과 같은 코드:

cout << idName[6];

을 실행하면 문제가 발생할 수 있다.

Key 6이 존재하지 않아도 operator[]는 새로운 원소를 생성한다.

결과:

6 → 기본값("")

이 자동으로 추가된다.

따라서 단순 조회 목적이라면:

find()

를 사용하는 것이 안전하다.

 

 

 

6. 사용자 정의 Key 사용

unordered_map의 Key는 기본 타입뿐 아니라 사용자 정의 클래스도 사용할 수 있다.

하지만 unordered_set과 마찬가지로 다음 두 가지가 필요하다.

1) Hash 함수

어떤 버킷에 저장할지 결정한다.

2) Equality 비교 함수

같은 Key인지 판단한다.

예:

unordered_map<Cat, int, CatHash>

처럼 사용한다.

 

 

 

7. unordered_multimap

unordered_map은 Key 중복을 허용하지 않는다.

하지만 중복 Key를 저장하고 싶다면:

unordered_multimap

을 사용한다.

예:

unordered_multimap<int, string>

입력:

1 → Kitty
1 → Nabi

결과:

1 → Kitty
1 → Nabi

처럼 같은 Key를 가진 여러 데이터를 저장할 수 있다.

 

 

 

8. C++ 컨테이너 비교 정리

set / map

특징:

• 트리 구조
• 정렬 가능
• 비교 연산자 필요
• 삽입, 삭제, 탐색 → O(log N)

set

• Value 자체가 Key

map

• Key + Value 구조

 

 

 

unordered_set / unordered_map

특징:

• 해시 구조
• 정렬되지 않음
• Hash 함수 필요
• 평균 삽입, 삭제, 탐색 → O(1)

unordered_set

• Value 자체가 Key

unordered_map

• Key + Value 구조

 

 

 

9. 전체 핵심 정리

컨테이너	구조	정렬	중복 Key	시간 복잡도
set	Tree	O	X	O(log N)
multiset	Tree	O	O	O(log N)
map	Tree	O	X	O(log N)
multimap	Tree	O	O	O(log N)
unordered_set	Hash	X	X	평균 O(1)
unordered_multiset	Hash	X	O	평균 O(1)
unordered_map	Hash	X	X	평균 O(1)
unordered_multimap	Hash	X	O	평균 O(1)

 

기억해야 할 핵심 포인트

• 정렬이 필요하면 → set, map
• 빠른 탐색(O(1))이 중요하면 → unordered_set, unordered_map
• 중복을 허용하려면 → multi 접두사 사용
• set, map 계열은 비교 연산자 필요
• unordered_set, unordered_map 계열은 Hash 함수와 == 연산 필요
• 해시는 Key에 대해서만 적용된다.
• unordered_map은 실무와 알고리즘 인터뷰에서 매우 자주 사용되는 자료구조이다.