해당 포스팅은 unordered_map 클래스 자체보단 해시맵/해시테이블에 대한 내용을 다룹니다.
[기존의 STL std::map]
C++ 11 이전의 기존 STL 컨테이너인 std::map은 요소가 자동으로 오름 차순으로 정렬되는 이진 탐색 트리(BST) 기반의 map이였다. 정확히 말하면 Red-black-tree 라는 스스로 균형을 맞추는 이진 탐색 트리의 일종이다. 여기서 주목해야 하는 것은 오름 차순이 아니라 정렬이 자동으로 된다는 것이다. 기존 map은 정렬이 필요하지 않은 경우에도 자동으로 되었기 때문에 불필요하게 감수해야 하는 오버헤드가 있었다.
[C++ 11의 std::unordered_map]
C++ 11 이전엔 정렬이 필요하지 않은 경우에도 std::map을 사용하여 불필요한 오버헤드를 감수해야 했다. 또는 비표준 라이브러리의 hash_map 컨테이너를 사용해야 했다. 그러다 표준에도 해시맵이 필요하다는 말이 많아졌는지 C++ 11에서 std::unordered_map이라는 컨테이너가 등장했고, 기존의 std::map과 달리 이진 탐색트리가 아닌 해시 테이블로 구현되어 있다. 때문에 요소를 자동으로 정렬하지 않으며 요소의 검색, 삽입, 삭제 연산이 평균적으로 상수 시간에 가능하다. (std::set, std::unordered_set 도 동일한 관계)
[unordered_map의 내부 동작]
기본적으로 해시맵과 동일하므로 해시맵의 동작 방식을 살펴보자. 앞으로 해시맵 또는 그냥 맵(map)이라고 부르자. 일단 map이라는 것은 key에 value를 매칭시켜 pair(쌍) 형태로 데이터를 저장하는 연관 컨테이너이다. 따라서 각 요소는 pair<key, value> 형태로 저장되며 우리는 key를 통해 value에 접근할 수 있다.
여기까진 맵의 기본적인 특징이고, 해시맵의 특징은 바로 key를 통한 value로의 접근이 빠르다는 것이다. 그 이유가 바로 hash 때문이다. hash는 다음과 같이 어떤 데이터를 특정 연산을 통해 특별한 값(보통 integer)으로 변환시켜주는 개념이다.
hash 연산을 하는 함수를 해시 함수라 하며 해시 알고리듬은 MD5, SHA 같의 여러 종류의 알고리듬이 존재한다. 해시맵은 해시 함수를 통해 key를 특정 값으로 변환시키고 이 값을 value를 저장할 공간의 인덱스로 사용한다. 저장되는 공간은 보통 bucket 또는 slot이라고 부르며 다음 그림과 같이 저장된다.
"Hi" 라는 데이터를 동일한 해시 함수에 넣으면 항상 23이라는 데이터를 반환한다. 사실 함수마다 다르지만 원래는 해시 함수의 반환값을 bucket size로 나눈 나머지(mod) 값을 인덱스로 사용하는 방법도 있다. 그러면 무조건 [0, bucket size) 범위의 인덱스가 나오니까. 어쨌든 이는 key를 통해 value가 저장된 인덱스에 상수 시간에 접근할 수 있다는 걸 뜻한다. 즉 O(1)의 시간복잡도를 가진다는 말이다. key-value 쌍이 10개든 100개든 1000개든 해시 함수 한번에 value의 index를 얻을 수 있기 때문이다. 물론 사용하는 해시 함수의 시간 복잡도가 key-value 쌍의 개수에 영향을 받아선 안될 것이다.(그럴 일이 있나 싶겠지만) 해시 함수가 아닌 key를 직접 비교해가며 value를 찾는다면 위 그림에선 24번 비교해야 23번 인덱스의 값에 접근할 수 있을 것이다.
정리해보면 만약 "Apple" - "Samsung"을 쌍으로 저장하고 싶다면 "Apple"을 해시 함수에 넣어 인덱스를 얻고 그 인덱스에 "Samsung"이라는 value를 저장한다. 만약 "Apple"의 value를 읽어오고 싶다면 똑같이 "Apple"을 해시 함수에 넣어 인덱스를 얻은 뒤 bucket에서 읽어오면 된다. 참고로 역은 성립하지 않아서 해시값을 통해 역으로 "Hi"라는 데이터에 접근할 순 없다.
[해쉬 충돌]
그런데 한가지 문제점이 있다. key는 무한함에 비해 bucket의 사이즈는 유한하다. 또한 key가 서로 다르더라도 확률상 해시 함수가 동일한 값을 반환할 수도 있다. 동일한 해시값을 반환하게 되면 value를 저장할 bucket의 인덱스가 동일할 것이고 이는 문제가 된다. 이처럼 다른 key 값으로 동일한 해시값이 나오는 걸 해시 충돌(Hash collision)이라고 한다. 이는 해시맵의 성능을 떨어뜨리는 주범이며 해시 함수가 해결해야 하는 문제이다. 하지만 해시 충돌은 불가피하며 단지 확률을 낮춤으로써 충돌을 최대한 피하는 것이 최선의 방법이다. 충돌을 피하는 방법은 잠시 후 알아보고 먼저 충돌 시의 대안을 먼저 알아보자. 일단 충돌이 난다고 어느 한 value를 버릴 순 없다.
[체이닝(chanining)]
첫 번째로, 해시 충돌이 발생해 동일한 인덱스가 나오면 해당 인덱스에 추가로 이어서 저장하는 방법이 있다.
위 그림에서 25번 인덱스에 이미 값이 존재한다고 가정해 보자. 그리고 나는 "Bird"-"parrot" 쌍을 해시맵에 저장하고 싶다. 그래서 "Bird"라는 key를 해시 함수에 넣었더니 인덱스로 25가 나와 충돌이 일어난 상황이다. 이 때 value가 저장되는 공간을 정적 배열 또는 std::vector와 같은 가변 배열로 구현하여, 충돌 시 기존 value에 이어서 다음 요소에 추가하도록 하면 충돌을 해결할 수 있다. 즉 버켓의 각 요소가 배열이다. 이러한 방법을 연쇄적으로 연결한다 해서 체이닝(chaining)이라 한다. 이 경우 Bird의 value인 "parrot"에 접근하기 위해선 해싱을 통해 인덱스를 얻고 "parrot"이 나올 때까지 순차적으로 탐색해야 할 것이다. 이는 bucket의 인덱스엔 상수 시간으로 접근하지만, 해시 충돌로 인해 요소가 여러개일 경우 일치하는 value를 찾기 위해선 요소를 하나씩 확인해야 한다. 따라서 최악의 경우 선형 시간이 걸릴 것이다.
정말 최악의 경우를 생각해보면 이해하기 쉽다. bucket의 사이즈가 1이라면 모든 value가 하나의 인덱스에 연쇄적으로 저장될 것이고, 이는 pair의 개수인 n번 만큼 돌기에 시간복잡도는 O(n)이 될 것이다. 그러나 bucket을 이렇게 설계하는 경우는 없고 충분한 크기로 설계하고 다른 방법으로도 해시 충돌을 피하기 때문에 보통 해시맵 및 해시테이블의 key로부터 value로의 접근 시간 복잡도는 O(1)으로 말한다.
[개방 번지화(open addressing)]
다른 방법으로는 개방 번지화(open addressing) 또는 개방 주소법이라고도 한다. 용어만 들어보면 어려울 수 있는데 사실 개념은 간단하다. 해시 충돌이 발생하면 그 결과(인덱스)를 버리고 다른 인덱스(비어있는)에 value를 할당하는 방법이다. 즉 다음과 같이 25번 인덱스에 이미 요소가 존재할 경우 비어있는 다른 인덱스를 찾아 그 곳에 저장하는 방식을 말한다. 이는 당연히 규칙이 있어야 할 것이다. 그래야 매번 동일한 결과를 기대할 수 있으니까.
개방 주소법에서 비어있는 인덱스를 탐색하는 방법으로는 여러가지가 있으며 몇가지만 소개하면 다음과 같다.
- 선형 탐사(Linear probing): 고정된 폭(인덱스)으로 탐사한다. 위의 bucket에서 25번에서 충돌이 났을 경우 바로 다음 인덱스를 확인한다. 이 방법은 value가 특정 부분에 밀집되는 클러스터(cluster) 현상이 발생하기 쉽다. 따라서 많은 데이터가 밀집되어 있을 경우 탐색 시간이 길어진다는 단점이 있다.
- 제곱 탐사(Quadratic probing): 선형 탐사와 비슷한데 폭을 단순히 선형으로 증가시키는 것이 아닌 이차식을 통해 인덱스를 구해 한 곳에 데이터가 집중되지 않도록 한다. 하지만 이 또한 같은 해시값이 나온다면 동일한 과정을 거치기 때문에 2차 클러스터가 발생할 수 있다.
- 이중 해싱(Double hashing): 해시 충돌이 발생할 경우 또 다른 해시 함수를 사용하여 증가 폭을 구한다. 증가폭만큼 인덱스를 증가시키며 비어있는 곳을 탐색하는 것이 이중 해싱이다.
다음은 bucket에 요소가 차지한 비율(LF)에 따른 탐사 방법별 성공 및 실패의 평균을 나타낸 표이다. 요소가 bucket을 차지하는 비율이 80% 부터는 fail이 눈에 띄게 많아지는 것을 볼 수 있다. 특히 선형 탐사가 제일 많은 실패율을 보여주고 제곱 탐사와 이중 해싱은 비슷한 비율을 보여준다.
[chaining vs open addressing]
그럼 체이닝과 오픈 어드레싱 중 어떤 방법이 더 좋을까?
먼저 아래 그래프를 보자. x축은 위에서 본 LF이며 y축은 성공 및 실패 회수이다.
일단 처음으로 알 수 있는 것은 네개의 방법 모두 버켓이 꽉 찰수록 효율성이 감소함을 알 수 있다. 이는 저장할 수 있는 공간이 적어질 수록 충돌이 많이 일어나는 것은 당연하기 때문이다. 참고로 제곱 탐사와 이중 해시는 거의 같은 수치를 보여주기 때문에 합친 듯 하다. 또한 알파가 0.5일 경우 네개의 방법 모두 비슷한 수치를 보여준다. 즉 bucket이 반정도 찼을 때는 모두 비슷한 효율성을 보여준다.
체이닝을 제외한 오픈 어드레싱 세개의 방법은 70% 정도까진 적당한 효율성을 보여준다. 즉 오픈 어드레싱을 사용할 경우 이상적인 data의 개수는 bucket의 70% 이하로 유지해야 한다는 의미이다. 그 이후로부턴 resizing을 통해 bucket의 크기를 늘리고 모든 요소를 갱신해야할 것이다.
체이닝은 90% 까진 괜찮은 효율을 보여주고 그 뒤부턴 동일하게 효율이 좋지 않다. 하지만 체이닝은 연결리스트 또는 벡터와 같은 또 다른 자료구조를 추가로 사용하기 때문에 일차적으로 메모리를 많이 차지할 수 있으며, 메모리 할당에 대한 오버헤드가 발생할 수 있고, 추가로 저장되는 데이터들은 bucket의 인덱스와는 또 다른 메모리이기 때문에 locality(지역성)가 좋지 않아 cpu cache에 의해 빠르게 참조되지 않을 수 있다.
정리해보면 bucket 사이즈와 비교했을 때 들어오는 데이터가 적을수록 오픈 어드레싱이 유리하고, 데이터가 bucket을 많이 차지한다면 체이닝이 더 좋은 방법이라고 할 수 있다.
[해시 충돌 최소화 방법]
다음으론 해시 충돌을 최소화 시키는 방법에 대해 알아보자. 사실 제일 중요한 것이 해시 충돌을 최소화시키는 것이다. 해시 충돌을 최소화시키는 방법엔 여러가지가 있는데 첫 번째로 해시함수를 잘 설계하던지 잘 만들어진 해시함수를 사용하는 것이다. 해시 함수가 제일 중요하다. 잘 설계되지 못한 해시함수는 동일한 해시값을 반환할 확률이 높다.
두 번째로 bucket의 size가 충분히 커야한다. 이상적인 bucket 사이즈는 들어오는 key의 개수가 bucket size의 ~40% 정도일 때라고 한다. bucket의 size가 10인데 들어오는 key의 개수가 20개라면 당연히 충돌이 많이 일어날 수 밖에 없다.
세 번째론 bucket의 크기를 소수(prime number)로 설계하는 것이다. 여기서 소수는 2, 3, 5, .. 등과 같은 1을 제외하고 1과 자신으로만 나누어 떨어지는 수를 말한다. 그 이유는 수학적으로 분석해보면 이진수로 볼 때 소수가 어떤 계산으로부터 나올 확률이 훨씬 적기 때문이라고 한다.
결론적으로 잘 만들어진 해시 함수를 사용하고, bucket 사이즈가 데이터를 담기에 충분히 크고 bucket의 크기가 소수라면 웬만해선 O(1)의 성능을 얻을 수 있다.
성능이 좋은 해시 함수로 djb2라는 해시 함수가 있는데 구글에서 쉽게 코드를 얻을 수 있다. 다시 한번 강조하지만 잘 만들어진 해시 함수를 사용하는 것이 중요하다.
'C,C++ > C++' 카테고리의 다른 글
| [C++] 스마트 포인터에 대해 알아보자(2) | 공유 포인터 | std::shared_ptr (1) | 2020.03.21 |
|---|---|
| [C++] 스마트 포인터에 대해 알아보자(1) | 유니크 포인터 | std::unique_ptr (0) | 2020.03.19 |
| [C++] 범위 내의 난수 생성하기 | 비결정적 난수 (0) | 2020.03.05 |
| [C++] 멤버 변수의 오프셋을 계산해주는 offsetof 매크로 (0) | 2020.02.29 |
| [C++] 가독성을 위해 default와 delete 키워드를 사용하기 (클래스) (0) | 2020.02.29 |
댓글