[Algorithm]문자열 해싱

https://m.blog.naver.com/PostView.nhn?blogId=withham1&logNo=221230878379&proxyReferer=https%3A%2F%2Fwww.google.com%2F

문자열 해싱(String Hashing)

 

햄과함께님 정리해주셔서 감사합니다.

 

 

hash(s) = (s[0] + s[1]* p + s[2] * p2 + … + s[n-1] * pn-1) mod m

 

위의 수식은 길이가 n인 문자열 s의 해시값을 구하는데 주로 사용되는 방법이다. 
p와 m은 특정 양수이며 이 수식은 polynomial rolling hash function라 한다.
p는 보통 문자열에 입력할 수 있는 문자의 개수와 비슷한 정도가 좋으며 보통 영어 소문자만 들어가는 경우 p=31 을 사용하고 대소문자 모두 들어가는 경우 p = 53을 사용한다.

m은 모듈로에 사용되는 양수로서 해시 값이 무수히 커지는 것을 방지한다.
이를 쓰면 해시 값이 중복되는 경우도 발생할 수 있으므로 큰 소수값으로 설정하는 것이 좋다.

 

long long hash(string s){
    const int p = 53;
    const int m = 1e9 + 9; //10^9 + 9

    int hash_val = 0;
    int pow_p = 1;

    for(int i = 0; i < s.length(); i++){
        hash_val = (hash_val + (s[i] - 'a' + 1) * pow_p) % m;
        pow_p = (p * pow_p) % m;
    }
    return hash_val;
}

문자열 s의 해시 값을 구하는 함수는 위와 같다.

만약 길이가 M인 문자열 s와 길이가 N인 문자열 pattern 있는데 문자열 s에서 pattern이 몇 번 나오는지 구할 때
브루트 포스 방법으로 이를 구하면 부분문자열과 pattern이랑 같은지 확인하는데 O(M)이 걸리기 때문에 총 시간복잡도는 O(NM)이 된다. 
하지만 해시를 사용하면 patter이랑 같은지 확인하는데 O(1)이 걸리기 때문에 O(N)이 소요된다. (정확히 말하면 문자열 pattern의 해시값도 구해야 하므로 O(N + M)이다.)