해시 테이블(Hash table)

이름으로 전화번호를 찾는 일을 생각해 봅시다. 이름을 정렬해 두고 이진 탐색⁠(binary search)⁠을 하면 $\log_2 n$번쯤 비교해야 하지만, 해시 테이블은 n이 아무리 커도 평균 한두 번이면 찾습니다. 비결은 키(이름)를 해시 함수라는 함수⁠(function)⁠로 뒤섞어 큰 수로 만들고, 칸의 개수 m으로 나눈 나머지를 칸 번호로 쓰는 것입니다. 넣을 때도 찾을 때도 같은 계산을 하니 그 칸만 보면 됩니다.

칸 수 $m =$ . 하나 넣기 다섯 개 넣기 비우기

키의 가짓수는 칸 수보다 훨씬 많으니, 서로 다른 키가 같은 칸에 떨어지는 충돌은 피할 수 없습니다(비둘기집 원리⁠, pigeonhole principle⁠). 게다가 충돌은 생각보다 훨씬 일찍 일어납니다. 해시 함수가 키를 칸들에 고르게 흩뿌린다고 하면 이것은 바로 생일 문제입니다. 365칸이면 23개만 넣어도 충돌이 있을 확률⁠(probability)⁠이 절반을 넘습니다. 일반적으로 m칸이면 약 $1.2\sqrt{m}$개에서 그 확률이 절반을 넘습니다. 칸 수의 절반이 아니라 제곱근 규모입니다. 쌍의 수가 키 수의 제곱으로 늘기 때문입니다.

그래서 해시 테이블은 충돌을 막는 대신 감당합니다. 여기서는 같은 칸의 키들을 사슬로 이어 두는 체이닝⁠(separate chaining)⁠을 썼습니다. 키 n개가 m칸에 고르게 퍼지면 사슬의 평균 길이는 적재율⁠(load factor)⁠ $\alpha = n/m$이고, 들어 있는 키를 찾는 데 드는 평균 비교는 $1 + \alpha/2$ 정도입니다(기댓값⁠, expected value⁠). 적재율이 1쯤을 넘으면 칸 수를 두 배로 늘려 모두 다시 넣습니다. 다시 넣는 데 n만큼 들지만, 다음번 늘리기까지 다시 n번쯤 삽입할 수 있으니 그 비용을 나눠 내면 한 번에 상수만큼입니다. 그래서 평균 $O(1)$이 유지됩니다(점근 표기법⁠, asymptotic notation⁠). 이 '나눠 내기' 평균은 확률과 상관없이 늘 성립하는 평균이라, 해시가 고르게 퍼진다는 가정에 기댄 앞의 평균과는 성격이 다릅니다.

'평균'이라는 말에 주의해야 합니다. 앞의 계산은 키들이 칸에 고르게 퍼진다는 가정 위에 서 있습니다. 해시 함수를 아는 사람이 한 칸에 몰리는 키만 골라 넣으면 이 가정이 무너져, 찾기 한 번에 $O(n)$이 듭니다. 2011년 여러 웹 서버가 이런 공격에 약하다는 것이 알려졌고, 그 뒤로 많은 언어가 프로그램을 시작할 때마다 해시 함수에 무작위 값을 섞습니다(무작위 알고리즘⁠, randomized algorithm⁠).

이어지는 곳. 해시 테이블은 프로그래밍 언어가 제공하는 집합⁠(set)⁠과 사전 자료 구조의 바탕입니다. 해시 함수만 따로 쓰기도 합니다. 파일을 짧은 수 하나로 요약해 두었다가 다시 계산해 비교하면 파일이 바뀌었는지 알 수 있습니다(검사합⁠, checksum⁠). 결과로부터 입력을 되찾거나 같은 결과를 내는 다른 입력을 만들기가 현실적인 계산량으로는 불가능하도록 설계한 것이 암호학적 해시입니다. zip의 렘펠–지브 압축⁠(Lempel–Ziv compression)⁠은 앞에 나온 같은 문자열을 해시 테이블로 빨리 찾아냅니다. 두 집합의 공통 원소⁠(element)⁠ 수를 합집합⁠(union)⁠의 원소 수로 나눈 값이 자카드 지수⁠(Jaccard index)⁠인데, 두 집합이 같은 해시값을 낼 확률이 바로 이 지수와 같아지도록 만든 해시(MinHash)로 수많은 문서 가운데 비슷한 것을 골라내기도 합니다.