Universal Hashing 이해하기

Hash Motivation

hash 자료구조는 Set Interface 에서 n 개의 아이템과 각 아이템의 유일한 키, k 가 존재할 때 search(k) 의 비용을 $O(log(n))$ 에서 O(1) 로 줄이기 위해 고안되었습니다.

정렬된 배열에서 binary search 를 이용하면 search(k) 는 비교모델(Comparison Model)의 Decision Tree 로 표현할 수 있습니다. 따라서 search(k) 의 비용의 lower bound 는 $O(log(n))$ 이라는 것을 증명할 수 있는데요.

빠르지만 비교모델이 아닌 hash 방법을 이용하면 이보다 더 빠르게 원하는 키를 찾을 수 있습니다. 

 

Direct Access Array

먼저 단순하게 어떻게 하면 O(1) 로 search(k) 를 달성할 수 있을 지 생각해봐요.

배열의 인덱스와 키를 1:1 로 매칭시켜서 바로 접근하면 어떨까요

각 아이템에게 유일한 키 $ k \in \{ 0, ..., u-1 \} $ 를 부여하고 각 아이템을 배열 인덱스 k 에 저장하는 거죠.

키는 유일하니 배열 A[k] 에 접근하면 원하는 키를 O(1) 로 바로 찾을 수 있습니다.

 

이렇게 인덱스와 키를 1:1 로 매칭시키고 해당하는 인덱스에 그 키에 해당하는 아이템을 저장하는 자료 구조를 Direct Access Array 라고 해요.

Direct Access Array 를 이용해서 쉽게 문제 해결!! 이라고 하고 싶지만 이 방법에는 아주 큰 문제가 있어요.

공간(Space) 의 문제가 발생하는데요.

키 공간의 크기 $u$ 가 크다면 $u$ 의 크기를 갖는 배열을 만들 때 사용하는 공간이 너무나도 낭비가 되기 때문입니다.

10 개의 알파벳을 키로 갖는다고 한다면 모든 키를 인덱스로 가지는 배열을 만들어야 하는데, 이러면 하나의 비트를 저장하려고 해도

$26^{10} \approxeq17.6 TB$ 의 공간이 필요하게 됩니다.

 

$k \in \{aaaaaaaaaa,\,...,\,zzzzzzzzzz\}, A[abcdabcdab] = item_{abcdabcdab}\; where\,k = abcdabcdab $ 

 

이를 해결하기 위해서는 키 공간 $U$를 더 작은 공간인 $m = \Theta(n)$ 으로 mapping 해서 Direct Access Array 를 이용해야 합니다. 이 아이디어가 바로 Hashing 입니다.

 

Hashing

$h(k)\,:\,\{0,\,...,\,u-1\}\,\rightarrow\,\{0,\,...\,m-1\}\;where\;m=O(n)$

 

키 유니버스 사이즈 u 가 m 보다 훨씬 클 때 키 공간을 작은 m 공간으로 맵핑 해서 m 개의 슬롯을 가지는 Direct Access Array 인덱스와 h(k) 를 1:1 매칭시킨다 

 

Hashing 아이디어를 다시 한번 정리했습니다. 이 때 h: U -> m 을 해쉬 함수(hash function or hash map), m 슬롯을 가지는 Direct Access Array 를 hash table 이라고 합니다 그리고 h(k) 를 k 의 해쉬(hash)라고 합니다.

 

하지만 $m < u$ 의 상황에서 해쉬 함수를 이용하면 문제가 발생합니다. 키에 대해서 사전에 아무런 정보가 없다면 어떠한 해쉬 함수를 이용하더라도 동일한 인덱스로 여러개의 키가 맵핑됩니다. 이를 pigeonhole principle 이라고 한다네요.

두 키 이상의 해쉬 값이 같아지는, $h(k_1) = h(k_2)$, 것을 두 키가 충돌했다(collide)고 합니다.

 

이러면 아이템을 어떻게 저장해야 할까요

한 방법은 충돌한 키의 아이템을 이미 아이템이 저장되어있는 배열의 해쉬 값 인덱스가 아닌 다른 인덱스에 저장하는 방법이 있습니다. 또 다른 방법은 배열이 아닌 아에 다른 자료 구조에 저장하는 방법이 있습니다. 첫 번째 방법을 Open Addressing, 두 번째 방법을 Chaining 이라고 합니다. 실제 구현할 때는 open addressing 을 훨씬 많이 쓴다고 합니다. 하지만 여기서는 분석의 편의를 위해 chaining 을 충돌 해결의 방법으로 상정하겠습니다.

 

