해시란 어떤 집합의 객체들에 제한된 구간의 수치 값을 대응시키는 어떤 함수입니다.
“좋은” 해시 함수의 조건은 다음과 같습니다.
- 빠르게 계산됩니다 — 객체 크기에 선형인 시간이 걸립니다;
- 값이 그리 크지 않습니다 — 64비트에 들어갑니다;
- «결정론적 무작위성» — 해시가 $n$가지 서로 다른 값을 가질 수 있다면, 두 무작위 객체의 해시가 일치할 확률은 대략 $\frac{1}{n}$입니다.
보통 해시 함수는 일대일 대응이 아닙니다. 하나의 해시에 여러 객체가 대응될 수 있습니다. 이러한 함수를 전사 함수라고 부릅니다.
어떤 문제에서는 객체 자체보다 해시를 다루는 편이 더 편리합니다. 길이가 $m$인 문자열 $n$개가 주어지고, 임의의 두 문자열이 같은지 확인하라는 요청을 $q$번 받는다고 합시다. $O(q \cdot n \cdot m)$의 나이브한 확인 대신, 모든 문자열의 해시를 계산하여 저장해 두고 질의에 답할 때 두 문자열이 아니라 두 수를 비교할 수 있습니다.
실생활에서의 응용
- 체크섬. 전송되는 큰 파일의 무결성을 확인하는 간단하고 빠른 방법은 송신자 측과 수신자 측에서 각각 해시 함수를 계산하여 비교하는 것입니다.
- 해시 테이블. STL의
unordered_set클래스는 다음과 같이 구현할 수 있습니다. 처음에 비어 있는 단일 연결 리스트 $n$개를 만듭시다. 치역이 $[0, n)$인 아무 해시 함수 $f$를 하나 잡읍시다..insert(x)를 처리할 때는 원소 $x$를 $f(x)$번째 리스트에 추가합니다..find(x)에 답할 때는 $x$번째 원소가 $f(x)$번째 리스트에 있는지 확인합니다. 해시 함수의 “균등성” 덕분에, $k$번 추가한 뒤 예상되는 비교 횟수는 $\frac{k}{n}$ = $O(1)$이 되며, 이는 $n$을 올바르게 선택했을 때 성립합니다. - 메모이제이션. 동적 계획법에서는 때때로 배열로 「펼치기」 위해 어떻게 인코딩해야 할지 분명하지 않은 상태를 다루어야 할 때가 있습니다. 예: 체스 포지션. 이런 경우에는 DP를 재귀적으로 작성하고 계산된 값을 해시 테이블에 저장해야 하며, 상태를 식별하기 위해서는 그 상태의 해시를 사용해야 합니다.
- 동형성 검사. 어떤 복잡한 구조(예를 들어 트리)가 서로 일치하는지 확인해야 한다면, 그 구조에 대한 해시 함수를 고안하고 문자열 예제와 마찬가지로 그 해시를 비교할 수 있습니다.
- 암호학. 데이터베이스에는 비밀번호 자체 대신 비밀번호의 해시를 저장하는 것이 더 올바르고 안전합니다. 해시 함수는 원래 값으로 일의적으로 되돌릴 수 없기 때문입니다.
- 다차원 공간에서의 검색. $n$차원 공간에 있는 $m$개의 점 중에서 가장 가까운 점을 결정론적으로 찾는 문제는 빠르게 풀리지 않습니다. 하지만 서로 가까이 있는 원소들에 같은 해시를 부여하는 해시 함수를 고안하여, 쿼리와 같은 해시를 가진 원소들 사이에서만 탐색할 수 있습니다.
해시하는 대상은 문자열, 이미지, 그래프, 체스 포지션, 단순한 비트 파일 등 매우 다양할 수 있습니다.
이 절에서는 주로 문자열에 초점을 맞추겠습니다.