std::unordered_map

std::unordered_map은 C++ 표준 라이브러리에서 제공하는 연관 컨테이너(associative container)의 한 종류다. 키(Key)와 값(Value)을 쌍으로 저장하며, 키를 기반으로 값에 매우 빠르게 접근할 수 있는 기능을 제공한다.

std::map과 가장 큰 차이점은 내부적으로 균형 잡힌 이진 검색 트리(Balanced Binary Search Tree)가 아닌 해시 테이블(Hash Table)을 사용하여 데이터를 관리한다는 점이다. 이로 인해 데이터가 정렬된 상태로 유지되지 않지만, 평균적으로 O(1)의 시간 복잡도로 삽입, 삭제, 검색이 가능하다.

1. 내부 구조 및 구현 방식 (Internal Structure and Implementation)

std::unordered_map의 핵심은 해시 테이블이다. 

• 해시 테이블 (Hash Table):
  내부적으로 '버킷(Bucket)'이라는 슬롯의 배열로 구성된다. 각 키는 해시 함수를 통해 특정 버킷의 인덱스로 매핑된다.
• 버킷 (Buckets):
  버킷은 해시 테이블의 각 슬롯을 의미한다.
  std::unordered_map은 해시 충돌(Hash Collision)을 해결하기 위해 각 버킷에 하나 이상의 키-값 쌍을 저장할 수 있는 구조를 가진다.
  표준에서는 버킷이 어떻게 구현되어야 하는지 명시하지 않지만, 대부분의 표준 라이브러리 구현체(GCC, Clang, MSVC)는 각 버킷을 연결 리스트(Linked List)로 구현합니다(Separate Chaining 방식).
  • [Bucket 0] -> Node(K1, V1) -> Node(K5, V5) -> nullptr
  • [Bucket 1] -> nullptr
  • [Bucket 2] -> Node(K2, V2) -> nullptr
  • ...
  • [Bucket N-1] -> Node(K_i, V_i) -> nullptr
• 해시 함수 (Hash Function):
  사용자가 제공한 키를 size_t 타입의 해시 값으로 변환하는 함수다. 이 해시 값은 이후 버킷 배열의 크기(bucket count)로 나머지 연산(modulo operation)을 거쳐 키가 저장될 버킷의 인덱스를 결정하는 데 사용된다.
  index = hash_function(key) % bucket_count
  C++ 표준 라이브러리는 std::hash<Key> 템플릿을 통해 int, double, std::string 등 기본 타입에 대한 해시 함수를 기본적으로 제공한다. 사용자 정의 타입을 키로 사용하려면, 해당 타입에 대한 해시 함수를 직접 정의하고 std::hash를 특수화해야 한다.
• 키 동등성 비교 (Key Equality Predicate):
  해시 충돌이 발생하여 하나의 버킷에 여러 노드가 연결 리스트 형태로 저장된 경우, 원하는 키를 찾기 위해 리스트를 순회하며 각 노드의 키와 찾고자 하는 키를 비교해야 한다. 이때 사용되는 것이 키 동등성 비교 함수(Key-Equal Predicate)이며, 기본적으로 std::equal_to<Key>가 사용된다. 이는 내부적으로 operator==를 호출한다.
• 해시 충돌 및 해결 (Hash Collision and Resolution):
  서로 다른 두 개 이상의 키가 해시 함수를 통해 동일한 버킷 인덱스로 매핑되는 현상을 '해시 충돌'이라고 한다. std::unordered_map은 주로 분리 연결법(Separate Chaining)을 사용하여 이 문제를 해결한다. 즉, 동일한 인덱스로 해싱된 모든 키-값 쌍을 해당 버킷의 연결 리스트에 추가하는 방식이다.
  충돌이 많아질수록 특정 버킷의 연결 리스트가 길어지고, 해당 버킷에 대한 검색 시간은 리스트의 길이에 비례하여 O(k)가 된다 (k는 리스트의 노드 수). 최악의 경우 모든 키가 동일한 버킷으로 해싱되면, 시간 복잡도는 O(N)까지 저하될 수 있다.
