cgiosy.dev
Hash Table, Open Addressing, Robin Hood Hashing 본문
아래에서 $N$은 테이블에 저장된 키 개수, $M$은 테이블 크기를 의미한다.
$N$개의 키에 대한 해시값이 모두 $M$ 미만이고 distinct하다면, 즉 해시가 Perfect Hash Function이면 단순히 크기 $M$의 배열 각각에 키에 대한 값을 저장하면 된다.
Perfect Hash Function을 사용하는 해시 테이블은 보통 FKS 해싱 기반인데, 이에 대해선 여기서 설명하지 않겠다.
그보단 대체로 xxHash나 wyhash처럼 매우 빠르며 충분히 랜덤함을 보장하는 해시 함수를 쓰게 된다. 문자열의 특정 부분만 뽑아 쓰는 해시도 있긴 한데, 이 글에선 해시 함수가 서로 다른 키에 대해 완전히 랜덤한 출력을 보장함을 가정한다.
생일 문제에 의해, $N = \sqrt{M}$ 정도만 돼도 테이블에서 동일 해시값을 가진 두 키가 있을 확률이 50%나 된다. 물론 M을 늘릴 수록 저 확률은 감소하지만, 0이 될 수도 없고 메모리엔 제한이 있다.
때문에 제한된 $M$에서 최소한의 작업으로 동일한 해시값을 가진 키들을 구분하는 방법이 필요하다. 이런 방법 중 유명하고 간단한 방법들을 소개하겠다.
Chaining
동일한 해시 키들은 리스트나 트리에 넣는다.
탐색 시, 해당 해시 값의 위치에 저장된 키 목록을 나이브하게 탐색한다.
평균 $O(\frac{N}{M})$ 정도의 중복이 발생하는데, $N = O(M)$이도록 유지할 수 있으면 탐색이 평균 $O(1)$인 셈이다.
C++의 std::unorderd_map은 명세에 체이닝이어야 함이 반쯤 명시되어 있다. GCC 확장으로 cc_hash_table과 gp_hash_table이 있다. 커스텀 해시 함수가 없다면, 셋 모두 어렵지 않게 적대적 입력을 생성 가능하다.
Java의 HashMap 계열은 기본적으로 링크드 리스트로 체이닝을 하지만, 한 버킷에 데이터가 쏠려 있으면(적대적 입력) BBST로 전환해서 최악의 경우를 $O(\lg N)$으로 낮춘다.
Open Addressing
리스트나 vector를 달아서 체인을 처리하는 대신, 해시 테이블 배열 내에서 어떻게든 잘 처리하는 방식이다.
아래에서 $L = \frac{M}{M - N}$이며, load factor $\lambda = \frac{N}{M}$에 대해 $\lambda = 1 - \frac{1}{L}$임을 참고하라.
Linear Probing
해시 값이 동일한 키들(체인)은 테이블에서 연속한 위치에 저장한다.
조회 시 우선 키의 해시 값을 구해 테이블에서 위치를 잡는다. 해당 위치에 저장된 키가 찾는 키와 동일하다면 해당 위치를 반환한다. 아니라면 위치를 $1$ 증가시킨 후 탐색을 반복하며, 체인의 끝에 도달하면 해당 키가 테이블에 없단 것이다.
삽입은 조회와 비슷한데, 체인의 끝에 키를 추가한다. 단, 탐색 중 동일한 키를 발견하면 추가할 키가 테이블에 이미 있단 것이다.
삭제는 두 가지 방법이 있다. 하나는 삭제할 키를 체인의 끝으로 swap해서 보내고 체인 끝을 제거하는 것이고, 다른 하나는 그냥 해당 위치에 삭제 표시(tombstone)를 남기는 것이다. 둘 모두 체인이 끊어지지 않는다.
tombstone이 있는 경우 삽입 시엔 빈 칸으로 해석하고 해당 위치에 키를 덮어쓴다. 조회 시엔 그냥 다음 칸으로 넘어간다.
좀 더 구체적인 내용은 저 아래 Robin Hood 해싱 부분에서 함께 설명한다.
장점은 랜덤 액세스를 단 한 번만 해서 캐시 효율이 높다. 매우 직관적이고 짜기 쉽다. 삽입과 테이블에 있는 키 조회만 사용할 경우, 충분한 공간이 할당되면 제일 빠르다.
단점은 테이블에 없는 키 조회가 느리다. 키 제거가 섞이거나 테이블에 키가 가득 찰 수록 크게 느려진다. 이를 완화하기 위한 여러 방법이 존재하지만, 기본적인 Linear Probing의 소요 시간은 다음과 같다.
삽입에 걸리는 총 시간은 $\Theta(NL)$이고, 이후 테이블에 없는 키 조회 및 삽입은 한 번 당 $\Theta(L^2)$이다.
예를 들어 테이블의 99%가 가득차 있는 경우, $L = 100$이므로 테이블에 없는 키 조회 및 삽입이 대략 $10000$배 느려지는 셈이다.
이런 문제가 발생하는 이유는 긴 체인들끼리 이어질 경우 체인의 길이 분포가 더더욱 악화되기 때문이다.
다른 문제로 긴 체인은 테이블에서 차지하는 구간이 넓기 때문에, 삽입 시 긴 체인에 연결될 확률이 높고, 체인들의 길이가 고루 분포되지 않고 긴 게 더욱 길어지는 현상이 있기도 하다.
가장 쉬운 해결법은 그냥 $M$을 늘리는 것이다. $N$이 $M$의 50% 이하이도록 잡는 게 좋다.
그러나 메모리가 그만큼 넉넉한 상황은 많지 않으며, 캐시 크기의 문제로 무작정 $M$을 늘리면 오히려 느려지는 경우도 발생한다. 하여튼 근본적인 해결책은 되지 않기에 $\Theta(L^2)$이란 끔찍한 복잡도를 낮추는 기술이 많다.
가장 유명한 건 Quadratic Probing이다. 탐색 및 삽입 시 위치를 $1$씩 증가시키는 대신 $1$, $4$, $9$, $16$처럼 수를 제곱해가며 증가시킨다.
예상 탐색 횟수는 $0.5 + \frac{1}{2L} + \log L$이다. 하지만 캐시 지역성이 좀 희생되는 게 아쉬운 부분.
여러 이유로 인해 삽입 시 reference invalidation을 허용하는 대신, 더 빠른 참조를 가능하게 하는 Robin Hood 휴리스틱이 있다.
Robin Hood Hashing
Linear Probing에서 테이블의 각 키에 대해 '원래 위치'와 '실제 위치' 간의 거리, 즉 해당 키를 조회하기 위해 필요한 탐색 수를 함께 저장해둔다.
삽입 시 다음 칸으로 넘어가기 전, 삽입할 키의 거리보다 지금 위치에 저장된 키의 거리가 작다면 둘을 swap한다. 이는 각 키의 거리를 최대한 차이나지 않게, 동시에 해시 값을 기준으로 '정렬된' 상태를 유지하는 것으로 해석 가능하다.
덕분에 조회 시 지금 위치에 저장된 키의 거리 $d_{pos}$가 현재 탐색한 거리 $d$ 미만이면 테이블에 해당 키가 없음을 조기에 알 수 있다. 조회할 키의 해시가 $h$라 하면, 지금 위치에 저장된 키의 해시 값은 $h + d - d_{pos}$이고, $h < h + d - d_{pos}$면 뒤에도 전부 $h$보다 더 큰 해시를 가진 키만 존재하므로(정렬된 상태라) 더 볼 필요가 없기 때문이다.
$L$이 $3$이나 $4$ 이상으로 좀 큰 경우, Organ Pipe Search란 기법을 적용하기도 한다. 이번엔 $d = d_{pos}$일 가능성이 높은 $d$부터 찍어보는 식이다. 방법은 그저 테이블에서 서로 다른 $d_{pos}$마다 개수를 세주고, 개수가 제일 많은 것부터 시도해보면 된다. 다른 테크닉과 잘 통합하며 깔끔하게 구현하긴 살짝 어렵다.
해시 값을 기준으로 정렬되어 있단 점을 활용한 추가적인 활용법으로, 키가 이미 uniform하게 분포돼 있다면 상위 비트를 해시로 쓰고 범위 탐색(Range Search)도 가능하다. 또 이를 정렬에 활용할 수도 있다.
아무것도 적용하지 않는 기본 Robin Hood의 경우, 조회에 걸리는 시간과 분산(variance)이 $O(L\ \mathrm{polylog}(L))$이라고 한다. $O(L^2)$에 비해 꽤나 개선이 있는 셈.
삭제 기능은 시프트로 처리하는 게 대세였는데, 삽입/삭제가 반복되는 상황에서 특히 $L$에 영향을 많이 받는단 약점이 있다. 그래도 삽입/삭제를 번갈아 하지 않거나 $L$이 그리 크지 않은 대부분의 상황에서 매우 빠르다.
최근에 나온 다른 방법으론 tombstone을 적극 활용해 조회에 걸리는 탐색을 항상 $O(L)$로 줄이는 Graveyard Hashing 테크닉이 있다.
삽입/삭제를 특정 횟수로 했을 때마다 다음과 같이 테이블의 tombstone을 초기화한다.
- 테이블의 tombstone을 '전부' 지운다.
- 테이블에서 $i = 0, 1, 2, ...$에 대해 $i \times \frac{2M}{M-N}$ 위치에 새로 tombstone을 표시한다.
- 이후 $\frac{M - N}{4}$번의 삽입/삭제 후에 초기화가 일어나도록 한다.
초기엔 tombstone이 존재하지 않으며, $\frac{M}{4}$번의 삽입/삭제 후에 초기화가 일어나야 한다.
비교를 위해 테스트가 필요했다. 내가 짠 Robin Hood 구현 및 간단한 테스트 코드. 딱 속도 테스트 용으로만 간단히 짠 거라, 실제 작동은 온전치 않을 수 있으므로 주의하라.
키 조회는 평범한 랜덤과 현실에 좀 더 가까운 Zipf 분포 두 개로 각각 테스트해봤는데, 딱히 이걸로 상대적인 순위가 바뀌진 않았다. 둘 다 똑같은 Open Addressing 방식이니 당연한가? ㅋㅋ
키 $N$개 삽입 - 키 $N$개 제거를 반복하는 것보다 키 $N$개 삽입 후 각 키를 제거 후 즉시 추가를 반복하는 게 더 느렸다. 후자에서 $L \le 2$ 기준으로 $M$이 작을 땐 Graveyard 방식이, $M$이 클 땐 시프트 방식이 좀 더 빨랐다.
한 쪽이 그냥 압도했으면 선택하기 편했을텐데, 좀 짜증나는 결과...
현재 범용적으로 가장 빠른 해시맵인 bytell_hash_map에 비하면 $L = 2$에서 비슷하거나 조금 더 느리고, 테이블에 없는 키 조회는 두 배쯤 걸리기도 한다. 다만 키 삽입만큼은 어지간하면 두 배에서 세 배쯤 빠르다.
$L = 3$인 경우 키 조회는 $M$이 작을 경우 로직의 간결함으로 인해 크게 빠른 모습을 보여준다. $M$이 클 경우 RAM 레이턴시의 비중이 커져 차이가 줄어든다. 테이블에 없는 키 조회는 bytell과 비슷하거나 살짝 더 빠르다.
정확히 몇% 차이나는지에 대해 언급을 피해 보기 답답할 수 있는데, 어쩔 수가 없는 게 CPU의 캐시와 RAM 레이턴시에 따라 결과의 차이가 너무 크다 ㅠㅠ...
M1 맥북의 경우 $M$이 작을 때 Graveyard가 시프트보다 키 조회가 3배쯤 빠른가 하면, 내 오라클 VPS에선 10% - 20%정도밖에 차이가 안 나는 등 상당히 골때린다;
캐시 크기에 상관없이 항상 빠르도록 개선하는 방법은 없을까? 흠..
Swiss Table
(작성 중)
이외
Open Addressing 방식에는 위에 소개한 것들을 제외해도 Cuckoo Hashing이나 Hopscotch Hashing를 비롯한 여러 응용이 있다. 허나 그 중 대부분이 50% 이하의 낮은 load factor에서, 그리고 어쩌면 조금 높은 load factor에서도 Robin-Hood 해싱에 비해 유의미하게 빠르지 않았다.
때문에 실용적이면서, 실제로 꽤 사용되는 해시 테이블에 대해서만 서술하는 게 낫다고 생각해 해당 내용은 쓰려다가 쳐냈다.
구현 시 알아둘 점들
적대적 입력이 없는 경우, 해시 함수의 강도는 최소한의 퀄리티만 보장된다면 해시 테이블의 속도에 그리 영향을 주지 않는다. 나는 피보나치 해싱이나 랜덤 생성기를 가져와서 쓰고 있다.
CPU마다 캐시 크기와 속도가 달라서, RAM 랜덤 액세스 레이턴시도 천차만별이다. 그래서 load factor같은 걸 적절히 잡기가 힘든데, 크게 잡으면 캐시 밖으로 나가서 속도가 크게 느려질 수 있기 때문이다.
벤치마크를 보면, 주로 삽입 테스트에서 dense_hash_map과 robin_map의 load factor가 $0.48$ -> $0.26$으로 전환되는 순간 시간이 크게 증가하는 것을 볼 수 있다.