<Hash> BOJ 15829 Hashing

문제

15829번 문제는 해시 함수를 설명하는 문제로 문제를 읽고 해시함수를 구현하여 주어진 문자열에 대해 해시값을 출력하면 되는 문제입니다.

접근

해시 함수는 수학적 함수로 동일한 문자열 입력에 대해서 동일한 출력값을 갖는 함수입니다. 해시 함수는 결국 문자열을 정수에 치환해주는 함수입니다. 만드는 방법은 아래와 같습니다.

1. 문자열을 구성하는 각 문자에 대해 고유한 값을 찾는다.(ex) ASCII 값)
2. 고유한 값에 항의 번호에 해당하는 만큼 특정한 숫자 r을 곱한다.
3. 2번까지 계산된 각 값을 숫자 M으로 나눈 나머지를 모두 더한다.
4. 모두 더한 값을 숫자 M으로 나눈다.

위의 과정을 수식으로 표현하면 아래와 같습니다.

보통 r과 M은 모두 소수이고 r과 M은 서로소이어야 합니다. 보통 r: 127 , M:1,000,000,007로 하는 경우가 많습니다.

다만 ! 해시 함수는 동일한 문자열 입력에 대해 동일한 출력값을 갖지만 다른 문자열 입력에 대해 동일한 출력값을 갖을수도 있습니다.이것은 해시충돌이라고 하며 해시 충돌이 일어날 확률은 1/M입니다. 해시 충돌이 왜 일어나냐고 생각하면 어찌보면 당연합니다. 입력의 방법은 무한한데 출력은 M으로 제한되어있기 때문입니다. 비둘기 집 원리를 생각해주시면 됩니다.(10개의 집에 11명의 사람이 들어간다. 최소 집 한개에는 두명 이상의 사람이 있다.) 해시 충돌을 막기 위한 방법으로 한 문자열에 대해 두 개의 Hash값을 구하는 방법이 있습니다. 두 개의 Hash값을 같이 들고다니면 해시 충돌이 일어날 확률을 매우 매우 작게 줄일 수 있습니다.

코드

import java.io.*;
import java.util.*;

class baek__15829 {
    static int r = 31;
    static int MOD = 1234567891;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        String s = br.readLine();

        long ans = 0;
        for (int i = 0; i < s.length(); i++) {
            long j = s.charAt(i) - 'a' + 1;
            for (int k = 0; k < i; k++) {
                j *= r;
                j %= MOD;
            }
            ans += j;
            ans %= MOD;
        }

        System.out.print(ans);
    }
}