문자열 해싱(String Hashing)

 

해싱 알고리즘은 다양한 문제들을 해결하는데 도움을 준다.

 

문자열을 효과적으로 비교해야 하는 문제들이 있다.

각 문자들을 비교해서 브루트 포스(brute force) 방법으로 문자열(s1, s2)을 비교하는 경우 시간복잡도는 O(min(|s1|, |s2|))가 된다. 더 효과적으로 비교하는 방법의 아이디어는 문자열을 정수형으로 바꾸는 것부터 시작한다. 문자열 대신 숫자를 비교하게 된다면 시간복잡도는 O(1)이 된다.

 

문자열의 해시(hash)라 불리는 정수를 얻기 위해 해시 함수(hash function)를 사용한다.

만약 두 문자열 "ss"와 "tt"가 같다면 그들의 해시 값도 같아야 한다.

hash(문자열)을 문자열의 해시값이라고 한다면 hash("ss")와 hash("tt")가 같아야 한다.

 

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)이다.)

---

참고 : https://e-maxx-eng.appspot.com/string/string-hashing.html

String Hashing - Competitive Programming Algorithms

을 많이 참고하였습니다.

더 상세한 내용을 알고 싶으면 위 링크를 확인해주세요.