해싱(Hashing)

1. 개요

해싱(Hashing)은 긴 길이의 문자열이나 큰 크기의 값을 어떤 작은 값으로 치환하는 방법이다.
특히 문자열 관련 문제에서 강력한 힘을 발휘하며, 본 글에서 소개할 방법에 따르면, 구현이 간단할 뿐만 아니라 해싱 충돌이 발생할 확률이 매우 낮기 때문에(충돌이 나지 않는다고 가정) 실제 대회에서 자주 사용된다.

2. 구현

dad라는 단어가 있다고 생각하자. 이 단어를 하나의 정수로 치환하려고 한다.
기본적인 아이디어는 "문자의 종류" 진법으로 생각하여 정수로 치환하는 것이다.
'a'는 1, 'b'는 1, … , 'z'는 26으로 생각하자.
dad는 아래처럼 하나의 값으로 표현할 수 있다.

'a'를 0부터 취급하지 않는 이유는 "a"와 "aaa"를 구분하지 못함에 있다.
아래의 코드는 하나의 문자열 str에 대해 위의 방법으로 해시값을 계산한 것이다.

사용하는 프로그래밍 언어가 C/C++ 혹은 Java인 경우 계산된 해시값은 크기가 매우 커져서 자료형의 범위를 벗어날(overflow) 수 있다. 하지만 overflow가 발생하더라도 덧셈(+), 뺄셈(-), 곱셈(*) 3가지 연산만 사용한다는 가정 하에서는, 본래의 값이 같다면 overflow값 또한 같다. 따라서 64bit 자료형에 위의 구현처럼 해시값을 계산하고, overflow가 발생하더라도 그 값을 그대로 해시값으로 취급한다.

3. 응용

ㄱ. 부분 문자열

한 문자열이 주어졌을 때에, 그 문자열에서 길이가 L인 가능한 모든 부분 문자열(substring)의 해시값은 어떻게 계산할 수 있을까. 예를 들어, 주어진 문자열이 "dogisdog"이고 L=3인 경우를 살펴보자.
dog에 대한 해시값을 계산하면 다음과 같다.

ogi에 대한 해시값을 계산하면 다음과 같다.

따라서 인접한 부분 문자열 간의 해시값은 아래의 과정으로 계산된다.
1) 이전에 계산한 부분 문자열의 가장 앞 글자의 항 제거 = 해시값에서 빼기
2) 남은 항의 차수 1씩 증가 = 해시값에 '문자의 종류' 곱하기
3) 추가된 가장 마지막 글자의 항 추가 = 해시값에 더하기

첫 부분 문자열 dog에 대한 해시값과 마지막 부분 문자열 dog에 대한 해시값이 같은 것을 확인할 수 있다.

ㄴ. 트라이(Trie)

계산된 해시값에 대해서 본래의 값(문자열 혹은 큰 숫자)을 찾으려면 어떻게 할 수 있을까? 해시값에 대한 Trie를 구성하여 해결할 수 있다.
트라이에 대해 생소하다면 kks227님의 블로그 글을 참고하여 알아보자.

4. 연습문제

1) COCI 2006/2007 Contest #5 6번
2) 2014년 ACM-ICPC 한국 예선 G번
3) RUN Programming Contest, Fall 2009 FANMEETING
4) 제1회 알고스팟 새싹 콘테스트 NUINJABMK
5) SWERC 2014 J번