알고리즘 문제 풀 때 쓰는 해시 종류들

순서 보존 (문자열, 순열 등)

이 경우, 라빈 카프 해싱으로 잘 알려진 $\sum_{i=1}^{n}{c^{n-i} A_i}$를 쓰는 게 일반적이다.
그냥 쓰긴 너무 크니까 보통 적당한 자연수 $m$로 나눈 나머지를 쓰는데, $c$와 $m$이 서로소이며 $A_i$의 최댓값보다 커야 품질이 좋다.

• $A_i$보다 작으면 서로 다른 $A$가 동일한 해시값을 가질 수 있다. ($\mod m$을 안 붙였을 때 기준) 즉 중복이 발생한다.
• $c$와 $m$이 서로소가 아니면 $\mod m$ 했을 때 0 나오기 쉽다. 그리고 굳이 이게 아니어도 딱히 좋진 않을 듯
• $c$를 $m$의 원시근으로 잡으면 좋긴 한데, 사실 PS 범위에선 그까진 필요없고 $c^0, ..., c^{1,000,000}$에서 중복이 없는 정도면 충분하다. 근데 $m = 10^9+7, 2^{32}, 2^{64}$ 등에서 홀수 상당수가 저거 만족하니까 그냥 신경 안 써도 될 것 같다.
• $c^{n-i}$ 대신 $c^i$를 쓰면 롤링 해시로 쓸 때 나눗셈이 필요해져서 모듈로 역원을 써야 할 수 있다. 되도록이면 기존 형태대로 쓰자.
• 계산 시 편의상 $m$을 고정된 상수($10^9+7$이라든지)로 잡으면 저격을 당할 수도 있다. 이 때 $A_i$ 그대로 쓰는 대신, $A$의 어떤 원소 $x$에 대한 랜덤한 값 $R_x$를 런타임에 만들고 $R_{A_i}$를 쓸 수 있다.

순서 보존 X (중복집합 등)

정렬이 가능하다면, 즉 중복집합의 원소가 모두 주어져 있고 이들 간에 비교가 가능하다면, 정렬하고 적당한 해시 쓰는 게 제일 쉽다.

정렬이 불가능하다면, 예를 들어 비교가 불가능하거나 원소가 실시간으로 추가된다면, 집합 $S$의 각 원소 $x$에 대해 랜덤 값 $R_x$를 적절히 만들며 $\sum_{x \in S}{R_x}$를 쓰는 게 나을 수 있다.

사실 PS 범위에서 후자의 케이스에 쓸만한 직관적인 방법 중 가장 좋은 건, 랜덤한 소수 $P_x$들을 만든 후 각 원소 $x$에 대해 배정해주며 $\prod_{x \in S}{P_x}$를 구하는 것이다. 각 중복집합에 대응되는 합성수가 유일함은 자명하다 (혹시 잘 모르겠으면 소인수분해를 생각하자).
다만 소수 구하는 코드를 짜넣음으로써 희생하는 속도나 구현량 등을 감안할 만큼 메리트가 있는 경우는 적은 것 같다. 위의 단순 합만으로도 해시가 겹치기 쉽진 않아서...
만약 이를 사용한다면 주의할 점으로, $\mod m$을 씌울 때 $m$이 소수면 상관없지만 $2^k$ 형태일 경우 $P_x$에 $2$를 쓰면 망한다. $3$ 이상의 소수만 구하도록 하자.

트리

루트가 있다면, 서브트리의 해시로 간선을 정렬하고 순서를 보존하며 해시 목록을 해싱하면 된다.

루트가 없다면, 각 정점이 루트일 때의 해시를 구한 뒤, 순서를 무시하고 해싱해야 한다.
각 정점을 루트로 봐야 할 때 몇몇 조건을 만족하는 트리DP를 부분합 등으로 $O(N)$에 하는 테크닉은 잘 알려져 있고, 어렵지 않게 답을 구할 수 있다. 다만 DP를 할 때 부모 간선 위치를 잘 고려해주지 않으면 순서가 꼬일 수 있으니 주의하자.