[STL] HashMap
•
해시맵은 관련 키를 사용하여 값을 검색할 수 있는 키-값 쌍을 포함하는 중요한 데이터 구조이다
•
모든 키는 해시맵의 특정 값 하나에 매핑된다
•
반복 중에 키를 사용하면 해당 값에 훨씬 빠르게 액세스 할 수 있다
•
따라서 해시맵은 모든 유형의 키와 값을 사용하여 값을 검색할 때 효율적이고 필수적인 데이터 구조로 간주된다
unordered_map : 해시맵의 대체 이름
unordered_map과 map의 차이점
•
unordered_map 안의 요소는 순서가 지정되지 않고, map의 요소는 순서가 지정된다
c++에서 std::unordered_map과 HashMap 사용
•
std::unordered_map은 c++의 해시테이블을 사용하여 구현된다. 해시 테이블도 연관 컨테이너에 속한다.
•
매핑된 값은 필요한 값을 검색할 수 있는 버킷 또는 슬롯 배열의 해시테이블에 저장된다
•
이 인덱싱은 해시 코드인 해시 함수를 사용하여 수행된다
•
std::unordered_map의 검색, 삽입 및 삭제를 위한 평균 시간복잡도는 O(1)이다
◦
효율적
#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;
}
}
// output //
// Number of Players 15
// Year 2022
// Age 18
C++
복사
C++에서 각 맵을 사용하는 경우와 주요 차이점
•
std::unordered_map은 분명히 std::map에 비해 상당한 성능 우위를 가지고 있다.
•
이는 주로 std::unordered_map이 슬롯에 배치될 때, 값을 직접 지정할 수 있으므로 보존해야 할 순서가 없기 때문이다
•
반면에 std::map에는 보존해야 하는 순서가 있다. 따라서 더 많은 시간을 소비한다. 이 효율성은 작은 데이터 세트에서는 보이지 않을 수 있지만, 이 차이는 큰 데이터 세트에서는 크다
•
std::unordered_map은 데이터 세트에서 단일 요소에 액세스하거나 순서가 필요하지 않은 경우 요소 수를 유지할 때 사용할 수 있다
•
std::map은 std::unordered_map보다 몇가지 장점이 있다. 일반적으로 BST는 해시테이블보다 더 빠르게 구현할 수 있으며, 우리가 선호하는 방식으로 구현할 수 있지만, 해싱을 위해서는 라이브러리에 크게 의존해야한다
•
따라서 std::map은 쉽게 구현할 수 있다. 또한 정렬과 관련해서도 std::map에서 키를 정렬하는 것이 훨씬 쉽다. inorder traversing이 해시 테이블에 대한 자연스러운 작업이 아니라 BST에 대한 것이기 떄문이다