unordered_associative container 학습

[[[종류]]] 

unordered_map, unordered_set, unordered_multimap, unordered_multiset

 

[[[설명]]] 

예전에는 hash라고 불렀던 컨테이너들인데 unordered 연관 컨테이너로 이름이 바뀌었다.

1. associative container이기 때문에 key값과 value를 갖는다.

find가 O(1)인 컨테이너들이다. hash를 이용해서 찾기 때문이다.

빠른 속도를 얻은 대신 메모리 공간을 많이 차지한다.

 

2. 표를 이용한다(bucket)

bucket에는 방 번호가 부여되어 있다.

 

3. key값이 있다면 알고리즘이 key값을 잘게 잘라서 유일한 정수를 준다(hasher)

hasher를 통해 hash값이 나오는데 인덱스로 하여 지정받은 bucket공간에 접근할 수 있다.

즉 key는 유일한 hash(방번호)를 얻게 되고 자신만의 bucket 공간에 접근 가능하다.

key를 통해 value 에 find하는데 O(1) 상수시간이다.

key - hahser: 해당 key에 해당하는 유일한 hash값 생성 - hash값을 index로 사용 - index로 메모리 공간에 접근

 

4. 알고리즘은 수학자들이 만든다. 일반인이 만들기엔 너무 어려운 공식이다.

 

5. 내가 사용자 지정 클래스를 만들었다면 이 객체를 hash 값으로 변환 시키기 위한 hasher 알고리즘을 작성해야 할 것이다. 하지만 이는 무척 어렴고, 클래스 안에 ID같은 것을 정수형으로 만들었다면 이것을 기존에 만들어진 hasher 알고리즘에 대입하여 사용할 수 있다.

 

6. string같은 stl은 이미 잘 만들어진 hasher를 가지고 있다. 

 

unordered_set

일반 set의 찾기 실력이 O(logN)인데 2진트리로 만들었기 때문이다.

2진트리 구조를 지키기 위해 key가 순서있게 저장된다.

하지만 unordered_set은 해쉬를 이용하기  때문에 순서있게 필요도 없고 그렇게 저장되지 않는다.

 

1. unordered_set에 키값을 저장하고 싶다면 default로 key값에 대한 hash 있어야 bucket이 지정이 된다.

즉 hasher 알고리즘을 통해 hash값을 얻어내야 hash값에 해당하는 bucket을 지정할 수 있다.

 

2. value값은 bucket에 저장되는데 저장될 위치가 hash에 따라 결정된다.

 

3. 한번 해쉬값이 결정되면 언제 물어봐도 똑같은 값이 나온다.

 

==헤더 파일==

#include <iostream>

#include <unordered_set>

 

==소스 코드==

저장되는 순서가 없다고 했으면서 출력하니 1 2 4 3 5 저장한 순서대로 나오지 않냐! 라고 생각할 수 있다.

단지 현재 해시 테이블에 상태에 결정된 순서일 뿐 요소를 삽입할 때 마다 순서가 달라질 수 있다.unordered_set은 순서에 의존하지 말아야 하며 다른 컴파일러나 환경에서는 얼마든지 달라질 수 있다.요소의 순서가 중요하다면 std::set을 이용하자

5를 insert 해보자. 값을 넣을 때 insert를 사용한다.

9를 insert해보자. 

알수있는 사실: 요소의 순서는 내부의 해시테이블에 의해서 결정된다.

메모리 관점에서 보자

set은 key == value이다.

왼쪽은 bucket이고 vector로 만들어 진다.

오른쪽은 bucket에 들어있는 value이고 list로 만들어 진다.

메모리 공간을 많이 차지한다.

현재 bucket은 0 ~ 7까지 만들어져 있고 가변사이즈다.

벡터 안에 리스트가 들어가 있는 형태다.

4가 어딨어? 라고 물어보면 4의 hash값을 찾아서(해시값 1이 나옴) bucket[1]에 바로 접근하여 list를 뒤져서 4가 있는지를 찾는다.

list안에 요소가 여러개 있으면 찾는데 선형시간이 더 걸릴 것이고 아래에서 설명한다.

 

문제 발생!!! 왜 하나의 버켓에 여러개의 값들이 들어가있지?

1. 이것을 해시 충돌이라고 한다. set에서는 해시 충돌이 문제되지 않는다.

 

2. 이 해시 충돌을 해결하는 방법을 해시 체이닝 이라고 한다. 연결 리스트를 사용하는 방법이다.

해시 테이블의 성능을 저하시킨다. 연결리스트에서 값을 찾으려면 O(N)만큼의 시간이 걸리기 때문이다.

예를들어 위에 그림에서 12라는 값이 있나를 찾고싶다면 hash값이 1이라서 bucket[1]에 찾아갔더니

연결리스트에 값이 여러개가 있고, 그 연결리스트를 선회하며 다 찾아봐야 12라는 값이 있는지 없는지를 알 수 있기 때문이다.

 

3. forward list를 사용해도 충분하지만 visual 스튜디오는 양방향으로 만들어 놓았다. 

