[자료구조] 6. STL Unordered_map

1. Unordered_map 간단 요약

  Hash Table을 기반으로 만들어진 많은 양의 자료를 검색하는 데 특화된 자료구조로, key와 value를 저장하는 점에서 Map과 비슷해 보이지만, key를 정해진 hash function을 통해 key 값을 특정 주소로 변환하여 value에 접근하므로 이론상 O(1)의 탐색 시간을 가지고, Map과 달리 데이터를 정렬하여 저장하지 않는다는 차이가 있다. 단점으로는 서로 다른 key에 대해 동일한 주소를 얻으면 충돌이 발생하여, 이를 방지하기 위한 안전장치가 필요하다.

 

2. Unordered_map 구조

- 해시 테이블(Hash Table)

- 반복자 사용이 가능하여 begin(), end() 등등의 STL 반복자 규칙을 공유한다.

- bucket의 다른 이름으로 slot이 있다.

 

* 해시 함수(Hash Function)

- 해시 함수 예시

1) Division Method : 단순히 key를 테이블의 크기(m)로 나눈 나머지를 주소로 정한다(h(k) = kmodm). 테이블 크기가 2의 제곱에서 먼 소수일 때 효율적이다.

2) Digit Folding : 각 key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 주소로 사용한다.

3) Multiplication Method : 숫자로 된 key값과 0과 1사이의 실수 A, 2의 제곱수인 m에 대해 h(k) = (kAmod1)*m을 주소로 한다.

4) Universal HAsing : 다수의 해시함수를 가지고 있고, 무작위로 해시함수를 선택해 해시값을 만드는 방법이다.

 

- 충돌에 대한 해결 방법

1) 분리 연결법(Separate Chaining)

- 동일한 주소를 가지는 데이터끼리 연결하여 저장한다. 테이블 외에 추가적인 메모리가 필요하다. 예를 들어 Linked List나 Red-Black Tree 등으로 데이터를 연결해놓는다. 이 경우 값의 탐색은 주소로 찾아간 뒤, 체인을 탐색하므로 시간복잡도가 O(1)보다 커지게 된다.

Separate Chaining

 

2) 개방 주소법(Open Addressing)

- 추가 메모리를 사용하는 분리 연결법과 달리, 테이블의 빈 공간을 활용하는 방법이다. 대표적인 방법은 아래와 같다.

1. Linear Probing : 현재 버킷의 주소로부터 고정폭만큼 이동하여 비어있는 버킷에 저장
2. Quadratic Probing : 해시의 저장 순서 폭을 제곱으로 늘려 저장
3. Double Hashing Probing : 해시된 값을 한번 더 해싱하여 해시의 규칙성을 제거, 추가 연산이 필요

3. Unordered_map 함수 정리

  1) 반복자(iterator) 관련

- begin() : 가장 먼저 추가한 key를 가리키는 iterator 반환

- end() : 가장 나중에 추가한 key의 다음 위치를 가리키는 iterator 반환(실제 값이 없음)

- cbegin() : begin()과 동일하나 수정이 불가능한(constant) iterator

- cend() : end()의 constant 버전

 

  2) 크기 관련

- empty() : Unordered_map이 비어있다면 true, 아니라면 false 반환

- size() : Unordered_map의 크기 반환

- max_size() : Unordered_map이 저장할 수 있는 데이터의 최대 개수

 

  3) 원소 관련

- at(n) : n을 key로 가지는 value 반환, 없는 경우 out_of_range 예외 호출

- Map[n] : n을 key로 가지는 value 반환, 없는 경우 n을 key로 가지는 새로운 value를 추가 후 레퍼런스 반환

 

  4) Map 수정 관련

- insert() : Unordered_map의 원소 추가

- erase() : Unordered_map의 원소 제거, erase(iter) : iter가 가리키는 노드 제거, erase(n) : n을 key로 하는 노드 제거, erase(iterFirst, iterEnd) : [iterFirst, iterEnd) 노드 제거

- swap(u_map) : 함수를 호출한 Unordered_map과 매개변수로 전달된 u_map의 원소 교환

- clear() : Unordered_map의 모든 원소 제거

- emplace() : insert와 비슷하나, 주어지는 매개변수로 make_pair()를 내부적으로 수행

- emplace_hint(iter, key, value) : Map과 마찬가지로 iter로 추가할 위치의 힌트를 주나, 성능을 보장하기 위해서 내부적으로 힌트를 사용할 수도 있고 아닐 수도 있음, iter를 기준으로 key에 해당하는 값이 있다면 해당 요소의 iterator 반환, 없다면 key와 value를 Unordered_map에 추가한 뒤 해당 위치의 iterator 반환

 

  4) 연산자

- find(n) : n을 key 값으로 갖는 iterator 반환, 없으면 end()를 반환

- count(n) : n을 key 값으로 갖는 원소의 개수를 반환, Unordered_map은 key가 유일하므로 원소가 존재하는 경우 1, 아니면 0을 반환

- equal_range(n) : pair(lower_bound(n), upper_bound(n))를 반환

 

  5) bucket 관련

- bucket_count() : 현재 Hash Table의 bucket 수 반환

- max_bucket_count() : Hash Table의 최대 bucket 수 반환

- bucket_size(n) : 주소 n의 bucket의 크기 반환, 이 때 크기는 동일한 주소를 가지는 value를 연결한 Linked List(또는 다른 컨테이너)의 크기

- bucket(n) : n을 key로 가지는 bucket의 주소(인덱스) 반환

 

  6) Hash policy 관련

- load_factor() : 원소의 수/bucket의 수 반환

- max_load_factor() : 두 가지 함수로 오버로딩 되어있음

> max_load_factor() : 현재 load factor의 최대값(기본값 1) 반환

> max_load_factor(float z) : load factor의 최대값을 z로 지정

- rehash(n) : Hash Table을 재조정, 이 때 원래 bucket의 수보다 n이 작으면 수행하지 않고, n이 더 크면 n과 같거나 큰 bucket의 수를 가지도록 됨, rehash 사용 시 Hash Table이 재배치되기 때문에 기존의 iterator가 가리키는 대상이 바뀔 수 있음

- reserve(n) : bucket의 수를 n으로 예약하여 미리 공간을 확보, bucket_count() 시 n이 반환됨

 

* load factor, max load factor

- Unordered_map의 원소의 수가 늘어나면 load factor가 max load factor를 넘어서고, 이를 기준으로 bucket의 수를 늘려 Hash Table을 조절한다.

 

  7) Getter 함수

- hash_function() : 해시 함수 반환

- key_eq() : key의 동일성을 판단하는 key_equal 반환

- get_allocator() : 할당자 반환

 

* hash_function(), key_eq() 예시

#include <iostream>
#include <unordered_map>

using namespace std;

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

	// Hash Function
	unordered_map<string, string>::hasher hashFunc = myMap.hash_function();

	cout << "h(key) : " << hashFunc("key") << endl;
	cout << "h(value) : " << hashFunc("value") << endl;

	// Key equal
	unordered_map<string, string>::key_equal keyEq = myMap.key_eq();

	cout << "key_eq(a, a) : " << (keyEq("a", "a") ? "true" : "false") << endl; // true
	cout << "key_eq(a, b) : " << (keyEq("a", "b") ? "true" : "false") << endl; // false
	cout << "key_eq(test, TEST) : " << (keyEq("test", "TEST") ? "true" : "false") << endl; // false, 대소문자 구분

	return 0;
}

 

h(key) : 1746258028
h(value) : 1113510858
key_eq(a, a) : true
key_eq(a, b) : false
key_eq(test, TEST) : false