C++에서 HashMap 사용

1. C++에서 std::map과 함께 HashMap 사용
2. C++에서 std::unordered_map과 함께 HashMap 사용
3. C++에서 각 맵을 사용하는 경우와 주요 차이점

HashMap은 관련 키를 사용하여 값을 검색할 수 있는 키-값 쌍을 포함하는 중요한 데이터 구조입니다. 모든 키는 HashMap의 특정 값 하나에 매핑됩니다.

반복 중에 키를 사용하면 해당 값에 훨씬 빠르게 액세스할 수 있습니다. 따라서 HashMap은 모든 유형의 키와 값을 사용하여 값을 검색할 때 효율적이고 필수적인 데이터 구조로 간주됩니다.

C++ 11 이전에는 표준 정의 해시 테이블이 C++의 표준 라이브러리에 없었지만 약간 다른 구현자들은 종종 HashMap이라고 하는 해시 테이블의 비표준 변형을 가지고 있었습니다. C++ 11과 함께 해시 테이블의 표준 구현이 표준 라이브러리에 추가되었습니다.

그래도 다른 라이브러리의 HashMap으로 해시 테이블의 다양한 변형이 있기 때문에 혼동을 피하기 위해 새 구현을 호출하는 별도의 이름을 사용하기로 결정했습니다.

따라서 C++에서 std::unordered_map은 HashMap의 대체 이름이지만 다른 맵은 키-값 쌍 개념인 std::map을 사용합니다.

std::unordered_map과 std::map 사이에는 주요 차이점이 있습니다. 이름에서 알 수 있듯이 std::unordered_map 안의 요소는 순서가 지정되지 않은 반면 std::map의 요소는 순서가 지정됩니다.

C++에서 std::map과 함께 HashMap 사용

std::map은 요소가 매핑된 키-값 쌍에 저장되는 연관 컨테이너 범주에 속합니다. std::map 및 std::unordered_map에서 키는 항상 고유해야 하지만 매핑된 값이 유사한 고유 키가 여러 개 있을 수 있습니다.

std::map은 [Self-Balancing Binary Search Tree](AVL 트리/레드-블랙 트리)를 사용하여 구현됩니다. BST(Self-Balancing Binary Search Tree)의 주요 기능은 요소의 삽입 및 삭제가 발생할 때 높이가 항상 자동으로 최소로 유지된다는 것입니다.

std::map에서 평균 시간 복잡도는 저장되는 요소의 수에 대수적으로 의존합니다. 따라서 작업이 발생하는 데 평균 O(log n) 시간이 걸립니다. O(log n)에서 O는 Big O 표기법을 나타내고 n은 저장된 요소의 수를 나타냅니다.

따라서 BST는 정렬된 목록을 만들고 유지 관리할 때 유용합니다.

예시:

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() {
  map<int, string> Players;

  Players.insert(std::pair<int, string>(2, "Lin Dan"));
  Players.insert(std::pair<int, string>(1, "Chen Long"));

  cout << "Number of Players " << Players.size() << endl;
  for (map<int, string>::iterator it = Players.begin(); it != Players.end();
       ++it) {
    cout << (*it).first << ": " << (*it).second << endl;
  }
}

출력:

Number of Players 2
1: Chen Long
2: Lin Dan

C++에서 std::unordered_map과 함께 HashMap 사용

std::unordered_map은 C++의 해시 테이블을 사용하여 구현됩니다. 해시 테이블도 연관 컨테이너에 속합니다. 매핑된 값은 필요한 값을 검색할 수 있는 버킷 또는 슬롯 배열의 해시 테이블에 저장됩니다.

이 인덱싱은 해시 코드인 해시 함수를 사용하여 수행됩니다. std::unordered_map의 검색, 삽입 및 삭제를 위한 평균 시간 복잡도는 O(1)입니다. 여기서 O는 Big O 표기법입니다. 이것이 std::unordered_map은 매우 효율적입니다.

예시:

#include <iostream>
#include <unordered_map>

using namespace std;

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

  info["Age"] = 18;
  info["Year"] = 2022;
  info["Number of Players"] = 15;

  for (auto x : info) cout << x.first << " " << x.second << endl;
}

출력:

Number of Players 15
Year 2022
Age 18

C++에서 각 맵을 사용하는 경우와 주요 차이점

std::unordered_map과 std::map을 비교할 때 둘 사이의 효율성 차이는 엄청납니다.

std::unordered_map은 분명히 std::map에 비해 상당한 성능 우위를 가지고 있습니다. 이는 주로 std::unordered_map이 슬롯에 배치될 때 값을 직접 지정할 수 있으므로 보존해야 할 순서가 없기 때문입니다.

반면에 std::map에는 보존해야 하는 순서가 있습니다. 따라서 더 많은 시간을 소비합니다. 이 효율성은 작은 데이터 세트에서는 보이지 않을 수 있지만 이 차이는 큰 데이터 세트에서는 큽니다.

std::unordered_map은 데이터 세트에서 단일 요소에 액세스하거나 순서가 필요하지 않은 경우 요소 수를 유지할 때 사용할 수 있습니다.

std::map은 std::unordered_map보다 몇 가지 장점이 있습니다. 일반적으로 BST는 해시 테이블보다 더 빠르게 구현할 수 있으며 우리가 선호하는 방식으로 구현할 수 있지만 해싱을 위해서는 라이브러리에 크게 의존해야 합니다.

따라서 std::map은 std::unordered_map에 비해 쉽게 구현할 수 있습니다. 또한 정렬과 관련하여 std::unordered_map보다 std::map에서 키를 정렬하는 것이 훨씬 쉽습니다. inorder traversing이 해시 테이블에 대한 자연스러운 작업이 아니라 BST에 대한 것이기 때문입니다.

std::map은 데이터를 정렬된 순서로 인쇄하는 것과 같은 상황에서 사용할 수 있습니다. 검색 쿼리, 주문 통계 등을 위해 데이터를 정렬해야 하는 경우입니다.

std::map과 std::unordered_map은 그 순간의 필요에 따라 조작할 수 있는 특정 유사점과 차이점이 있습니다.