반복자 종류는 bidirectiory iterator이다.

 

4. 요소의 총 개수 > bucket의 개수가 되면 bucket의 개수를 늘리고 요소를 재 배치 시킨다.

 

5. 정리: unordered_set에서 여러 요소가 동일한 hash값을 갖고 있을 수 있고 해시 충돌이라고 한다.

해시 체이닝 기법을 사용하여 충돌을 해결할 수 있지만 성능저하가 생긴다.

8의 배수로 늘어난다.

 

unordered_multiset

unordered_set은 hash 충돌이 일어나도 key값은 전부 달랐고, 버킷을 늘렸을 때 다른 방으로 잘 이주하였는데

unordered_multiset같은 경우는 중복된 key값을 넣을 수 있기 때문에 hash충돌 + 다른방 이주해도 뭉쳐있음

 

==헤더 파일==

#include <iostream>

#include <unordered_set>

 

==소스 코드==

unordered_set -> unordered_multiset으로 변경

만약 여러 캐릭터를 저장했는데 hash가 충돌한다면

operator == 을 이용하여 ID로 찾아주어야 한다.

해시테이블을 자료구조로 사용하는 곳은 컴파일러가 파싱할 때 사용한다.

 

==생각==

졸작하면서 unordered_set, unordered_map을 사용하는 팀을 본적이 없다고 한다.

나는 서버에서 unordered_map을 사용중이다.

sector를 unordered_map으로 만들어서 관리중인데 오히려 일반 map이 더 빠르려나?

그럴일은 없을 것이다.

몬스터 20만마리를 100개의 sector에 나눠서 관리하고 있다. 

처음부터 bucket을 reserve해서 크기를 매우 키워 놓으면 hash충돌도 적을 것이다.

그런데 이렇게 하면 램이 버틸 수 없을정도로 늘어난다.

hash 충돌이 10개의 요소정도밖에 안된다면 사실 상수로 봐도 무관하긴 하다.

이전에 reserve를 10000으로 했더니 6기가 사용되던 램이 11.1기가까지 올라갔다.

 

해셔를 직접 만들어보자. hasher공식을 만들수는 없으니 3번방에만 배치되도록 한다.

 

내가 만든 String에 표준 해쉬를 사용하기

template<>는 템플릿 특수화(template specialization)를 선언할 때 사용한다.

템플릿 특수화는 일반적인 템플릿이 특정 타입이나 조건에 대해서는 다르게 동작하도록 하는 기능이다.

기본 템플릿과 다른 동작을 하도록 구현할 수 있다.

 

(예시)

[[일반 템플릿]]

template<typename T>

class Temp{

    public:

    T value;

}

 

[[템플릿 특수화]]

template<>

class Temp<int>{

    public:

    int value:

}

1. Temp<double> temp

2. Temp<int> temp

1번은 class Temp가 실행되고 2번은 class Temp<int>가 실행된다.

 

[[이와 같은 경우 템플릿 특수화이며 hash<String>객체를 만들 때만 실행된다.]]

template<>

class hash<String>

 

즉, unordered_multiset<String, hash<String>> unm 이런식으로 String객체를 만들고 나면

template<> class hash<String> 여기서 정의한 공식대로 hash가 만들어진다.

(일반적으로 String, hash<String>에서 hash<String>는 생략된다. default로 들어간다.)

 

정의를 분석해보자.

1. unordered_multiset<String, hash<String>> String class와 hash클래스를 받는다.

 

2. hash class를 받고나면  multiset 내부 동작으로는 hash class 안에 operator () 함수 호출 연산자를 실행시킬 것이다.

operator()안에 해쉬를 만들어주는 코드가 있을 것이다.

클래스를 함수처럼 사용할거고 템플릿 특수화를 사용하여 다양한 TYPE에 따라서 다르게 실행되도록 할 수 있다.

 

3. return hash<string>()(string{s.begin(), s.end()});를 분석해보면

hash<string>은 string 타입에 대해 해시 값을 생성하는 클래스이다.

hash<string>()은 임시 객체를 생성한다. 기본 생성자를 호출하여 객체를 생성하는 것이다.

 

4.hash<string>()()은 임시객체를 만들고 함수호출 연산자롤 호출하는 것이다.

 

5. string{s.begin(), s.end()}를 분석해보면 string 임시 객체를 만드는데 내가 앞에서 만든 String s객체를 복사하는 것이다.

그 이유는 내가 해쉬 공식을 만들 수 없으니까. 해쉬에 대해 기본적인 느낌만 느껴보기 위해 이와 같이 공부해 보는 것이다.

 

6. 정리를 해보자 unordered<String, hash<String>>에서 내부적으로 hash<String>()()동작을 할텐데 hash<String>임시 객체가 만들어지고 함수 호출 연산자기 실행된다. String s를 인자로 받아서 해시코드(정수형)을 만들고 값을 return해준다.

return받은 정수형 해시코드를 인덱스로 해서 value를 저장한다.

 

학습 장소: 한국공학대학교 게임공학과 수업

참고: https://en.cppreference.com/w/