Chaining

chaining 은 해쉬 테이블이 아닌 다른 자료 구조에 아이템을 저장해서 충돌을 해결하는 방법입니다. 해쉬 테이블의 각 인덱스에는 아이템이 아닌 또 다른 자료 구조를 가르키는 포인터가 저장됩니다. 이 자료 구조는 insert, search, 그리고 delete(k) 를 상수 비용으로 지원하는 Set Interface 이고 chain 이라고 합니다. linked list 나 array 를 생각하면 됩니다.

충돌이 발생해도 모든 해쉬 테이블의 chain 의 크기가 상수 이면 insert, serach, 그리고 delete(k) 를 O(1) 으로 수행할 수 있게 되고 이것이 hashing 을 통해 달성하고자 하는 목표인데요. 이를 위해서는 해쉬 함수가 중요합니다. 만약에 아주 안좋은 해쉬 함수를 선택해서 모든 키의 해쉬 값이 동일한 인덱스를 가진다면, 해당 인덱스 chain 의 크기는 O(n) 이 되고 insert, serach, 그리고 delete(k) 의 비용도 O(n) 이 되버립니다. 최악이죠.

 

이상적으로 어떠한 키 유니버스가 주어져도 충돌의 개수를 줄여서 테이블의 가장 큰 chain 의 크기가 상수인 해쉬 함수를 선택해야 합니다.

 

Universal Hashing

좋은 해쉬 함수의 기준을 다시 한번 정리하겠습니다.

 

어떠한 키 유니버스가 주어져도 충돌의 개수를 줄여서 가장 큰 chain 의 크기를 상수로 만드는 해쉬 함수

 

만약 키 집합이 uniformly distribtued 하다면 $h(k) = k \; mod \; m $ 인 해쉬 함수도 좋은 해쉬 함수가 될 수 있습니다. 두 키가 충돌할 확률을 1 / m 으로 만들기 때문이에요.

 

$ \underset{k_1 \neq k_2}{Pr} \{\;h(k_1) = h(k_2)\; \} = \cfrac{1}{m} $

 

키 집합에서 어떠한 키가 임의로 주어져도 h(k) 는 $\{0, 1, \, ..., \, m-1 \}$ 중 하나의 값이기 때문에

두 개의 키가 같은 값을 가질 확률이 $ \cfrac{1}{m} $ 이 됩니다. 이렇게 되면 chain 의 크기가 상수임이 보장됩니다.

이와 관련된 이론은 밑에서 다시 한번 보겠습니다.

 

하지만 이 해쉬 함수는 키 집합이 uniformly distributed 해야 한다는 조건이 붙습니다. 그렇지 않은 경우 이 해쉬 함수는 최악의 상황을 만들어낼 수 있습니다. 

예를 들어 $m = 11, \; k \in \{ 11, 22, 33, ...,  \} $ 이런 조건 이면 모든 해쉬 값은 0 이 되고 모든 아이템이 hash table 의 0 인덱스 chain 에 저장되게 됩니다.  결국, 인덱스 0 chain 의 크기는 O(n) 이 됩니다.

 

최종 목적은 키 집합에 대한 아무런 가정도 하지 않고, 어떠한 키 집합이 주어지더라도, 충돌하는 해쉬 값을 테이블 인덱스 전반으로 골고루 분산 시키는 해쉬 함수를 찾아야 합니다. 생각해보면, 해쉬 함수가 미리 정해져 있는 한, 이 해쉬 함수의 특성을 보고 나쁜 상황을 만드는 키 집합을 선택할 수가 있게 됩니다.

 

결론적으로, 해쉬 함수를 미리 결정하지 않고 임의로 선택해서 어떠한 키 집합에도 대응하는 전략이 Universal Hashing 입니다.

자 이제, Universal Hashing 을 본격적으로 알아보겠습니다.

 

Universal Hashing 의 아이디어는 다음과 같습니다.

 

• 해쉬 함수 family $H$ 에서 임의로 하나의 해쉬 함수를 선택한다
• $H$ 는 다음을 만족하면 universal hashing family 이다

