이상한 코딩 나라의 혜돌이

# 유니버설 해싱 (Universal Hashing) * 유니버설 해싱이란? 같은 자리에 여러 개의 키가 해시되는 것을 막기 위하여 실제 저장되는 키들과 독립적인 해시 함수를 무작위로 선택하는 것 유니버설 해싱에서 실행 초기에는 주의 깊게 설계된 함수의 집합으로부터 해시 함수를 무작위로 선택한다. 이때 해시 함수를 무작위로 선택하기 때문에 이 알고리즘을 동일한 입력에 대해서도 실행할 때마다 다르게 동작할 수 있어 임의의 입력에 대해 좋은 평균적 성능을 보장한다. * 유니버설 해시 함수 집합의 조건 Η를 키들의 전체집합 U를 {0, 1, ..., m - 1} 로 대응시키는 해시 함수들의 유한한 집합이라고 하자. 서로 다른 키 k, l ∈ U 각 쌍에 대해 h(k) = h(l)인 해시 함수 h ∈ Η 의 개..