해싱이라는 건 알고리즘 문제풀이를 해 봤다면 한 번쯤은 들어 보았을 분류이다. 주로 파이썬의 dict, C++의 unordered_set 등이 해싱을 사용해서 구현되었다.
삼성 동계 DX 알고리즘 특강을 들을 때, 해싱을 직접 구현해서 문제를 풀어야 하는 일이 있었다. 해시 함수를 직접 만든 뒤에, 해시가 가지는 시간상의 이점을 활용해서 문제를 해결한다. 그때 당시에는 문제를 푸는 데 꽤나 고생했다. 시간이 조금 지나서 다시 공부해보고 기록한다.
정리한 글에 오류가 있을 수 있습니다. 댓글로 남겨주시면 반영하겠습니다.
방문해주셔서 고맙습니다 🙆🏻♂️
파일 시스템을 생각해 보자. 하나의 디렉토리에 존재 가능한 파일의 수 제한이 존재하지 않는다. 나아가 해당 파일 시스템에서는 디렉토리 내 존재하는 파일들을 사용자에게 보여줘야 하거나, 특정 파일이 이미 존재하는지 등의 연산이 추가적으로 요구된다. 하나의 디렉토리에 많은 양의 파일이 존재한다면, 이를 어떻게 빠른 시간 내에 찾아 사용자에게 보여줄 수 있을까?
우선 간단한 경우부터 생각해 보자. 디렉토리 내에 파일이 많지 않은 경우, 단순하게 메모리 위에 디렉토리 정보들을 올려둠으로써 해결할 수 있다. 이렇게 전체 키 집합이 크지 않은 경우, 메모리에 모든 키의 정보를 올려두고 바로바로 연산하는 것을 Direct Address Table이라고 한다. 이 방법은 정의에서 나타나는 큰 단점이 있다. 전체 키 집합이 메모리보다 커질 때 문제가 된다. 나아가 실제로 저장되는 키 집합이 전체 키 집합에 비해 작으면 메모리 낭비가 되기도 한다.
이를 극복하기 위해 Hash Table이라는 방식이 고안되었다. Hash table의 경우, 실제 사용하는 키만큼을 메모리에 올리도록 되어 있고, 이 테이블에 매핑하기 위해 해시 함수 $h$를 사용한다.
해시 함수 $h$는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 함수 계산의 경우는 기계적인 계산이므로 $O(1)$ 이라는 시간 안에 찾을 데이터를 매핑할 수 있다. 알고리즘 문제해결에서 사용되는 해싱의 경우, 문자열 내지 그래프 구조를 다른 문자열이나 수로 매핑하는 데 사용된다. 해시 함수의 경우에는 여러 번 실행해도 같은 결과가 나오며, 사용하는 키 집합이 커질수록 같은 곳으로 매핑될 확률이 증가하게 되어 있다. 두 개의 키 $k_1$, $k_2$에 대해서 $k_1 \neq k_2$이면서 $h(k_1) = h(k_2)$인 경우를 해시 충돌(Hash collision)이라고 한다.
임의의 길이의 데이터는 문자열이나 트리와 같은 그래프, 고정된 길이의 데이터는 C++에서 저장하는 자료형인 int, long long 등이 이에 해당한다. 간단하게 문자열을 수로 매핑하는 방법으로는 흔히 사용하는 10진법을 차용한 방법을 쓸 수 있다.
수를 쓸 때에는 다음과 같은 등식이 성립한다.
$$12\ 345 = 1 \times 10^4 + 2 \times 10^3 + 3 \times 10^2 + 2 \times 10^1 + 1 \times 10^0$$
위와 비슷한 방식으로 알파벳 하나를 0 ~ 25까지 대응해서 쓰는 방법이 있다. 예를 들면 아래와 같이 매핑한다.
$$\text{“abc”} = 0 \times 26^2+ 1 \times 26^1 + 2 \times 26^0$$
하지만 위와 같은 방식은 $\text{“a”}$와 $\text{“aa”}$를 구분할 수 없다. 두 문자열 전부 위 식을 적용하면 $0$을 뱉어내기 때문이다. 따라서 알파벳을 1부터 26까지 매핑하는 방식으로 27진법을 사용할 수 있다. 조금 더 일반화해 보자. 우리가 사용할 문자열에는 알파벳 소문자만 들어있지 않을 수 있기 때문에, 사용할 문자의 종류를 $C$개라고 한다면 다음과 같이 해시 함수를 만들 수 있다. $(L = |s|, C < p)$
$$h(s) = s_{1} \times p^{L-1} + s_2 \times p^{L-2} + … + s_{L-1} \times p^{1} + s_{L} \times p^0$$
문자열의 길이가 길어질수록 해당 수의 범위는 고정된 크기를 벗어날 수 있다. 해시 함수는 고정된 길이의 데이터로 매핑해주는 함수이므로, 범위를 넘어간다면 추가적인 연산이 필요하다. 이는 나머지 연산을 사용해 범위 내로 줄여줄 수 있다.
$$h(s) = s_{1} \times p^{L-1} + s_2 \times p^{L-2} + … + s_{L-1} \times p^{1} + s_{L} \times p^0 \\\ \mod M$$
위와 같은 해싱 방법을 Polynomial Hashing이라고 한다. 이 때 $p$는 사용할 문자의 종류보다 많아야 한다. (구현에 따라 $p$의 지수가 $0, 1, 2…$꼴이 될 수도 있고, $n-1, n-2, …, 0$꼴이 될 수도 있다. 개념에서 크게 벗어나지 않으니 구현의 일관성을 가지는 데 주의하자.)
나머지 연산을 취하지 않았을 때에는 각 문자열이 고유한 해시값을 가지지만, 고정 크기로 맞추면서 해시가 충돌될 가능성이 생긴다. 즉, 두 문자열 $str_1, str_2$에 대해서 $h(str_1) = h(str_2)$이지만 $str_1 \neq str_2$인 경우가 발생할 수 있다. 이 확률은 $\frac{1}{M}$에 가깝다(자세한 설명은 이곳을 참고하자). 나아가 $p$와 $M$이 서로소이고, $M$이 소수일 때 충돌이 덜 일어난다.
단순히 해시를 들고 있는 것보다, 문자열의 부분 문자열을 가지고 문제를 해결해야하는 경우가 많다. 따라서 부분 문자열에 대해서도 해시값을 빠르게 구할 수 있어야 한다.
hash[i]를 $s_{1..i}$의 해시값이라고 하면, 글자 하나가 늘어날 때마다 이전 해시에 $p$를 곱한 뒤, 문자열에 해당하는 값을 더한다. 범위를 초과할 때를 대비해 나머지 연산까지 진행한다. 문자열의 해시를 구하는 데에는 $O(|s|)$면 충분하다. 이 알고리즘은 Rabin-Karp 알고리즘으로 알려져 있다. 이런 식으로 해시값을 구해두면, 부분 문자열의 해시값은 $O(1)$에 구할 수 있다. $’abcde’$의 해시 값을 구한다고 해 보자. 편의상 나머지 연산은 생략했다.
$$ \begin{alignat}{1} &hash[1] = a \times p^0 \notag \\ &hash[2] = a \times p^1 + b \times p^0 \notag \\ &hash[3] = a \times p^2 + b \times p^1 + c \times p^0 \notag \\ &hash[4] = a \times p^3 + b \times p^2 + c \times p^1 + d \times p^0 \notag \\ &hash[5] = a \times p^4 + b \times p^3 + c \times p^2 + d \times p^1 + e \times p^0 \notag \end{alignat}$$
여기서, $s_{3..5}$의 해시값을 구하고 싶다. 해당 해시값은 아래와 같다.
$$h(s_{3..5}) = c\times p^2 + d\times p^1 + e\times p^0$$
$$ \begin{alignat}{1} &hash[1] = a \times p^0 \notag \\ &\color{blue}hash[2] = a \times p^1 + b \times p^0 \notag \\ &hash[3] = a \times p^2 + b \times p^1 + c \times p^0 \notag \\ &hash[4] = a \times p^3 + b \times p^2 + c \times p^1 + d \times p^0 \notag \\ &\color{red} hash[5] = a \times p^4 + b \times p^3 + c \times p^2 + d \times p^1 + e \times p^0 \notag \end{alignat}$$
hash[5]에서 hash[2]에 해당하는 해시값에 $p^{5-3+1}$를 곱한 뒤, 빼야 한다는 것을 알 수 있다. 일반화하면 아래와 같다.
$$s_{l..r} = hash[r] \ -\ hash[l-1] \times p^{r-l+1}$$
해시 배열과 $p$의 거듭제곱들은 모두 전처리가 가능하고, $O(|s|)$의 시간이 걸린다. 이후 부분 문자열의 해시값은 구간 합을 구하는 것처럼 단순 계산이 가능하다. 위 식에서 생략했던 나머지 연산을 잊지 말자.
constexpr ll BASE = 53;
constexpr ll MOD = 1e9+7;
void hash_string(string str){
int n = str.length();
p[0] = 1;
for(int i = 1; i <= n; i++){
h[i] = ((h[i-1] * BASE) % MOD + str[i-1]) % MOD;
p[i] = (p[i-1] * BASE) % MOD;
}
}
ll get_hash(int l, int r){
return (h[r] - (h[l-1] * p[r-l+1]) % MOD + MOD) % MOD;
}
이러한 방식으로, KMP를 사용하는 것으로 널리 알려져 있는 BOJ 1786: 찾기를 풀 수 있다. 전체 해시값을 구해준 뒤, 문자열 길이 $n$, 패턴 길이 $m$에 대해서 문자열의 $s_{i..i+m-1}$의 해시값을 패턴의 해시값과 비교하면 된다.
이번에는 BOJ 3033: 가장 긴 문자열을 보자. 최대 길이 $200\ 000$인 문자열에 두 번 이상 등장한 부분 문자열의 최대 길이를 구해야 한다. 해싱 한 번 하는 데 $O(|L|)$이 들 테고, 이걸 모든 가능한 부분 문자열의 길이에 대해서 판별하면 오랜 시간이 걸릴 것이다.
조금만 다르게 생각해보면 문제를 어떤 식으로 풀어야할 지 감이 온다. 만약 길이 $5$의 부분 문자열이 두 번 이상 등장한다면, 해당 부분 문자열에서 문자 하나를 떼어낸 길이 $4$의 문자열도 당연히 두 번 이상 등장할 것이다.
이 성질을 활용해서 부분 문자열의 길이에 대해서 매개변수 탐색을 해줄 수 있다. 만약 부분 문자열을 해싱한 값이 충돌한다면, 같은 문자열일 확률이 있지만 이곳에서는 해시 테이블을 관리해야 하기 때문에 $M$을 작게 잡아야 하고, 충돌 시에 문자열이 서로 같은지도 한 번 더 확인해야 한다.
이 때 걸리는 시간복잡도는 $O(|L| + |L| \times (\log{|L|} + \alpha))$ 이고, $\alpha$는 해시 충돌 시 문자열을 확인하는 시간이다.
References
삼성 DX 알고리즘 게시글
https://www.acmicpc.net/blog/view/67
https://codeforces.com/blog/entry/100027
https://blog.naver.com/kks227/220927272165
https://cp-algorithms.com/string/string-hashing.html
https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98
https://github.com/justiceHui/SSU-SCCC-Study/blob/master/2022-winter-intermediate/slide/08.pdf
연습문제
https://www.acmicpc.net/problem/10840
https://www.acmicpc.net/problem/1786
https://www.acmicpc.net/problem/21162
https://www.acmicpc.net/problem/17228
https://www.acmicpc.net/problem/3033