$\underset{h \in H}{Pr}\{\;h(k)=h(k^{'})\;\} \leq \cfrac{1}{m} \; for \; all \; k \neq k^{'}$

 

• h 를 임의로 선택하는 것이고 키 집합에 대해서는 아무런 가정을 하지 않는다

Theorem: $For \; n \; arbitrary \; distinct \; keys \; and \; random \; h \in H, \; where \; H \; is \; a \; universal \; hashing  \; family,$

E[ number of keys colliding in a slot ] $ = 1 + \alpha \;\; where \; \alpha = \cfrac{n}{m}$

 

Universal hashing family 에서 선택된 임의의 해쉬 함수 h 는 어떠한 키 집합(유니버스)이 와도 아이템의 개수인 n 개의 키를 m 공간으로 맵핑합니다. 이 때, 해쉬 값들이 평균적으로 충돌하는 개수가 $1+\alpha$ 이하가 된다는 이론입니다. $\alpha$ 는 $\cfrac{n}{m}$ 이고 m = O(n) 이므로 충돌 개수는 상수가 됩니다.

 

충돌 확률을 1/m 이하로 낮추는 구체적인 해쉬 함수의 형태는 이따가 살펴보기로 하고 먼저 이론의 증명을 보겠습니다.

 

n 개의 키 $k_1, k_2, ..., k_n$ 가 있을 때 다음의 indicator random variable 을 정의합니다.

 

$I_{i, j} = $ $\begin{cases}1~&{\text{if}}~h(k_i) = h(k_j) \\0~&{\text{otherwise}}  \end{cases}$

 

두 키가 충돌하는 경우와 그렇지 않은 경우를 확률적으로 표현했습니다.

그럼 다음이 성립합니다.



이론이 어렵지 않게 증명되는 것을 확인할 수 있습니다.

 

Dot Product Hash Family

이제 마지막으로 $\text{Pr}\{h(k_i)=h(k_j)\} \leq \cfrac{1}{m}$ 을 만드는 hash family 를 알아보겠습니다. 이 hash family 말고 다른 형태도 존재합니다.

 

가정

• m 은 소수
• $u = m^r$ where $r$ 은 정수

어떤 키 집합이 주어져도 이 가정을 충족하도록 m 과 u 를 조정할 수 있습니다.

이제 키를 m 진법의 수로 생각합니다. $k = <k_0, k_1, ..., k_{r-1}>$

또 다른 키 a 도 m 진법으로 표현하고 $a = <a_0, a_1, ..., a_{r-1}>$ 

다음을 정의합니다. 

 

dot product hash family: $H = \{h_a \;| \;a \in \{0, 1, ..., u-1\} \}$

 

구체적인 예시는 다음과 같습니다.

키가 201, m이 17, 그리고 r 이 3 일 때 u 는 4913 이 됩니다. 이때, 또 다른 키 $a$를 임의로 뽑습니다.

$k = 201_{10} = <14, 11, 0>$ (14*17^0 + 11*17^1+0*17^2 = $201_{10}$)

$a = 3590_{10} = <3, 7, 12>$ (3*17^0 + 7*17^1+12*17^2 = $3590_{10}$)

$14*3 + 11*7 + 0*12 \;\; (mod \;17) = 1$ 

이 때, a 는 $\{0, 1, ..., u - 1\}$ 에서 1/4913 확률로 임의로 선택한 수 입니다. 따라서, hash 함수는 확률적으로 결정됩니다!

결론적으로 k = 201 이면 hash table 인덱스 1의 chain 에 키와 아이템을 저장합니다.

 

이 hash family 는 Universal Hash Family 입니다.

즉, 이 hash family 에서 임의로 뽑은 hash 함수는 두 키가 충돌할 확률을 1/m 이하로 만듭니다.

 

증명은 다음과 같습니다.

 

마지막 두 번째 줄이 $\underset{a_{\text{not d}}}{E}[\cfrac{1}{m}]$ 이 되는 이유는 $a_d$ 는 결국 mod m 의 결과로 나오는 수 이기 때문에

$\underset{a_d}{\text{Pr}}$ 는 1/m 이 됩니다. (0, 1, ..., m -1) 의 중 하나의 수가 나올 확률이기 때문이죠.

 

 

참조

https://www.youtube.com/watch?v=Nu8YGneFCWE&list=PLUl4u3cNGP63EdVPNLG3ToM6LaEUuStEY&index=5

https://www.youtube.com/watch?v=z0lJ2k0sl1g&list=PLTV7NgF818VXpV2P-Px2H74hvEBL2o-G2&index=11