std::unordered_map

std::unordered_map은 해시 테이블 기반의 연관 컨테이너로, key–value 쌍을 저장하되 정렬은 하지 않고 빠른 평균 시간 검색을 제공하는 컨테이너이다.

개념 & 기본 구조

• 정의

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;

• Key: 키 타입
• T: 값(매핑되는 값) 타입
• Hash: 해시 값을 계산하는 함수 객체
• KeyEqual: 두 키가 같은지 비교하는 함수 객체
• 특징
  • 키는 유일하고, 같은 키로 insert를 하면 두 번째는 무시함.
  • 요소들은 어떤 순서로도 정렬되지 않음.

시간 복잡도

검색, 삽입, 삭제는 평균 O(1), 최악 O(N) (해시 충돌이 심한 경우)

장점 / 단점

장점

1. 빠른 평균 접근 속도
   키 기반 검색/삽입/삭제가 평균적으로 O(1)이라 많은 경우에 std::map보다 빠름
   
2. 정렬이 불필요한 경우 효율적
   순서가 전혀 중요하지 않고, 키 -> 값 빠르게 찾기가 목적일 경우 매우 적합
   
3. Key 타입에 따라 해시 함수 정의 가능
   사용자 정의 타입에 대해 해시 함수를 정의해서 사용할 수 있음
   

단점

1. 순서가 없음
   요소 순회 시 삽입 순서 보장 X, 키 정렬 X

2. 최악 시간 복잡도 O(N)
   해시 충돌이 심하면 특정 버킷에 원소가 몰려 성능이 급격히 저하될 수 있음

3. 해시/버킷 조정 비용
   원소가 늘어나면서 load_factor가 max_load_factor를 넘으면 자동 rehash가 발생하고, 모슨 원소를 재배치하는 비용이 발생

해시 충돌 시 해결 방법

Chaining

해시 테이블의 각 버킷이 리스트 하나를 들고 있는 방식이다.

어떤 키의 해시 값을 계산해서 버킷 인덱스를 구한 뒤, 해당 버킷 안에 있는 연결 리스트에 노드로 추가한다.

즉, 원소의 해시 값이 같을 경우 같은 버킷에 여러 원소가 연결되어 있다.

Open Addressing

모든 원소를 하나의 배열 안에만 저장하는 방식이며, 충돌이 발생하면 다른 빈 슬롯을 찾아가면서 저장한다.

대표적으로 선형 탐사, 이차 탐사, 이중 해싱 등이 존재한다.