유니버설 해싱 편집하기 (부분)

== 시뮬레이션 ==
해시 대상: apple, pear, kiwi, lime, mango

* 각 단어를 고정 길이 벡터로 변환 (알파벳을 숫자 1~26로 매핑하고, 부족하면 0으로 패딩)
* 예) "lime" → (12, 9, 13, 5, 0)

해시 함수 형태: ha(x) = (a0 + a1·x1 + a2·x2 + a3·x3 + a4·x4 + a5·x5) mod m<ref>실제 실무적으론 해시 함수가 저렇게 단순 곱셈 및 덧셈이기보단 좀 더 복잡한 다항식으로 구성된다.</ref>

* a = (a0, ..., a5)는 랜덤 벡터 (각 요소는 0~28)
* x = (x1, ..., x5)는 단어를 숫자로 변환한 벡터
* m은 해시 테이블의 크기
** 여기선 가장 타이트하게 해시 대상의 수인 5로 한다.

a값은 미리 정해진 고정 난수값이다. 예를 들어 [[의사 난수 생성기]]에서 시드값을 정해놓으면 항상 같은 난수를 사용할 수 있다.<ref>일시적으로 사용되는 세션 내 암호화에선 이 난수값이나 난수 생성을 위한 시드값이 세션에 저장될 수도 있다.</ref>

* 여기선 임의로, a = [20, 3, 0, 23, 8]

해시값을 만들어보자

* h(apple) = (20 + 3×1 + 0×16 + 23×16 + 8×12 + 7×5) mod 5 = (20 + 3 + 0 + 368 + 96 + 35) mod 5 = 522 mod 5 = 2
* h(pear) = (20 + 3×16 + 0×5 + 23×1 + 8×18 + 7×0) mod 5 = (20 + 48 + 0 + 23 + 144 + 0) mod 5 = 235 mod 5 = 0
* h(kiwi) = (20 + 3×11 + 0×9 + 23×23 + 8×9 + 7×0) mod 5 = (20 + 33 + 0 + 529 + 72 + 0) mod 5 = 654 mod 5 = 4
* h(lime) = (20 + 3×12 + 0×9 + 23×13 + 8×5 + 7×0) mod 5 = (20 + 36 + 0 + 299 + 40 + 0) mod 5 = 395 mod 5 = 0
* h(mango) = (20 + 3×13 + 0×1 + 23×14 + 8×7 + 7×15) mod 5 = (20 + 39 + 0 + 322 + 56 + 105) mod 5 = 542 mod 5 = 2

0과 2 두가지 키에서 충돌이 발생했다. 이와 같이 mod 5를 하기 때문에 각 키별 충돌 가능성은 1/5이다. 이 확률을 더 줄이기 위해 보통 해시 테이블은 여유 있게(over-provisioning) 잡는다. 그리고 충돌을 최소화하기 위해 [[FKS 해싱]]을 사용한다.