C++ STL unordered associative container(unordered map)
intro
정렬 기준이 없는 자료를 빠른 시간 내에 검색하려면 어떻게 해야 할까?hash 자료구조를 사용하면 된다.
hash
여러 개의 string을 삽입, 삭제, 검색하는 상황을 가정해보자.
sequence container로 string을 관리하면, 검색할 때마다 모든 string을 탐색해야 하므로 O(N)이 소요된다. 그리고 string에 정렬기준이 없는 상황에서 ordered associative container로 관리할 수도 없다.
string을 어떤 특정 int값으로 변환할 수는 없을까? 이것이 hash의 출발이다. hash라는 것이, 임의의 길이의 data를 고정된 길이의 data로 mapping 하는 것을 뜻한다. (위의 그림에서 hash function에 해당한다.)
이번 posting에서 다루고자 하는 unordered map 또한 hash구조이다.
unordered map
unordered_map은 우리가 일반적으로 알고 있는 hash를 생각하면 된다. 그림으로 자세히 이해해 보자.
- hash function으로 hash값이 return 되고, 이를 bucket의 count로 나눈 나머지 값으로 hash table의 index를 정한다.
- hash 충돌이 발생하는 경우, bucket의 list에 추가해서 연결하는 방식이다. (chaining)
// CLASS TEMPLATE unordered_map
template <class _Kty, class _Ty, class _Hasher = hash<_Kty>, class _Keyeq = equal_to<_Kty>,class _Alloc = allocator<pair<const _Kty, _Ty>>>
class unordered_map : public _Hash<_Umap_traits<_Kty, _Ty, _Uhash_compare<_Kty, _Hasher, _Keyeq>, _Alloc, false>> {
// hash table of {key, mapped} values, unique keys
...
}- template의 파라미터는 key, value, hash function, key equal function이다.
- key를 struct로 할 경우, 이를 파라미터로 갖고 있는 hash function, key equal function은 재정의가 필요하다.
삽입, 삭제, 검색의 시간복잡도는 다음과 같다.
주의할 것은, key에 따라 bucket에 잘 분배되도록 hash function을 만들어야 한다. 그렇지 못할 경우, worst 시간복잡도 O(n)이 걸린다. (n은 container의 객체 수)
| average 시간복잡도 | worst 시간복잡도 | |
| insert | O (1) | O(n) |
| erase | O (1) | O(n) |
| find | O (1) | O(n) |
예제 코드는 다음과 같다.
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main()
{
unordered_map<string, int> hashMap;
hashMap.insert({ "smith", 32 });
hashMap.insert({ "john", 15 });
hashMap.insert({ "mikasa", 21 });
hashMap.insert({ "monika", 42 });
cout << hashMap.bucket("mikasa") << endl; // bucket index
cout << hashMap.count("john") << endl; // 1
cout << hashMap.erase("john") << endl; // 1
cout << hashMap.erase("asdfjka") << endl; // 0
cout << hashMap.count("john") << endl; // 0
auto it = hashMap.find("mikasa");
cout << it->first << endl; // mikasa
cout << it->second << endl; // 21
return 0;
}