해시 테이블: randomness를 이용한 충돌 해결 - universal hashing
체이닝의 한계 극복, 무작위성의 힘
지난 시간에 살펴본 체이닝 방식은 해시 테이블에서 충돌을 해결하는 간단하고 효율적인 방법이지만, 최악의 경우 모든 키가 같은 슬롯에 매핑되어 성능이 저하될 수 있다는 한계점을 가지고 있었다. 이러한 문제를 해결하기 위해 randomness를 도입하는 방법을 소개한다.
무작위 해시 함수: 균등한 분포
이상적인 해시 함수는 모든 키를 해시 테이블의 슬롯에 균등하게 분포시켜 충돌을 최소화한다. 하지만 실제로는 키의 분포를 미리 알 수 없기 때문에, 완벽한 해시 함수를 설계하는 것은 어렵다.
이러한 문제를 해결하기 위해 무작위 해시 함수(random hash function)를 사용한다. 무작위 해시 함수는 키를 입력으로 받아 무작위로 슬롯을 출력하는 함수이다. 즉, 각 키가 어떤 슬롯에 매핑될지 예측할 수 없도록 한다.
"h is uniformly random"은 해시 함수 h가 모든 키를 모든 슬롯에 균등한 확률로 매핑한다는 것을 의미한다. 즉, 각 키가 특정 슬롯에 매핑될 확률은 \( \frac{1}{n} \)(n은 슬롯의 개수)이다.
무작위 해시 함수를 사용하면, 각 버킷에 저장되는 아이템 수의 기댓값이 2 이하가 된다. 이는 체이닝 방식에서 최악의 경우 발생할 수 있는 O(n) 검색 시간을 O(1)로 줄여준다.
 |
| How can "h" be uniformly random? |
해시 함수 구현의 어려움: space 문제
무작위 해시 함수를 구현하는 가장 직관적인 방법은 모든 가능한 해시 함수 중에서 하나를 무작위로 선택하는 것이다. 하지만 키의 개수가 U, 슬롯의 개수가 n이라면, 가능한 해시 함수의 개수는 \(n^{U} \) 개가 된다. 이는 매우 큰 공간(ASCII string 기준 \(128^{140}\))이며, 모든 해시 함수를 저장하고 무작위로 선택하는 것은 현실적으로 불가능하다.
 |
| too big to handle on the computer |
해시 패밀리: 더 작은 해시 함수 집합
모든 해시 함수를 저장하는 대신, 더 작은 해시 함수 집합인 해시 패밀리(hash family)를 사용할 수 있다. 해시 패밀리는 특정 조건을 만족하는 해시 함수들의 집합이다.
하지만 해시 패밀리를 사용하면 새로운 문제가 발생한다. 특정 해시 패밀리 H에 대해, 어떤 키 x와 y가 충돌할 확률이 높은 해시 함수 h가 존재할 수 있다. 즉, H에서 무작위로 해시 함수를 선택하더라도, x와 y는 높은 확률로 충돌하게 된다. (여전히 collision이 일어날 가능성이 있다)
유니버설 해시 패밀리: 충돌 확률 최소화
이러한 문제를 해결하기 위해 유니버설 해시 패밀리(universal hash family)를 사용한다. 유니버설 해시 패밀리는 다음 조건을 만족하는 해시 함수들의 집합이다.
유니버설 해시 패밀리 H에서 임의로 선택된 해시 함수 h에 대해, 임의의 두 키 x와 y가 충돌할 확률은 \( \frac{1}{n} \) 이하이다.
이 말은 앞에서 언급했던 uniformly random이라는 말과 같다. 즉, 유니버설 해시 패밀리는 키의 분포에 관계없이 충돌 확률을 최소화하여 해시 테이블의 성능을 보장할 수 있다.
유니버설 해시 함수 구현: 두 단계 매핑
유니버설 해시 함수는 일반적으로 두 단계 매핑으로 구현된다.
- 첫 번째 단계: 키를 크기가 p인 정수 집합으로 매핑한다. 이때 p는 M보다 크거나 같은 소수이다.
- 두 번째 단계: 첫 번째 단계에서 얻은 정수를 해시 테이블의 슬롯에 매핑한다.
 |
| example of universal hash function |
첫 번째 단계에서 사용하는 함수 f는 다음과 같이 정의할 수 있다.
f(x) = ((ax + b) mod p) mod n
여기서 a는 1과 p-1 사이의 무작위 정수이고 b는 0과 p-1 사이 무작위 정수다. 이 함수는 키 x를 0과 p-1 사이의 정수로 매핑하며, a와 b를 무작위로 선택함으로써 충돌 확률을 최소화한다.
 |
| 2 step of universal hash function |
여기서 핵심은 첫번째 단계에서 충돌이 일어나지 않는다는 점이다.
유니버설 해시 패밀리의 장점: 공간 효율성
유니버설 해시 패밀리를 사용하면 모든 해시 함수를 저장하는 것보다 훨씬 적은 공간을 사용하여 무작위 해시 함수를 구현할 수 있다. a와 b를 저장하는 데 필요한 비트 수는 O(log p(p-1)) = O(log M)이며, 이는 모든 해시 함수를 저장하는 데 필요한 O(M log n) 비트보다 훨씬 작다. (ASCII string 기준 140log(128) vs \(128^{140}\)))
결론: 무작위성을 통한 해시 테이블 성능 향상
무작위 해시 함수와 유니버설 해시 패밀리를 사용하면 해시 테이블의 충돌 확률을 최소화하고 성능을 향상시킬 수 있다. 유니버설 해시 패밀리는 키의 분포에 관계없이 균등한 해싱을 제공하며, 공간 효율성도 높다.
추천글 :
[알고리즘] hash table - direct addressing, hash function, chaining
(https://hyeonb.blogspot.com/2024/10/hash-table-direct-addressing-hash.html)
[알고리즘] Randomized algorithm - quicksort, randomized selection, majority element
(https://hyeonb.blogspot.com/2024/10/randomized-algorithm-quicksort.html)