• 부하율과 재해싱 (Load Factor and Rehashing):
  • 부하율(Load Factor): 해시 테이블이 얼마나 차 있는지를 나타내는 척도. (저장된 요소의 수) / (버킷의 수)로 계산.
  • 최대 부하율(Max Load Factor): std::unordered_map이 재해싱을 트리거하는 부하율의 임계값. 기본값은 보통 1.0. 사용자가 max_load_factor() 멤버 함수를 통해 이 값을 조절할 수 있다.
  • 재해싱(Rehashing): 요소의 수가 늘어나 부하율이 최대 부하율을 초과하면, 해시 테이블은 성능 저하를 막기 위해 스스로를 확장한다. 이 과정을 재해싱이라고 한다.
    재해싱은 보통 더 많은 버킷(일반적으로 기존의 2배)을 가진 새로운 해시 테이블을 생성하고, 기존의 모든 요소를 새로운 해시 함수(새로운 버킷 수에 맞게 조정된)를 사용해 새로운 테이블에 다시 삽입하는 과정이다. 재해싱은 비용이 큰 작업(O(N))이므로, 요소의 개수를 미리 알 수 있다면 reserve() 멤버 함수를 호출하여 초기에 충분한 수의 버킷을 할당함으로써 불필요한 재해싱을 피할 수 있다.

2. std::unordered_map vs std::map

특징	std::unordered_map	std::map
내부 자료구조	해시 테이블 (Hash Table)	레드-블랙 트리 (Red-Black Tree)
데이터 정렬	정렬되지 않음 (Unordered)	키를 기준으로 자동 정렬 (Sorted)
시간 복잡도
- 삽입/삭제/검색	평균: O(1), 최악: O(N)	O(log N)
메모리 사용량	일반적으로 더 많음 (포인터, 버킷 배열)	일반적으로 더 적음
키의 요구사항	std::hash와 std::equal_to (또는 사용자 정의)	std::less (또는 사용자 정의 비교 함수, operator<)
반복자 무효화	재해싱 발생 시 모든 반복자, 포인터, 참조가 무효화됨	삽입/삭제 시 해당 요소를 가리키는 반복자만 무효화됨

언제 무엇을 사용해야 하는가?

• std::unordered_map을 사용해야 할 때:
  • 데이터를 정렬할 필요가 없을 때.
  • 최대한 빠른 평균 검색, 삽입, 삭제 성능이 필요할 때 (예: 실시간 조회, 캐싱 시스템).
  • 최악의 경우(O(N))의 성능 저하를 감수할 수 있거나, 좋은 해시 함수를 통해 이를 회피할 수 있을 때.
  • 게임 개발에서 ID나 이름으로 게임 오브젝트, 리소스, 플레이어 데이터 등을 관리할 때 매우 유용.
• std::map을 사용해야 할 때:
  • 키를 기준으로 정렬된 데이터가 필요할 때 (예: 순서대로 출력, 범위 기반 검색).
  • 안정적이고 예측 가능한 성능이 중요할 때 (O(log N)의 상한 보장).
  • 해시 함수를 만들기 어려운 복잡한 키를 사용할 때.
  • 데이터의 순서가 중요한 리더보드, 정렬된 이벤트 큐 등을 구현할 때 적합.

3. 계층 구조 (Layered Architecture)

std::unordered_map이 동작하는 과정을 계층별로 나누어 보면 다음과 같다.

1. 사용자 애플리케이션 계층 (User Application Layer):
   • 개발자는 std::unordered_map<Key, T> myMap;과 같이 객체를 선언.
   • myMap["player1"] = 100; (삽입), myMap.find("player1"); (검색)과 같은 멤버 함수를 호출하여 컨테이너와 상호작용.
2. C++ 표준 라이브러리 계층 (C++ Standard Library Layer):
   • unordered_map의 구현 코드가 이 계층에 속함.
   • 사용자의 함수 호출을 받아 내부 로직을 수행.
   • find 호출 시:
     1. std::hash<Key>를 호출하여 키의 해시 값을 계산.
     2. hash % bucket_count 연산으로 버킷 인덱스를 결정.
     3. 해당 버킷의 연결 리스트를 순회하며 std::equal_to<Key>를 사용해 키를 비교.
     4. 일치하는 키를 찾으면 해당 노드의 반복자를 반환, 찾지 못하면 end() 반복자를 반환.
   • insert 호출 시:
     1. 부하율을 검사, 필요 시 재해싱을 수행. 재해싱은 아래 메모리 관리 계층에 메모리 재할당 요청.
     2. find와 유사한 과정으로 키가 들어갈 위치를 찾음.
     3. 새로운 노드를 생성하고(메모리 할당 요청) 버킷의 연결 리스트에 추가.
