롤링 해시를 할때 주의해야 할점

해시테이블 크기가 1000000007 x 998244353 이었는데 터졌습니다

해싱을 해야하는 문제에서 계속 터져서 하도 화가 난 나머지 오랜만에 블로그 글을 적습니다.

지금까지 제가 당해보며 얻게 된 해싱 관련 팁을 공유합니다.

만약 다른 해싱 관련 팁이 있으면 제보해주세요.

 

1. 해싱이란

 

문자열 $a[1,2,...,n]$이 존재하고, 어떤 적절한 숫자 $x$와 $p$가 존재할때, 다음과 같은 값을 정의할 수 있습니다.

 

$f(a,x,p) = a[1] x^{n-1} + a[2] x^{n-2} + \cdots + a[n] x^0$ mod $p$

 

이렇게 어떠한 문자열$a$를 한개의 값 $f$로 표현하는것을 해싱이라고 합니다. 사실, 해싱 방법은 위에서 적힌 수식 말고도 여러가지가 존재하나 PS에서 해싱이라고 하면 십중팔구 저 위에서 적힌 해싱방법을 이용합니다. 위 방법은 롤링 해시(Rolling Hash)라고 부르는 방법인데, 다른 해싱보다 방법이 간단하며, 충돌 가능성도 적고, 계산하기 매우 간편하기 때문입니다. 예를 들어, 문자열 $a[1,..,n]$과 $x,p$가 주어졌을 때, 임의의 $l,r$에 대하여 $f(a[l,...,r],x,p)$를 $ \mathcal{O}(\log n)$의 시간에 계산할 수 있습니다(세그먼트 트리 자료구조가 필요합니다).

 

롤링 해시 이외에 문제에 따라서 다양한 형태의 해싱을 해야할때도 있습니다. 예를 들어, 다음과 같은 해싱도 자주 사용됩니다.(문자의 개수에 관한 쿼리가 주어지는 경우 롤링 해시는 한계가 있어 다음 해싱이 자주 쓰입니다)

 

적당한 함수 $g$가 존재할때 $f(a,g) = g(a[1]) \oplus g(a[2]) \oplus \cdots \oplus g(a[n])$

 

여러 해싱 방법중에서 가장 많이 사용되는게 롤링 해시고, 또 가장 많이 실수하는게 롤링 해시이기 때문에, 이 글에서는 롤링 해시에 관한 주의사항을 다루려고 합니다.

 

2. 롤링 해시를 할때 주의해야 할점

 

해싱은 기본적으로 충돌 가능성, 즉 두 문자열이 다름에도 불구하고 해싱값이 같아서 다른 문자열을 같다고 판단하는 문제가 필연적으로 발생합니다. 이러한 충돌 가능성은 낮긴 하나, 구현을 잘못했을 경우, 혹은 위에서 말한 $x$와 $p$값이 밝혀진 경우 악랄한 테스트케이스 제작자에 의하여 충돌이 일어날 수 있습니다. 따라서 롤링 해시를 할때는 유명한 $x$와 $p$를 사용하면 안됩니다. 유명한 $x$와 $p$값을 사용할 경우, 악랄한 TC 제작자에 의하여 해시가 충돌할 수도 있습니다!

 

1) $p$를 아주 큰 소수로 설정해야 합니다. $p$가 작으면 해시 테이블 크기가 작아져 충돌 가능성이 매우 높아지며, $p$를 소수로 잡지 않으면 충돌하기 쉽고, 특정 문제를 풀때 불편할 수 있습니다. 예를 들어, 문제에 따라서 $a[1,...,n]$의 해싱값에서 $a[1,..,n-1]$의 해싱값을 구해야 하는 경우가 생길 수 있습니다(트리를 DFS로 탐색하면서 트리의 노드를 해싱하는 경우 등등). 이 경우, $x^{-1}$ mod $p$값을 계산해야 하는데, $p$가 소수가 아니면 문제가 생길 수 있기 때문입니다.

 

2) $x$와 $p$는 서로소 관계를 가져야 합니다. 1)에서 설명하였듯 $x$와 $p$가 서로소가 아니면 $x^{-1}$ mod $p$를 계산 할 수 없어 문제가 생길 수 있고, 그것이 아니더라도 $x$와 $p$가 서로소가 아니면 해시 테이블 크기가 $p$에서 $p/\gcd(x,p)$로 줄어드는 효과를 내기 때문에, 해시 충돌 확률이 크게 높아지게 됩니다. $x$와 $p$가 서로소인지 아닌지 판단하는게 귀찮다면, 그냥 $p$를 소수로 잡으면 말끔하게 해결됩니다.

 

3) $x$를 랜덤하게 잡는것이 좋습니다. $x$값은 $p$와 서로소기만 하면 되기 때문에, $p$를 소수로 잡았다면 $x$값이 무엇이든 상관 없습니다. 정확하게는, $x$값이 $a$의 문자열에 속한 문자의 개수 초과, $\sqrt{p}$ 이하로 잡는것이 좋습니다. 그러므로 이 범위 내에서 $x$값을 랜덤하게 잡는게 좋습니다. $x$를 고정시켰다면, 추후에 uphack당할 가능성이 있습니다. 이거 경험담입니다.

https://codeforces.com/contest/1794/submission/196033833

 

4)  절대 오버플로우를 이용한 해시를 하지 마십시요. 몇몇 PS 블로그등에서 오버플로우가 일어나도 어짜피 같은 문자열이라면 오버플로우가 일어나는 것도 똑같을테니 결과값은 변하지 않는다, 라고 말하고 있습니다. 이 말은 사실입니다 - 오버플로우가 일어나도 결과값이 같으면 두 문자열은 높은 확률로 같겠지요. 하지만 이 방법은 악랄한 TC 제작자에 의하여 저격 TC를 맞고 틀릴 가능성이 매우 큽니다. 심지어 $p$를 998244353등 유명한 소수를 사용했을때보다 틀릴 가능성이 아주 큽니다. 그러므로 절대 오버플로우를 이용한 해싱을 하면 안됩니다.

 

이유는 간단한데요, 오버플로우를 이용한 해시는 $p = 2^{64}$로 두고 롤링 해시를 하는 것과 완전히 같은 결과를 내게 됩니다. 그리고 $p=2^{64}$는 소수가 아니기 때문에 해싱할때 충돌이 심하게 일어날것이란 예상을 할 수 있습니다. 실제로 $p=2^{64}$일때 $x$값에 상관 없이 무조건 해시 충돌을 일으키는 두 문자열을 만드는것이 가능합니다. 그러니 몇번이고 강조하지만 절대 오버플로우를 이용한 해시를 하지 마세요.

 

여담이지만, SCPC 2017 본선 B? C? 문제에서 제가 오버플로우를 이용한 해시를 써본적이 있습니다. $x$를 10번넘게 바꿨는데도 계속 해시충돌이 발생하여 결국 그 문제를 못풀어 5등상을 못탄 쓰라린 기억이 있습니다. 그러니 몇번이고 말하지만 오버플로우를 이용한 해시를 하면 안됩니다.