유니버설 해싱 편집하기

유니버설 해싱(Universal Hashing)은 해시 함수의 집합 중에서 하나를 무작위로 선택하여 사용하는 해싱 기법으로, '''모든 키 쌍이 충돌할 확률이 최소화되도록 보장하는 해시 방식'''이다. 해시 함수가 고정되지 않고 무작위로 선택되기 때문에, 입력에 의존적인 공격이나 최악의 성능을 회피할 수 있다는 장점이 있다.
==개념==
*일반적인 해시 테이블은 해시 함수가 고정되어 있음 → 충돌 위험 존재
*유니버설 해싱은 '''해시 함수의 집합 H에서 무작위로 하나의 해시 함수 h ∈ H를 선택'''
*임의의 키 쌍 x ≠ y에 대해 충돌할 확률이 낮도록 H가 설계됨
==정의==
해시 함수 집합 H가 유니버설(universal)하다는 것은 다음 조건을 만족함:
*임의의 서로 다른 키 x ≠ y에 대해,
*선택된 해시 함수 h ∈ H에서 충돌 확률이 다음과 같을 때:
**Pr[h(x) = h(y)] ≤ 1/m
여기서 m은 해시 테이블의 크기
==유니버설 해시 함수 예시==
*모듈러 기반 해시 함수
**정수 키 x에 대해, 소수 p > u (키 공간 크기), 그리고 임의의 a ∈ {1,...,p−1}, b ∈ {0,...,p−1}에 대해:
 h<sub>a,b</sub>(x) = ((a⋅x + b) mod p) mod m
*이 함수 집합은 유니버설이며, a, b를 무작위로 선택함
==장점==
*충돌 확률을 수학적으로 상한선 아래로 제한할 수 있음
*입력 키 분포와 상관없이 성능 유지 가능
*[[보안 해시]], [[암호학적 해시]]와 달리 계산이 빠르고 간단
==단점==
*해시 함수 설정에 추가적인 무작위 요소가 필요
*해시 함수를 매번 선택하거나 유지해야 하므로 구현이 약간 복잡해짐
==응용==
*[[해시 테이블]]에서의 키 충돌 최소화
*랜덤화된 알고리즘 설계
*[[블룸 필터]], [[완전 해시]], [[암호학]] 분야
*보안 환경에서 입력에 따른 악의적 충돌 방지
==같이 보기==
*[[해시 함수]]
*[[해시 테이블]]
*[[충돌 해결 기법]]
*[[완전 해싱]]
*[[랜덤화 알고리즘]]
==참고 문헌==
*Carter, J. L., & Wegman, M. N. (1979). Universal classes of hash functions. Journal of Computer and System Sciences
*Cormen, T. H. et al. (2009). Introduction to Algorithms. MIT Press
*Mitzenmacher, M., & Upfal, E. (2005). Probability and Computing. Cambridge University Press
[[분류:알고리즘]]