3. 메모리 관리 계층 (Memory Management Layer):
   • 표준 라이브러리는 std::allocator<Node> (기본 할당자)를 통해 메모리를 관리.
   • unordered_map이 버킷 배열(해시 테이블)이나 노드(키-값 쌍)를 위한 메모리가 필요할 때, 할당자는 C++ 런타임 시스템에 메모리를 요청.
   • 예를 들어, new Node(...)는 내부적으로 std::allocator의 allocate 함수를 호출, 이는 다시 C++ 런타임의 ::operator new를 호출할 수 있음.
4. C++ 런타임 / 운영체제 계층 (C++ Runtime / OS Layer):
   • C++ 런타임은 힙(Heap) 메모리 영역을 관리.
   • 애플리케이션의 메모리 요청(e.g., ::operator new)이 들어오면, 런타임은 미리 할당해 둔 힙 영역에서 메모리를 제공.
   • 만약 힙에 가용 메모리가 부족하면, 런타임은 운영체제(OS)에 시스템 콜(System Call, 예: brk, mmap)을 통해 추가적인 메모리 페이지를 요청.
5. 커널 계층 (Kernel Layer):
   • 운영체제 커널은 시스템 콜을 받아 프로세스의 가상 주소 공간에 새로운 메모리 페이지를 매핑.
   • 커널은 가상 메모리 시스템을 관리, 이 가상 주소가 실제 물리 메모리(RAM)의 어느 위치에 매핑되는지를 페이지 테이블을 통해 관리.
6. 하드웨어 계층 (Hardware Layer):
   • CPU는 코드를 실행. 메모리 주소에 접근하는 명령이 실행, CPU 내의 MMU(Memory Management Unit)가 가상 주소를 물리 주소로 변환.
   • 해시 테이블의 버킷 배열이나 연결 리스트의 노드들이 메모리상에 흩어져 있을 경우, CPU 캐시의 지역성(locality)이 저하되어 캐시 미스(Cache Miss)가 자주 발생할 수 있음. 이는 unordered_map의 실질적인 성능에 영향을 미치는 중요한 요소. 연결 리스트를 따라가는 것은 포인터를 역참조하는 과정이며, 이는 캐시 효율성 측면에서 배열 순회보다 불리함.

5. 요약

std::unordered_map은 키와 값 쌍을 저장하는 C++의 자료구조로, 내부적으로 해시 테이블을 사용합니다. 키를 해시 함수에 넣어 나온 값으로 데이터가 저장될 위치를 바로 계산하기 때문에, 평균적으로 한 번의 연산, 즉 O(1)의 매우 빠른 속도로 데이터를 찾거나 추가하고 삭제할 수 있습니다.

하지만 std::map처럼 키를 기준으로 데이터가 정렬되지는 않습니다. 또한, 아주 드물게 여러 다른 키들이 같은 저장 위치를 할당받는 '해시 충돌'이 많이 발생하면 성능이 O(N)까지 느려질 수 있습니다. 이런 성능 저하를 막기 위해 데이터가 일정 수준 이상으로 차면, '재해싱'이라는 과정을 통해 더 큰 저장 공간을 확보하고 데이터를 재배치하여 빠른 속도를 유지하려고 합니다.

따라서, 데이터의 순서가 중요하지 않고 최대한 빠른 검색 속도가 필요할 때, 예를 들어 게임에서 캐릭터 ID로 데이터를 즉시 찾아야 하는 경우에 std::unordered_map을 사용하는 것이 가장 효과적입니다. 반면, 데이터의 정렬이 필요하거나 항상 일정한 성능(O(log N))을 보장받고 싶을 때는 std::map이 더 나은 선택입니다.